在信息学奥赛中，有一类问题是模拟一个游戏的对弈过程，或者模拟一项任务的操作过程，进行统计计分、判断输赢等。这些问题很难建立数学模型用特定算法解决，一般只能采用“模拟”法。用模拟法解题必须关注以下几个问题：审题要仔细，游戏规则不能错；分析要全面，各种特例不能漏；编程要细心，测试运行要到位。
- 定义：用计算机的操作模拟现实世界中的事务变化，从而完成相应任务。
- 做法: 读懂题目，用纸和笔，针对样例数据，模拟计算一遍，理清各个数据之间的内在逻辑，然后建立 数学模型, 用计算机模拟出来数据的处理过程。
- 可以用于解决第1、2道题目
读题-> 建模-> 代码实现-> 调试、优化
技巧：
通过程序设计，用计算机来模拟生成日常生活中的相关数据，
以分析相应的数据，从而对实际工作进行预判。算法思想：
在程序设计语言中，可以使用随机函数来模拟自然界中发生的不可预测的情况。在C语言中使用srand()和rand()两个函数来生成随机数。
提示：函数srand（）用来初始化随机数发生器，然后使用rand()函数来生成随机数要使用这两个函数，要使用的头文件是“time.h”和“stdlib.h”。 一般情况下使用过程为：
srand(time(NULL));
i=rand()%100+1;使用上面的语句，变量i的值将会在1~100之间。
实例：用模拟算法来编写一个猜数字游戏。由计算机随机生成一个1~100的整数，然后由用户来猜这个数，根据用户猜测的次数分别给出不同的提示文字。
#include <time.h>
#include <iostream>
#include <cstdio>
#include <conio.h>
#include <stdlib.h>
using namespace std;
int main()
{
int n,m,i=0;
srand(time(NULL));
n=rand()%100+1;
do{
cout<<"输入猜测的数";
cin>>m;
i++;
if(m>n)
cout<<"NO!数太大了" <<endl;
else if(m<n)
{
cout<<"NO!数太小了"<<endl;
}
}while (m!=n);
cout<<"yes"<<endl;
cout<<"一共猜了"<<i<<"次" ;
getch();
return 0;
}
自然界和日常生活中的有些事物，若用计算机很难建立起枚举、贪心等算法，甚至没法建立数学模型。我们解决这类问题可用模拟法。所谓模拟法，就是用计算机模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起的过程状态的变化，然后从中得出解答。
实例讲解：
P1042 乒乓球
- 重点: 如果一局比赛刚开始，则此时比分为0比0。直到分差大于或者等于2，才一局结束
- 难点:
- 读取若干行, 不是一行, 不是固定行数, 怎么判断读取完毕呢?
- ‘E’ 代表结束, 并且’E’后面可能还有输入
- 超过11 或者 21分, 分值要差2分才行.
- 下一局开始 0:0 也要输出.
参考代码:
#include <bits/stdc++.h>
using namespace std;
int a11[10000], b11[10000];
int a21[10000], b21[10000];
int cnt11, cnt21;
char c;
int main()
{
while(c = getchar()) {
if(c == 'E')
break;
if(c=='W') {
a11[cnt11]++;
a21[cnt21]++;
} else if(c == 'L') {
b11[cnt11]++;
b21[cnt21]++;
} else
continue;
if(a11[cnt11] >= 11 || b11[cnt11] >= 11) {
if(abs(a11[cnt11] - b11[cnt11]) >= 2)
cnt11++;
}
if(a21[cnt21] >= 21 || b21[cnt21] >= 21) {
if(abs(a21[cnt21] - b21[cnt21]) >= 2)
cnt21++;
}
}
int i;
for(i = 0; i <= cnt11; i++) {
printf("%d:%d\n", a11[i], b11[i]);
}
printf("\n");
for(i = 0; i <= cnt21; i++) {
printf("%d:%d\n", a21[i], b21[i]);
}
return 0;
}
P1328 生活大爆炸版石头剪刀布
难点:
- 如何建模? 不可能把每种出拳都用if来比较的. 上面图形多么像个二维数组啊. 就用二维数组吧, 来描述甲对乙的输赢的分数. 赢为1, 输为0. 0 表示“剪刀”，1 表示“石头”，2 表示“布”，3 表示“蜥蜴人”，4表示“斯波克”.
int score[5][5] = {
{0,0,1,1,0},
{1,0,0,1,0},
{0,1,0,0,1},
{0,0,1,0,1},
{1,1,0,0,0}
};
- 周期… 周期到了从头开始吧. 可以用取模运算, 也可以用if判断.
参考代码:
#include <bits/stdc++.h>
using namespace std;
int score[5][5] = {
{0,0,1,1,0},
{1,0,0,1,0},
{0,1,0,0,1},
{0,0,1,0,1},
{1,1,0,0,0}
};
int a[208],b[208];
int n, an, bn;
int sa, sb;
int main()
{
int i;
scanf("%d %d %d", &n, &an, &bn);
for(i = 0; i < an; i++)
scanf("%d", &a[i]);
for(i = 0; i < bn; i++)
scanf("%d", &b[i]);
int ai = 0, bi = 0;
for(i = 0; i <n; i++) {
sa += score[a[ai]][b[bi]];
sb += score[b[bi]][a[ai]];
ai =(ai + 1) %an;
bi = (bi + 1) %bn;
}
printf("%d %d", sa, sb);
return 0;
}
P1563 玩具谜题
难点:
- 描述好多, 题意需要仔细分析
- 环和取模的关系
- 数组存放按逆时针和习惯相反
参考代码
#include <bits/stdc++.h>
using namespace std;
int n,m;
char toy[100008][12];
int a[100008];
int main()
{
int i;
int d, s;
scanf("%d %d", &n, &m);
for(i = 0; i < n; i++){
scanf("%d %s", &a[i], toy[i]);
}
int idx = 0;
int flag = 1; //逆时针+ 1； 顺时针 -1 -
for(i=0; i < m; i++)
{
scanf("%d %d", &d, &s);
if (a[idx] == 0) {
if(d == 0){
flag = -1;
} else {
flag = 1;
}
} else {
if(d == 0){
flag = 1;
} else {
flag = -1;
}
}
idx = (idx + flag * s + n)%n;
}
printf("%s", toy[idx]);
return 0;
}补充知识
| 函数名 | 格式 | 功能说明 | 列子 |
|---|---|---|---|
| 绝对值函数 | abs(x) | 求一个数的绝对值 | abs(-5) = 5 |
| 自然数指数函数 | exp(x) | 求实数x的自然指数e^nen | exp(1)=2.718282 |
| 向下取整 | floor(x) | 求不大于实数x的最大整数 | floor(3.14) = 3 |
| 向上取整 | ceil(x) | 求不小于实数x的最小整数 | ceil(3.14) = 4 |
| 自然对数函数 | log(x) | 计算x的自然数对数 | log(1) = 0 |
| 指数函数 | pow(x,y) | 计算x^yxy 结果为双精度实数 | pow(2,3) = 8 |
| 随机函数 | rand() | 产生0 到 RAND-MAX之间的随机数 | |
| 平方根函数 | sqrt(x) | 求实数x的平方根 | sqrt(25) = 5 |
题单:
- P1042 乒乓球
- P2670 扫雷游戏
- P1563 玩具谜题
- P4924 [1007]魔法少女小Scarlet
- P1328 生活大爆炸版石头剪刀布
- P1518 [USACO2.4]两只塔姆沃斯牛 The Tamworth Two
- P1067 多项式输出
- P1098 字符串的展开