大家好，我是bigbigli，模擬算法我們將分為幾個(gè)章節(jié)來(lái)講，今天我們只看一維數(shù)組相關(guān)的題目

目錄

模擬的概念

訓(xùn)練：開(kāi)關(guān)燈

解析

參考代碼

訓(xùn)練：數(shù)組變化

解析

參考代碼

訓(xùn)練：折疊游戲

解析

參考代碼

---

模擬的概念

模擬算法就是模擬題目給的操作，用代碼一步一步的描述出來(lái)即可。在過(guò)程中使用的都是我們已知的各種方法，如數(shù)組元素調(diào)用、排序、枚舉等等，只是這些過(guò)程一般比較復(fù)雜。本次課程主要針對(duì)一維數(shù)組的模擬。

在各類算法競(jìng)賽中，包括CSP-J/S，NOIP等競(jìng)賽，經(jīng)常會(huì)出現(xiàn)各類“模擬題目”，遇到這種題大家不需要害怕，甚至可以將其作為“送分題”，因?yàn)槟阒恍枰凑疹}目敘述的方式來(lái)寫(xiě)程序就能得到最終答案。模擬不是一種算法，而是一種技巧，要想掌握模擬題目，就需要多讀題、多整理細(xì)節(jié)問(wèn)題。

訓(xùn)練：開(kāi)關(guān)燈

有n盞燈，從1到n按順序依次編號(hào)，初始時(shí)所有燈都處于開(kāi)啟狀態(tài)；有m個(gè)人，從1到m依次編號(hào)。

第一個(gè)人將燈全部關(guān)閉，第二個(gè)人將編號(hào)為2的倍數(shù)的燈打開(kāi)，第三個(gè)人將編號(hào)為3的倍數(shù)的燈做相反處理（即將打開(kāi)的燈關(guān)閉，將關(guān)閉的燈打開(kāi)）。依照編號(hào)遞增順序，以后的人都一樣，將凡是自己編號(hào)倍數(shù)的燈做相反處理。

請(qǐng)問(wèn)：當(dāng)?shù)趍個(gè)人操作之后，哪幾盞燈是關(guān)閉的，按從小到大輸出其編號(hào)，用逗號(hào)間隔。

【輸入描述】一行，n和m，空格隔開(kāi)

【輸出描述】順次輸出關(guān)閉的燈的編號(hào),用逗號(hào)隔開(kāi)

【輸入樣例】10 1010

【輸出樣例】1,4,9

?

解析

因?yàn)闊糁粫?huì)出現(xiàn)0和1兩種情況，我們可以使用數(shù)組元素來(lái)表示（類似桶），隨后只需要重復(fù)m次，每次尋找當(dāng)前序號(hào)的倍數(shù)為下標(biāo)的元素進(jìn)行更改，如果是1就變成0，是0就變成1。

最后對(duì)數(shù)組元素進(jìn)行判斷，找出是0的元素，就行數(shù)組元素下標(biāo)的輸出。

輸出時(shí)要注意的問(wèn)題是用逗號(hào)隔開(kāi)不同于用空格隔開(kāi)。

?

參考代碼

#include<iostream>
using namespace std;
int a[1010];//全部是0，表示關(guān)閉
int main()
{int n,m;cin>>n>>m;for(int i=2;i<=m;i++)//從第二個(gè)人開(kāi)始操作for(int j=i;j<=n;j+=i)//編號(hào)對(duì)應(yīng)倍數(shù)下標(biāo)if(a[j]==1)    a[j]=0;else a[j]=1;//更改狀態(tài)cout<<1;//1號(hào)肯定關(guān)閉for(int i=2;i<=n;i++)if(a[i]==0)    cout<<","<<i;//間隔逗號(hào)輸出return 0;
}

訓(xùn)練：數(shù)組變化

現(xiàn)有一個(gè)長(zhǎng)度為n的數(shù)組，對(duì)這個(gè)數(shù)組進(jìn)行m次操作，可以對(duì)數(shù)組進(jìn)行的操作分為以下三類：

輸入1 i： ??表示輸出數(shù)組中第i個(gè)元素的值；

輸入2 i v： 表示在數(shù)組中第i個(gè)元素前加入新的元素v；

輸入3 i： ??表示刪除數(shù)組中的第i個(gè)元素。

注意：三類操作都要滿足 i <= n。

【輸入描述】第1行：n，表示數(shù)組的初始長(zhǎng)度

第2行：n個(gè)用空格間隔的數(shù)，表示原始的數(shù)組

第3行：m，表示操作的次數(shù)

接下來(lái)的m行分別是每次對(duì)數(shù)組進(jìn)行的操作（題目描述中的三類操作中的一種）

【輸出描述】對(duì)于第一種操作輸出對(duì)應(yīng)的答案，一行輸出一個(gè)數(shù)。

【樣例輸入】

5
6 7 8 9 10
5
1 2
2 2 12
1 2
3 3
1 3

【樣例輸出】

7
12
8

解析

對(duì)題目的要求一步一步的實(shí)行，先保證數(shù)組的輸入以后，需要對(duì)三種情況進(jìn)行分類處理。第一種處理里面有輸出，后面兩種都是在操作。操作的要點(diǎn)是數(shù)組的插入和刪除。插入的話，就要求插入位置后面所有數(shù)字向后移動(dòng)一步，實(shí)現(xiàn)a[i+1]=a[i]的操作；而刪除則需要當(dāng)前位置后面所有的數(shù)字向前移動(dòng)一步，實(shí)現(xiàn)a[i]=a[i+1]。這里需要注意移動(dòng)的方向，要從頭移動(dòng)。

參考代碼

#include<iostream>
using namespace std;
int a[1001];
int main()
{int n,m,p,q,v;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];cin>>m;for(int i=0;i<m;i++){cin>>p;if(p==1){cin>>q;cout<<a[q]<<endl;}else if(p==2){cin>>q>>v;for(int j=n;j>=q;j--)//挨個(gè)向后移動(dòng)a[j+1]=a[j];a[q]=v;//單獨(dú)把插入的數(shù)字放入位置n++; //數(shù)組長(zhǎng)度加1}else  if(p==3){cin>>q;for(int j=q;j<n;j++)//挨個(gè)向前移動(dòng)a[j]=a[j+1];n--;//數(shù)組長(zhǎng)度減1}}return 0;
}

訓(xùn)練：折疊游戲

小明和小華在玩數(shù)組折疊游戲，游戲規(guī)則是，給出n個(gè)整數(shù)，按照從左到右的順序排列，現(xiàn)在需要將這列整數(shù)從中間折疊m次，右邊的疊加到左邊，每次折疊后，重合的兩個(gè)數(shù)字會(huì)相加變成一個(gè)新的數(shù)字。請(qǐng)你輸出折疊m次后的s數(shù)組。

【輸入描述】第1行：輸入一個(gè)整數(shù)n表示序列的長(zhǎng)度，輸入一個(gè)整數(shù)m表示折疊的次數(shù)。

第2行：輸入n個(gè)空格隔開(kāi)的整數(shù)，整數(shù)不超過(guò)100。

【輸出描述】輸出折疊m次后的數(shù)組。

【輸入樣例】

5 2
1 2 3 4 5

【輸出樣例】

9 6

解析

數(shù)組對(duì)折，需要把后半部分移動(dòng)到前半部分對(duì)應(yīng)位置進(jìn)行數(shù)組相加，所以移動(dòng)次數(shù)為n/2（即循環(huán)次數(shù)）。

然后需要進(jìn)行的就是數(shù)組加法。

最后要對(duì)數(shù)組長(zhǎng)度也做n/2的操作。

但是這里需要注意的是，如果長(zhǎng)度是奇數(shù)不能只是簡(jiǎn)單的n/2哦。

?

參考代碼

#include<iostream>
using namespace std;
int a[10010];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)    cin>>a[i];for(int i=1;i<=m;i++){for(int j=1;j<=n/2;j++)a[j]+=a[n-j+1];if(n%2!=0)n++;n/=2;}for(int i=1;i<=n;i++)cout<<a[i]<<' ';return 0;
}

從入門到算法，再到數(shù)據(jù)結(jié)構(gòu)，查看全部文章請(qǐng)點(diǎn)擊此處?http://www.bigbigli.com/