第27章 模拟算法
| 等级 | 知识块 | 考查频率 |
|---|---|---|
| GESP C++ 三级 | 模拟法(原理、特点、实际问题) | ⭐⭐⭐ |
模拟算法:照着题目描述的运行过程或操作步骤,一步一步地计算和操作,最终得到结果。不需要复杂数学推导,只要把规则忠实复现即可。三级常考。
27.1 模拟算法核心概念
核心思路:按部就班复现题目流程。题目给出清晰、分步执行的过程(游戏、排队、物理运动、计时、流程操作等),我们就定义状态变量、用循环/分支把每一步规则写出来。
适用场景:流程清晰、规则明确,但用公式不好直接算的题目。
27.2 模拟算法标准实现步骤
- 阅读理解完整流程,拆分每一步操作;
- 定义变量存储过程状态(时间、数量、位置、窗口空闲时刻等);
- 用循环/分支复现每一步规则;
- 每次操作后更新状态变量;
- 满足终止条件后输出最终结果。
27.3 模拟算法优缺点
优点
- 逻辑与题目描述一一对应,易懂、好写;
- 无需复杂公式,新手友好;
- 读懂流程就能实现,适用范围极广。
缺点
- 步骤极多时循环量大、效率偏低;
- 对文字细节敏感,漏一条规则就错;
- 大量状态记录占用较多内存。
模拟题失分几乎都不是算法难,而是没看清某条规则(比如"遇到周末不营业""满 100 减 10")。动手前先把所有约束列成清单,逐条对应到代码。
27.4 经典模拟代码示例
示例1:掷两枚骰子 10 次,统计和为 7 的次数
#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:银行多窗口排队模拟
#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 秒)
#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 次反弹高)
#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 模拟编写注意事项
- 逐字阅读题目规则,不漏任何限制条件;
- 状态变量初始化必须符合题目初始状态;
- 循环终止条件严格对应题目结束场景;
- 随机类模拟必须
srand(time(0))保证每次不同; - 调试时打印中间状态,快速定位逻辑错误。
示例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 错)。