模拟算法：数据结构与算法的完美结合

模拟算法

在自然界和我们的日常生活中，如果计算机难以建立枚举、贪心等算法，甚至无法建立数学模型。我们可以用模拟来解决这类问题。所谓模拟算法，就是利用计算机对一个过程进行模拟，通过改变数学模型的各种参数，观察这些参数的变化所引起的过程状态的变化，并从中得出答案。

用一句老话解释模拟算法，就是“照着葫芦画瓢”；官方化的诠释则是：根据题目表述进行筛选提取关键要素，按需求书写代码解决实际问题。

模拟问题的算法一般不是很复杂，关键是不能漏掉所有的条件，而且要对条件进行清楚的分析。模拟问题的求解一般都是繁琐的，在编程之前必须事先规划好各个模块的功能和结构，这样就不注重具体的编程而漏掉了一些重要的方面。回答模拟问题的通常步骤是:

(1)仔细阅读题目。对模拟题的描述一般比较详细，长度一般比较长，读的时候要逐条记录相关情况，读后要反复核对，绝对不能有错误。

(2)建立条件之间的关系，最好用一些简明的表格。

(3)仔细分析这些关系，建立这些关系的数学模型。

(4)规划各模块的结构，用相应的语言和方法描述具体算法，并逐步细化。

(5)编写程序、调试和运行。

(6)检查题目给出的样本是否通过。比赛题目一般会给出一个输入和输出的样本，为了检查程序的输入和输出格式是否正确，但是这些样本往往比用来判断比赛的测试数据简单，所以你不能满足于通过这些样本，还可以尝试绘制一些更复杂、更全面的测试数据来检查程序的正确性。经过反复调试、检查，才能解决问题。

例题一：[NOIP2014 提高组] 生活大爆炸版石头剪刀布

题目描述

石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一样，则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头剪刀布的升级版游戏。

升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势:

斯波克:《星际迷航》主角之一。

蜥蜴人:《星际迷航》中的反面角色。

这五种手势的胜负关系可以列出的是甲对乙的游戏结果。

现在,小 A 和小 B 尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小 A 以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为 6 的周期出拳,那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-......”,而如果小 B 以“剪刀-石头-布-斯波克-蜥蜴人”长度为 5 的周期出拳,那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-......”

已知小 A 和小 B 一共进行 N 次猜拳。每一次赢的人得 1 分，输得得 0 分；平局两人都得 0 分。现请你统计 N 次猜拳结束之后两人的得分。

输入格式

第一行包含三个整数：N,NA,NB,分别表示共进行 N 次猜拳、小 A 出拳的周期长度，小 B 出拳的周期长度。数与数之间以一个空格分隔。

第二行包含 NA 个整数,表示小 A 出拳的规律,第三行包含 NB 个整数,表示小 B 出拳的规律。其中，0 表示“剪刀”，1 表示“石头”，2 表示“布”，3 表示“蜥蜴人”，4 表示“斯波克”。数与数之间以一个空格分隔。

输出格式

输出一行，包含两个整数，以一个空格分隔，分别表示小 A、小 B 的得分。

样例 #1

样例输入 #1

10 5 6

0 1 2 3 4

0 3 4 2 1 0

### 样例输出 #1

6 2

## 样例 #2

### 样例输入 #2

9 5 5

0 1 2 3 4

1 0 3 2 4

### 样例输出 #2

4 4

## 提示

对于100%的数据，0 < N ≤ 200, 0 < NA ≤ 200, 0 < NB≤ 200 。

分析：

此题就是模拟猜拳操作，按照题目要求，用数组存储甲乙猜拳结果，然后用for循环来模拟猜拳操作，每一次操作对结果得分进行统计，最后只要输出最终结果即可。思路很清晰，代码实现如下：

#include<bits/stdc++.h>

using namespace std;

int main()

{

int n,na,nb;

cin>>n>>na>>nb;

int a[na+1],b[nb+1];

for(int i=1;i<=na;i++)

{

cin>>a[i];

}

for(int i=1;i<=nb;i++)

{

cin>>b[i];

}

int ans=0,bns=0;

int i=0,j=0;

for(int k=1;k<=n;k++)

{

i++; //a数组下标

j++; //b数组下标

if(i>na) //如果 i 超出了a 数组的长度，从头开始，实现循环数组

{

i=1;

}

if(j>nb) //如果 j 超出了b 数组的长度，从头开始，实现循环数组

{

j=1; //数组下标从 1开始

}

if(a[i]==0&&b[j]==1) //模拟猜拳

{

bns++;

}

if(a[i]==0&&b[j]==2)

{

ans++;

}

if(a[i]==0&&b[j]==3)

{

ans++;

}

if(a[i]==0&&b[j]==4)

{

bns++;

}

if(a[i]==1&&b[j]==0)

{

ans++;

}

if(a[i]==1&&b[j]==2)

{

bns++;

}

if(a[i]==1&&b[j]==3)

{

ans++;

}

if(a[i]==1&&b[j]==4)

{

bns++;

}

if(a[i]==2&&b[j]==0)

{

bns++;

}

if(a[i]==2&&b[j]==1)

{

ans++;

}

if(a[i]==2&&b[j]==3)

{

bns++;

}

if(a[i]==2&&b[j]==4)

{

ans++;

}

if(a[i]==3&&b[j]==0)

{

bns++;

}

if(a[i]==3&&b[j]==1)

{

bns++;

}

if(a[i]==3&&b[j]==2)

{

ans++;

}

if(a[i]==3&&b[j]==4)

{

ans++;

}

if(a[i]==4&&b[j]==0)

{

ans++;

}

if(a[i]==4&&b[j]==1)

{

ans++;

}

if(a[i]==4&&b[j]==2)

{

bns++;

}

if(a[i]==4&&b[j]==3)

{

bns++;

}

}

cout<<ans<<" "<<bns;

return 0;

}