龙空技术网

数据结构与算法-模拟算法

智美童程青少儿编程 166

前言:

当前看官们对“算法描述语言”都比较讲究,兄弟们都需要了解一些“算法描述语言”的相关文章。那么小编在网摘上搜集了一些对于“算法描述语言””的相关知识,希望各位老铁们能喜欢,同学们快快来了解一下吧!

模拟算法

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

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

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

(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;

}

标签: #算法描述语言