本讲定位:三级最后一讲,也是官方知识块 4「算法与描述」的另一半。上一讲的枚举还有”缩小范围”这类技巧可讲,模拟法连技巧都没有——它的全部内容就是”题目说什么,代码就做什么”。正因为没有技巧,模拟题考的是最朴素的两样东西:读题的细致度和写代码的条理性。官方在同一个知识块里还点名了三种「算法描述」方式——自然语言、流程图、伪代码——这是客观题的固定考点,本讲后半部分专门讲。三级到此结束。
对应官方大纲:三级知识块 4「算法与描述」——模拟法;自然语言描述、流程图描述、伪代码描述。
前置知识:二级第 03 讲(流程图——本讲第 7 节直接接续它)、二级第 06、07 讲(嵌套分支与嵌套循环)、三级第 04、05 讲(数组)、三级第 06 讲(字符串)、三级第 07 讲(枚举——模拟常与枚举混合出现)。
代码说明:本讲所有代码均已用 g++ 11.5(
-std=c++11)编译运行验证,输出结果即为文中标注结果。
第一道(单选):
下列关于算法描述方式的说法,错误的是( ) A. 自然语言描述通俗易懂,但可能存在歧义 B. 流程图用图形符号描述算法,直观清晰 C. 伪代码介于自然语言和程序语言之间,不能直接编译运行 D. 同一个算法只能用一种方式描述
第二道(编程题,经典):
约瑟夫问题:$n$ 个人围成一圈,从第 1 个人开始报数,报到 $m$ 的人出圈,然后从下一个人重新从 1 开始报数。求出圈的顺序。
答案:第一道选 D。
同一个算法当然可以用三种方式分别描述——它们只是”说给谁听”不同:自然语言说给人听、伪代码说给会编程的人听、流程图画给所有人看。A、B、C 三项都是标准表述,要背下来。
第二道题是模拟法的教科书例题。 它没有任何数学技巧,就是老老实实地”数一个、圈一个”——但要处理”围成一圈”(转回开头)和”已出圈的人要跳过”这两件事,代码的条理性在这里见真章。
模拟(模拟法):按照题目描述的过程或规则,一步一步地在程序里重现它,直接得出答案。
模拟和枚举的区别:
| 枚举 | 模拟 | |
|---|---|---|
| 思路 | 猜答案,然后验证 | 走过程,走完就是答案 |
| 典型形态 | for 遍历所有候选 + if 检验 |
while 一步步推进状态 |
| 难点 | 范围要不重不漏 | 规则要一条不落 |
| 失分原因 | 边界漏了、范围错了 | 题目某句话没实现 |
📌 模拟题的特征很好认:题面很长,规则一条一条列出来,但没有任何需要”想”的地方。看到这种题就该高兴——只要把题读全,分就是你的。
⚠️ 模拟题的唯一敌人是”漏读”。一句”如果不足则不再移动”、一个”从下一个人开始”,漏掉就全错。模拟题的正确率和读题时间成正比。
$$ \boxed{\textbf{① 把规则逐条抄下来} \to \textbf{② 想清楚"状态"是什么} \to \textbf{③ 一步只做一件事} \to \textbf{④ 手工模拟前三步验证}} $$
| 纪律 | 具体做法 |
|---|---|
| ① 抄规则 | 在草稿纸上把题目的规则编号列出,写完代码后逐条打勾 |
| ② 定状态 | 问自己:“要描述当前局面,需要哪几个变量?” 这些变量就是状态 |
| ③ 一步一件事 | 每轮循环只推进一步,不要在一轮里塞两个动作 |
| ④ 手工验证 | 拿样例手工走前 3 步,和程序的输出逐个对比 |
💡 纪律 ④ 是模拟题的救命稻草。模拟题一旦写错,从输出上完全看不出错在哪;但只要手工走前三步,错的那一步立刻现形。这一条要求学生每道模拟题都做,不许跳过。