GESP 三级 第 08 讲:模拟算法与算法描述

本讲定位:三级最后一讲,也是官方知识块 4「算法与描述」的另一半。上一讲的枚举还有”缩小范围”这类技巧可讲,模拟法连技巧都没有——它的全部内容就是”题目说什么,代码就做什么”。正因为没有技巧,模拟题考的是最朴素的两样东西:读题的细致度和写代码的条理性。官方在同一个知识块里还点名了三种「算法描述」方式——自然语言、流程图、伪代码——这是客观题的固定考点,本讲后半部分专门讲。三级到此结束。

对应官方大纲:三级知识块 4「算法与描述」——模拟法;自然语言描述、流程图描述、伪代码描述。

前置知识:二级第 03 讲(流程图——本讲第 7 节直接接续它)、二级第 06、07 讲(嵌套分支与嵌套循环)、三级第 04、05 讲(数组)、三级第 06 讲(字符串)、三级第 07 讲(枚举——模拟常与枚举混合出现)。

代码说明:本讲所有代码均已用 g++ 11.5(-std=c++11)编译运行验证,输出结果即为文中标注结果。


1. 先看两道真题

第一道(单选):

下列关于算法描述方式的说法,错误的是( ) A. 自然语言描述通俗易懂,但可能存在歧义 B. 流程图用图形符号描述算法,直观清晰 C. 伪代码介于自然语言和程序语言之间,不能直接编译运行 D. 同一个算法只能用一种方式描述

第二道(编程题,经典):

约瑟夫问题:$n$ 个人围成一圈,从第 1 个人开始报数,报到 $m$ 的人出圈,然后从下一个人重新从 1 开始报数。求出圈的顺序。

答案:第一道选 D。

同一个算法当然可以用三种方式分别描述——它们只是”说给谁听”不同:自然语言说给人听、伪代码说给会编程的人听、流程图画给所有人看。A、B、C 三项都是标准表述,要背下来。

第二道题是模拟法的教科书例题。 它没有任何数学技巧,就是老老实实地”数一个、圈一个”——但要处理”围成一圈”(转回开头)和”已出圈的人要跳过”这两件事,代码的条理性在这里见真章。


2. 模拟是什么:让程序演一遍

模拟(模拟法):按照题目描述的过程或规则,一步一步地在程序里重现它,直接得出答案。

模拟和枚举的区别:

枚举 模拟
思路 猜答案,然后验证 走过程,走完就是答案
典型形态 for 遍历所有候选 + if 检验 while 一步步推进状态
难点 范围要不重不漏 规则要一条不落
失分原因 边界漏了、范围错了 题目某句话没实现

📌 模拟题的特征很好认:题面很长,规则一条一条列出来,但没有任何需要”想”的地方。看到这种题就该高兴——只要把题读全,分就是你的。

⚠️ 模拟题的唯一敌人是”漏读”。一句”如果不足则不再移动”、一个”从下一个人开始”,漏掉就全错。模拟题的正确率和读题时间成正比。

2.1 模拟题的四条纪律

$$ \boxed{\textbf{① 把规则逐条抄下来} \to \textbf{② 想清楚"状态"是什么} \to \textbf{③ 一步只做一件事} \to \textbf{④ 手工模拟前三步验证}} $$

纪律 具体做法
① 抄规则 在草稿纸上把题目的规则编号列出,写完代码后逐条打勾
② 定状态 问自己:“要描述当前局面,需要哪几个变量?” 这些变量就是状态
③ 一步一件事 每轮循环只推进一步,不要在一轮里塞两个动作
④ 手工验证 拿样例手工走前 3 步,和程序的输出逐个对比

💡 纪律 ④ 是模拟题的救命稻草。模拟题一旦写错,从输出上完全看不出错在哪;但只要手工走前三步,错的那一步立刻现形。这一条要求学生每道模拟题都做,不许跳过。