11 模拟法
正在加载视频播放器…
GESP C++ 三级讲义：模拟法
核心目标：理解模拟算法的原理与特点，掌握“识别状态变量 → 确定更新规则 → 确定终止条件”的解题框架，能熟练运用模拟法解决数组操作、数字变换、日期推算、字符串处理等实际问题。
模拟法就是“把题目描述的规则，用代码一步一步忠实复现出来”；题目怎么说，你就怎么做，不遗漏任何细节，不改变任何顺序。
一、模拟算法的原理与特点
1. 什么是模拟法
模拟算法就是按照题目描述的规则，一步步用代码还原过程，直到得到最终结果。
如果把枚举法比作“地毯式搜索”，那么模拟法更像是在计算机里“搭建一个舞台，还原一个过程”。题目描述了一个怎样的场景、规则或者流程，你就用代码原原本本地把这个过程一步一步地“演”出来，直到得到最终结果。它不要求你有什么特别的数学技巧，但极度考验你的细心、逻辑清晰度和代码实现能力。
2. 模拟法的核心特点
| 特点 | 说明 |
|---|---|
| 忠实复现 | 题目怎么说，代码就怎么做，不遗漏、不改变 |
| 不依赖数学推导 | 不需要找公式，只需按规则逐步执行 |
| 状态驱动 | 核心是识别“什么在变”和“怎么变” |
| 考验细心程度 | 边界条件、循环终止、变量更新顺序都容易出错 |
模拟题就像是在做“阅读理解+代码还原”，只要你不漏掉题目中的任何一个细节，一步步忠实地实现，就一定能得到答案。
3. 模拟法与枚举法的区别
| 对比项 | 模拟法 | 枚举法 |
|---|---|---|
| 核心思想 | 按规则逐步复现过程 | 遍历所有可能，用条件筛选 |
| 适用场景 | 有明确的规则和流程 | 解空间有限，答案可枚举 |
| 代码结构 | 循环 + 状态更新 | 多层循环 + 条件判断 |
| 关键难点 | 忠实复现每一步规则 | 确定枚举范围和优化 |
| 典型题目 | 数组清零、日期推进、数字变换 | 完全平方数、寻找倍数 |
二、模拟法的解题框架
1. 三步框架
第一步：识别状态变量（哪些量在变化）
第二步：确定每一步的操作规则（按顺序执行什么）
第三步：确定终止条件（什么时候停止）
2. 状态变量的识别
状态变量是模拟过程中会发生变化的量。常见的状态变量类型包括：
| 状态类型 | 示例 | 典型题目 |
|---|---|---|
| 数组元素的值 | a[i] 的值在变化 |
数组清零 |
| 当前位置坐标 | x, y 坐标 |
迷宫行走 |
| 当前方向 | dir 方向值 |
螺旋矩阵 |
| 剩余数量 | 剩余糖果数、剩余天数 | 分糖果 |
| 当前数值 | 数字在变换 | 数字游戏、卡拉兹猜想 |
| 累计计数 | 操作次数、步数 | 所有模拟题 |
| 当前日期/时间 | 年、月、日 | 日期推算 |
3. 更新规则的确定
更新规则就是“每一步按什么顺序做什么”。关键原则：
- 步骤不能少：题目描述三步，代码就必须写三步。
- 顺序不能乱：先找最大还是先找最小，顺序不同结果不同。
- 条件不能漏：多个最大值时选下标最大的、多个最小值时取第一个，这些细节必须实现。
4. 终止条件的确定
| 终止条件类型 | 示例 |
|---|---|
| 状态达到目标 | 数组全为0、数字变为1、日期到达目标 |
| 步数用完 | 操作次数达到上限 |
| 无法继续 | 找不到满足条件的元素 |
5. 通用模板
// 1. 读入初始状态
// 2. while (未达到终止条件) {
// a. 检查终止条件，满足则退出
// b. 按题目规则，逐步更新状态
// c. 记录操作次数/输出中间结果
// }
// 3. 输出最终结果
三、真题精讲
真题1：数组清零
题目描述：
小A有一个由n个非负整数构成的数组。重复进行以下操作，直到数组只包含0：
- 找到最大的整数，记其下标为k。如果有多个最大值，选择下标最大的。
- 从所有不为零的整数中找到最小的整数。
- 将第一步找到的数减去第二步找到的数。
求需要多少次操作才能使得数组全部变成0。
示例：[2, 3, 4] 需要 7 次操作变成 [0, 0, 0]。
解题思路：
这道题是典型的模拟法——规则非常明确，只需要把三个步骤翻译成代码，循环执行直到数组全为0。
关键细节：
| 细节 | 说明 |
|---|---|
a[i] >= a[maxIdx] |
用 >= 而非 >，保证多个最大值时取下标最大的 |
a[i] > 0 条件 |
只在非零元素中找最大/最小 |
allZero 检查 |
每次循环开始前检查，全0则退出 |
| 数据规模 | n≤100，aᵢ≤100，模拟次数有限，不会超时 |
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a[105];
for (int i = 0; i < n; i++) cin >> a[i];
int ops = 0;
while (true) {
// 检查是否全部为0
bool allZero = true;
for (int i = 0; i < n; i++) {
if (a[i] != 0) { allZero = false; break; }
}
if (allZero) break;
// 步骤1：找最大元素，多个取下标最大的
int maxIdx = -1;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
if (maxIdx == -1 || a[i] >= a[maxIdx]) {
maxIdx = i; // 注意用 >= 取下标最大的
}
}
}
// 步骤2：找最小非零元素
int minVal = 1000000000;
for (int i = 0; i < n; i++) {
if (a[i] > 0 && a[i] < minVal) {
minVal = a[i];
}
}
// 步骤3：最大值减去最小值
a[maxIdx] -= minVal;
ops++;
}
cout << ops << endl;
return 0;
}
优化技巧：可以用 sum 记录数组元素总和，每次操作减去 minVal，当 sum == 0 时终止，省去每次遍历检查全零。
真题2：小洛的数字游戏
题目描述：
小洛有一个正整数n，他会进行若干次下列操作：
- 取出n的末位，记作x。
- 将x²之后，保留个位，放于n的首位之前（如果是0，则不保留前导0）。
上述两步合计为一次操作。例如，正整数142经过一次操作变为414，经过两次操作变为641。现在小洛想知道，对于一个正整数n，能否进行不超过q次操作让其变为正整数m。如果能，输出每次操作后的n值；否则输出-1。
解题思路：
这是典型的数字变换模拟，状态变量是当前的数字n，每一步需要拆位、平方、拼接到首位。
#include <iostream>
using namespace std;
int main() {
long long n, m;
int q;
cin >> n >> m >> q;
for (int i = 1; i <= q; i++) {
int x = n % 10; // 取末位
n /= 10; // 去掉末位
int sq = (x * x) % 10; // 平方后保留个位
// 将 sq 放到 n 的首位之前
if (sq != 0) {
// 计算 n 的位数
long long t = n, base = 1;
while (t > 0) { base *= 10; t /= 10; }
n = sq * base + n;
}
// 如果 sq == 0，数字不保留前导0，相当于只去掉了末位
cout << n << endl;
if (n == m) return 0;
}
cout << -1 << endl;
return 0;
}
关键细节：
| 细节 | 说明 |
|---|---|
n % 10 取末位 |
从右往左取 |
n / 10 去末位 |
缩短数字 |
(x * x) % 10 |
平方后只保留个位 |
sq != 0 判断 |
如果平方个位是0，不保留前导0 |
| 计算位数 | 用循环或 to_string(n).size() |
| 每次输出 | 题目要求输出每次操作后的n值 |
易错点：当 n 变为一位数时，n / 10 得到0，后续操作需要正确处理。例如 n=5，取末位5，n变为0，平方个位5，sq * base + n 中 base 的计算需要特判。
真题3：分糖果
有n个小朋友围成一圈分糖果。老师给每个小朋友一定数量的糖果，然后按照规则传递：每个小朋友同时将自己糖果的一半分给右边的小朋友（如果是奇数，先吃掉一颗变成偶数）。重复直到所有小朋友糖果数相同。求经过多少轮后糖果数相同，以及最终每人有多少颗。
解题思路：
状态变量是每个小朋友的糖果数数组，每轮需要同时更新所有位置（先计算每个人的一半，再更新）。
// 核心逻辑
while (true) {
// 检查是否全部相等
bool same = true;
for (int i = 1; i < n; i++) {
if (a[i] != a[0]) { same = false; break; }
}
if (same) break;
// 计算每人分出的糖果
int give[105];
for (int i = 0; i < n; i++) {
if (a[i] % 2 == 1) {
a[i]--; // 奇数先吃掉一颗
// 记录被吃掉的糖果（可选）
}
give[i] = a[i] / 2;
}
// 同时更新（注意用临时数组）
for (int i = 0; i < n; i++) {
a[i] = a[i] - give[i] + give[(i - 1 + n) % n];
}
rounds++;
}
关键细节：
- “同时”传递：必须先用临时数组记录每个人给出的糖果，再统一更新。
- 环形处理：右边用
(i + 1) % n，左边用(i - 1 + n) % n。 - 奇数处理：奇数先减1变成偶数，再分一半。
四、模拟法的常见题型
1. 数组操作模拟
按照规则反复操作数组，直到满足终止条件。典型题目：数组清零、分糖果、均分纸牌。
核心：状态变量是数组元素，每轮更新数组。
2. 数字变换模拟
按照规则对数字进行变换。典型题目：数字游戏、卡拉兹猜想。
核心：状态变量是当前数字，每步根据规则计算新数字。
3. 日期时间模拟
按照天数推进日期，处理闰年、月份天数等。典型题目：日历制作、日期推算。
核心：状态变量是年、月、日，每步推进一天，处理月末/年末进位。
4. 字符串处理模拟
按照规则对字符串进行操作。典型题目：字符串分割、密码合规检测。
核心：状态变量是字符串内容或位置，每步按规则修改。
5. 游戏/过程模拟
模拟一个游戏过程或物理过程。典型题目：棋子移动、排队叫号。
核心：状态变量是位置、方向、剩余步数等，每步更新。
五、易错点与边界处理
1. 模拟法高频失分点
| 失分点 | 原因 | 正确做法 |
|---|---|---|
| 步骤遗漏 | 题目描述三步，代码只写了两步 | 把题目步骤逐条列在注释里，逐条对照 |
| 顺序错误 | 先找最大还是先找最小搞反了 | 按题目描述的顺序执行 |
| 边界条件遗漏 | 多个最大值时选下标最大的 | 用 >= 而非 > |
| 变量更新错误 | 同时更新时用了旧值 | 用临时数组先保存旧值 |
| 终止条件错误 | 死循环或提前退出 | 每轮开始前检查终止条件 |
| 整数溢出 | 数字变换后超出 int 范围 |
用 long long |
2. “3组边界自测”规则
每写完一道模拟题，必须自行设计3组边界测试数据：
- 第1组：
n = 1（最小规模，验证基本逻辑） - 第2组：全0 / 全相同值（特殊输入，验证终止条件）
- 第3组：全最大值（验证是否会溢出、是否会超时）
3. 调试技巧
在循环内插入输出语句，观察每一步的变量变化：
while (未终止) {
cout << "step " << ops << ": ";
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
// ... 执行操作
}
用小数据手动模拟，和程序输出对照。
六、速查表
| 需求 | 写法 | 关键注意 |
|---|---|---|
| 模拟法框架 | while (未终止) { 检查终止; 按规则更新; ops++; } |
步骤不能少、顺序不能乱 |
| 数组清零 | 找最大、找最小、相减、计数 | 多个最大值取下标最大的 |
| 数字变换 | 拆位、变换、拼接 | 注意位数计算和前导0 |
| 日期模拟 | 加一天、处理月末/年末 | 闰年判断、月份天数 |
| 分糖果 | 同时传递，环形处理 | 用临时数组保存旧值 |
| 终止条件 | 全0、全部相等、达到目标值 | 每轮开始前检查 |
| 调试 | 打印每步状态 | 小数据手动验证 |
七、总结
模拟法是GESP三级从语法迈向算法的核心考点。
- 模拟法的核心是“忠实复现题目描述的规则”，不遗漏、不改变、不提前退出。
- 三要素：识别状态变量、确定更新规则、确定终止条件。
- 状态变量是“什么在变”，更新规则是“怎么变”。
- 题目描述三步，代码就必须写三步，顺序不能乱。
- “同时更新”的场景必须用临时数组先保存旧值。
- 每轮循环开始前检查终止条件，避免死循环。
- 边界条件要写进代码：多个最大值取下标最大的、多个最小值取第一个。
- 大数变换用
long long，防止溢出。 - 每道题写完做“3组边界自测”：n=1、全0、全最大值。
- 多练“数组清零”“数字游戏”“分糖果”三类真题，体会不同状态变量的处理方式。
复习建议：理解模拟法的三步框架；再练“数字游戏”和“分糖果”，体会数字变换和同时更新的处理方式；最后尝试日期模拟和字符串模拟类题目。每道题写完必须用边界数据手动验证，确保终止条件和细节处理无误。考试中先读懂题目规则，列出所有状态变量和更新步骤，再写循环结构，最后逐行检查边界和输出格式。