第27章 模拟算法

第27章 模拟算法

GESP 三级定位
等级知识块考查频率
GESP C++ 三级模拟法(原理、特点、实际问题)⭐⭐⭐

模拟算法:照着题目描述的运行过程或操作步骤,一步一步地计算和操作,最终得到结果。不需要复杂数学推导,只要把规则忠实复现即可。三级常考。

27.1 模拟算法核心概念

核心思路:按部就班复现题目流程。题目给出清晰、分步执行的过程(游戏、排队、物理运动、计时、流程操作等),我们就定义状态变量、用循环/分支把每一步规则写出来。

适用场景:流程清晰、规则明确,但用公式不好直接算的题目。

模拟算法:状态随步骤变化

27.2 模拟算法标准实现步骤

  1. 阅读理解完整流程,拆分每一步操作;
  2. 定义变量存储过程状态(时间、数量、位置、窗口空闲时刻等);
  3. 用循环/分支复现每一步规则;
  4. 每次操作后更新状态变量;
  5. 满足终止条件后输出最终结果。

27.3 模拟算法优缺点

优点

  1. 逻辑与题目描述一一对应,易懂、好写;
  2. 无需复杂公式,新手友好;
  3. 读懂流程就能实现,适用范围极广。

缺点

  1. 步骤极多时循环量大、效率偏低;
  2. 对文字细节敏感,漏一条规则就错;
  3. 大量状态记录占用较多内存。
模拟题最怕"漏规则"

模拟题失分几乎都不是算法难,而是没看清某条规则(比如"遇到周末不营业""满 100 减 10")。动手前先把所有约束列成清单,逐条对应到代码。

27.4 经典模拟代码示例

示例1:掷两枚骰子 10 次,统计和为 7 的次数

dice_sim.cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
srand(time(0)); // 设置随机种子
int count7 = 0;
for (int i = 0; i < 10; i++) {
int d1 = rand() % 6 + 1;
int d2 = rand() % 6 + 1;
if (d1 + d2 == 7) count7++;
}
cout << "点数和为 7 的次数:" << count7 << endl;
return 0;
}

示例2:银行多窗口排队模拟

bank_sim.cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
srand(time(0));
int windows[3] = {0}; // 3 个窗口的"空闲时刻"
for (int i = 0; i < 5; i++) { // 5 位客户
int service = rand() % 5 + 1;
int minT = windows[0], idx = 0;
for (int j = 1; j < 3; j++) // 找最早空闲窗口
if (windows[j] < minT) { minT = windows[j]; idx = j; }
int start = windows[idx];
windows[idx] = start + service; // 更新该窗口空闲时刻
cout << "客户" << i + 1 << " 窗口" << idx + 1
<< " 开始:" << start << " 结束:" << windows[idx] << endl;
}
return 0;
}

示例3:时钟秒针走动(输出 10 秒)

clock_sim.cpp
#include <iostream>
using namespace std;
int main() {
int h = 12, m = 30, s = 0;
for (int i = 0; i < 10; i++) {
printf("%02d:%02d:%02d\n", h, m, s);
s++;
if (s == 60) { s = 0; m++; if (m == 60) { m = 0; h++; if (h == 24) h = 0; } }
}
return 0;
}

示例4:小球下落反弹(每次反弹为一半,求 5 次落地总路程与第 5 次反弹高)

ball_sim.cpp
#include <iostream>
using namespace std;
int main() {
double h = 10.0, total = 0.0;
for (int i = 0; i < 5; i++) {
total += h; // 下落
if (i < 4) { h /= 2; total += h; } // 反弹(最后一次不反弹)
}
cout << "第5次落地总路程:" << total << " 米\n";
cout << "第5次反弹高度:" << h / 2 << " 米\n"; // i=4 时 h 已是第5次落地后的反弹高
return 0;
}
状态变量是模拟的灵魂

模拟题的关键往往是"用什么变量记录状态"。上面银行题用 windows[3] 记录每个窗口何时空闲;时钟题用 h/m/s 三个变量互相进位。先把状态设计清楚,代码自然就出来了。

27.5 模拟编写注意事项

  1. 逐字阅读题目规则,不漏任何限制条件;
  2. 状态变量初始化必须符合题目初始状态;
  3. 循环终止条件严格对应题目结束场景;
  4. 随机类模拟必须 srand(time(0)) 保证每次不同;
  5. 调试时打印中间状态,快速定位逻辑错误。
慎用 sleep 做"真实时间"模拟

示例3 用 this_thread::sleep_for 只是为了演示"每秒跳一下",考试/评测中不要靠 sleep 控制逻辑时间,应该用整数变量累加时间步,否则会超时或被判 TLE。

27.6 选择题练习

1. 模拟算法的核心思路是?

A. 寻找数学公式直接求解
B. 按照题目描述的步骤逐步复现
C. 递归分解
D. 贪心取优

点击展开参考答案与解析

答案:B

解析:模拟就是"按题目步骤忠实复现",选 B。

2. 下面哪类问题最适合用模拟算法?

A. 大整数乘法
B. 规则清晰、分步执行的过程(如排队、计时)
C. 求最短路径
D. 海量数据排序

点击展开参考答案与解析

答案:B

解析:规则清晰、分步执行的题目(排队、计时、游戏规则)最适合模拟,选 B。大整数、最短路、海量排序各有专门算法。

3. 在银行窗口模拟中,记录"每个窗口何时空闲"最适合用?

A. 一个整数
B. 一个数组
C. 一个字符串
D. 一个布尔值

点击展开参考答案与解析

答案:B

解析:多个窗口各有空闲时刻,用数组 windows[3] 最合适,选 B。

4. 模拟算法最容易出错的原因是?

A. 算法思想太难
B. 漏掉题目中的某条规则
C. 一定会超时
D. 无法用 C++ 实现

点击展开参考答案与解析

答案:B

解析:模拟题失分多因为"漏规则"(比如忘记某条边界约束),而非算法难,选 B。

5. 关于随机类模拟,下列说法正确的是?

A. 不需要设置随机种子
B. 应设置 srand(time(0)) 保证每次结果不同
C. 必须用 sleep 控制流程
D. rand() 默认返回 1~6

点击展开参考答案与解析

答案:B

解析:随机模拟应 srand(time(0)) 初始化种子保证每次不同(B 对,A 错);不应靠 sleep 控流程(C 错);rand() 返回 0~RAND_MAX,需取模才能得到指定范围(D 错)。

SShowball OI知识手册