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

目錄

模擬的概念

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

解析

參考代碼

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

解析

參考代碼

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

解析

參考代碼

---

模擬的概念

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

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

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

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

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

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

【輸入描述】一行，n和m，空格隔開

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

【輸入樣例】10 1010

【輸出樣例】1,4,9

?

解析

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

最后對數(shù)組元素進行判斷，找出是0的元素，就行數(shù)組元素下標的輸出。

輸出時要注意的問題是用逗號隔開不同于用空格隔開。

?

參考代碼

#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++)//從第二個人開始操作for(int j=i;j<=n;j+=i)//編號對應(yīng)倍數(shù)下標if(a[j]==1)    a[j]=0;else a[j]=1;//更改狀態(tài)cout<<1;//1號肯定關(guān)閉for(int i=2;i<=n;i++)if(a[i]==0)    cout<<","<<i;//間隔逗號輸出return 0;
}

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

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

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

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

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

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

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

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

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

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

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

【樣例輸入】

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

【樣例輸出】

7
12
8

解析

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

參考代碼

#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--)//挨個向后移動a[j+1]=a[j];a[q]=v;//單獨把插入的數(shù)字放入位置n++; //數(shù)組長度加1}else  if(p==3){cin>>q;for(int j=q;j<n;j++)//挨個向前移動a[j]=a[j+1];n--;//數(shù)組長度減1}}return 0;
}

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

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

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

第2行：輸入n個空格隔開的整數(shù)，整數(shù)不超過100。

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

【輸入樣例】

5 2
1 2 3 4 5

【輸出樣例】

9 6

解析

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

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

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

但是這里需要注意的是，如果長度是奇數(shù)不能只是簡單的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)，查看全部文章請點擊此處?http://www.bigbigli.com/