GESP 三级 第 07 讲：枚举算法

本讲定位：三级第一个真正意义上的”算法”。前六讲教的是工具（进制、编码、位运算、数组、字符串），本讲教的是用工具解决问题的思路。官方大纲三级知识块 4 只列了两种算法——枚举法和模拟法——枚举是其中更”讲得清道理”的那一个。好消息是：枚举是所有算法里最笨也最可靠的一个，思路只有一句话”把所有可能都试一遍”；坏消息是：枚举题的失分几乎全部来自边界和范围，而不是来自不会写循环。本讲的重点是”怎么确定枚举范围”和”怎么保证不重不漏”。

对应官方大纲：三级知识块 4「算法与描述」——枚举法（与第 08 讲的模拟法并列）。

前置知识：一级第 05 讲（整除与求余）、一级第 08 讲（循环）、二级第 07 讲（多重循环）、二级第 08 讲（sqrt）、三级第 04、05 讲（数组与套路——枚举的载体几乎都是数组）、三级第 06 讲（字符串）。

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

1. 先看两道真题

第一道（单选）：

用枚举法求出 100 以内所有的”水仙花数”（各位数字的立方和等于该数本身的三位数），下列枚举范围最合适的是（　） A. 1 到 100　B. 100 到 999　C. 1 到 999　D. 0 到 1000

第二道（编程题，经典）：

百钱买百鸡：公鸡 5 元一只，母鸡 3 元一只，小鸡 1 元三只。用 100 元买 100 只鸡，问公鸡、母鸡、小鸡各买几只？输出所有方案。

答案：第一道选 B。

水仙花数按定义就是三位数，所以范围是 100 到 999。选 A 根本找不到（100 以内没有三位数）；选 C、D 虽然能找到答案，但多枚举了几百个必然不成立的数——“范围不出错，但也不该白跑”是枚举题的基本功。

第二道题是枚举的教科书例题，它的看点不是”能不能做出来”，而是”要枚举几层”：三个未知数看起来要三层循环（$100^3 = 10^6$，也不算慢），但用”总数 100”这个条件能省掉一整层——这就是本讲第 6 节要讲的优化。

2. 枚举是什么：三步法

枚举（穷举）：把所有可能的答案一个一个列出来，逐个检验，符合条件的就是答案。

枚举的三步法：

$$ \boxed{\textbf{① 确定范围} \ \longrightarrow\ \textbf{② 逐个尝试（循环）}\ \longrightarrow\ \textbf{③ 检验条件（if）}} $$

对应到代码，就是一个循环套一个 if：

for (可能的取值 x = 下界; x <= 上界; x++) {     // ① + ②
    if (x 满足条件) {                          // ③
        // 找到了！
    }
}

📌 枚举的最大优点是”一定对”。只要范围没漏、条件没写错，枚举的答案是保证正确的，不需要任何数学推导。

它的唯一缺点是慢。 所以枚举的所有技巧都围绕一件事：在保证不漏的前提下，让范围尽量小。

2.1 枚举的四个要素（做题时逐条问自己）

💡 这张表要变成学生做枚举题的固定动作。四问答完，代码基本就写出来了。 尤其第 ② 和第 ④ 问——枚举题的失分几乎全在这两处。