算法03 模拟算法之一维数组相关内容详解

bigbigli
基础算法
2024-06-11
1327热度
4评论

模拟的概念

模拟算法就是模拟题目给的操作，用代码一步一步的描述出来即可。在过程中使用的都是我们已知的各种方法，如数组元素调用、排序、枚举等等，只是这些过程一般比较复杂。本次课程主要针对一维数组的模拟。

在各类算法竞赛中，包括CSP-J/S，NOIP等竞赛，经常会出现各类“模拟题目”，遇到这种题大家不需要害怕，甚至可以将其作为“送分题”，因为你只需要按照题目叙述的方式来写程序就能得到最终答案。模拟不是一种算法，而是一种技巧，要想掌握模拟题目，就需要多读题、多整理细节问题。

训练：开关灯

有n盏灯，从1到n按顺序依次编号，初始时所有灯都处于开启状态；有m个人，从1到m依次编号。

第一个人将灯全部关闭，第二个人将编号为2的倍数的灯打开，第三个人将编号为3的倍数的灯做相反处理（即将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的人都一样，将凡是自己编号倍数的灯做相反处理。

请问：当第m个人操作之后，哪几盏灯是关闭的，按从小到大输出其编号，用逗号间隔。

【输入描述】一行，n和m，空格隔开

【输出描述】顺次输出关闭的灯的编号,用逗号隔开

【输入样例】10 1010

【输出样例】1,4,9

解析

因为灯只会出现0和1两种情况，我们可以使用数组元素来表示（类似桶），随后只需要重复m次，每次寻找当前序号的倍数为下标的元素进行更改，如果是1就变成0，是0就变成1。

最后对数组元素进行判断，找出是0的元素，就行数组元素下标的输出。

输出时要注意的问题是用逗号隔开不同于用空格隔开。

参考代码

#include<iostream>
using namespace std;
int a[1010];//全部是0，表示关闭
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=2;i<=m;i++)//从第二个人开始操作
        for(int j=i;j<=n;j+=i)//编号对应倍数下标
            if(a[j]==1)    a[j]=0;
            else a[j]=1;//更改状态
    cout<<1;//1号肯定关闭
    for(int i=2;i<=n;i++)
        if(a[i]==0)    cout<<","<<i;//间隔逗号输出
    return 0;
}

训练：数组变化

现有一个长度为n的数组，对这个数组进行m次操作，可以对数组进行的操作分为以下三类：

输入1 i：表示输出数组中第i个元素的值；

输入2 i v：表示在数组中第i个元素前加入新的元素v；

输入3 i：表示删除数组中的第i个元素。

注意：三类操作都要满足 i <= n。

【输入描述】第1行：n，表示数组的初始长度

第2行：n个用空格间隔的数，表示原始的数组

第3行：m，表示操作的次数

接下来的m行分别是每次对数组进行的操作（题目描述中的三类操作中的一种）

【输出描述】对于第一种操作输出对应的答案，一行输出一个数。

【样例输入】

【样例输出】

7
12
8

解析

对题目的要求一步一步的实行，先保证数组的输入以后，需要对三种情况进行分类处理。第一种处理里面有输出，后面两种都是在操作。操作的要点是数组的插入和删除。插入的话，就要求插入位置后面所有数字向后移动一步，实现a[i+1]=a[i]的操作；而删除则需要当前位置后面所有的数字向前移动一步，实现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;//单独把插入的数字放入位置
            n++; //数组长度加1
        }
        else  if(p==3){
            cin>>q;
            for(int j=q;j<n;j++)//挨个向前移动
                a[j]=a[j+1];
            n--;//数组长度减1
        }
     }
     return 0;
}

训练：折叠游戏

小明和小华在玩数组折叠游戏，游戏规则是，给出n个整数，按照从左到右的顺序排列，现在需要将这列整数从中间折叠m次，右边的叠加到左边，每次折叠后，重合的两个数字会相加变成一个新的数字。请你输出折叠m次后的s数组。

【输入描述】第1行：输入一个整数n表示序列的长度，输入一个整数m表示折叠的次数。

第2行：输入n个空格隔开的整数，整数不超过100。

【输出描述】输出折叠m次后的数组。

【输入样例】

5 2
1 2 3 4 5

【输出样例】

9 6

解析

数组对折，需要把后半部分移动到前半部分对应位置进行数组相加，所以移动次数为n/2（即循环次数）。

然后需要进行的就是数组加法。

最后要对数组长度也做n/2的操作。

但是这里需要注意的是，如果长度是奇数不能只是简单的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;
}