第26章 枚举算法
| 等级 | 知识块 | 考查频率 |
|---|---|---|
| GESP C++ 三级 | 枚举法（原理、特点、实际问题） | ⭐⭐⭐ |
枚举（穷举）算法：遍历问题所有合法候选解，逐个校验条件，筛选出符合要求的答案。它不要求复杂数学推导，靠计算机高速循环穷举，逻辑简单，适合解空间较小的题目——是三级最基础、最常考的算法思想。
26.1 枚举核心思想与执行步骤
核心思想
不做复杂推导，把所有可能的解全部列举，逐一判断是否满足条件，保留有效解。
标准步骤
- 确定解的范围：依题意划定上下限，缩小循环区间；
- 设定判断条件：写出满足答案的逻辑表达式；
- 循环枚举所有候选：按顺序遍历每个可能值；
- 校验并收集结果：符合条件则输出/保存。
26.2 枚举优缺点
优点
- 逻辑直观，极易编写，新手友好；
- 范围无遗漏就一定能找出全部解；
- 适用广，数字、组合类基础题都能用。
缺点
- 数据范围很大时循环次数爆炸、运行慢；
- 多层嵌套枚举时间开销大。
枚举的本质是「以时间换正确」。如果范围到 ，盲目枚举必然超时。先缩小边界（用不等式估计），必要时换数学/二分等算法。三级题数据范围通常有意设计得适合枚举。
26.3 经典代码示例
示例1：输出 1~100 所有素数
#include <iostream>
#include <cmath>
using namespace std;
int main() {
for (int num = 1; num <= 100; num++) {
int isPrime = 1;
if (num <= 1) isPrime = 0;
else {
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) { isPrime = 0; break; }
}
}
if (isPrime) cout << num << " ";
}
return 0;
}
示例2：百钱百鸡问题
题意：鸡翁五钱一只，鸡母三钱一只，鸡雏三只是一钱，百钱买百鸡，求所有组合。
#include <iostream>
using namespace std;
int main() {
for (int x = 0; x <= 20; x++) { // 鸡翁最多 20 只
for (int y = 0; y <= 33; y++) { // 鸡母最多 33 只
int z = 100 - x - y;
if (z % 3 == 0 && 5 * x + 3 * y + z / 3 == 100) {
cout << "鸡翁:" << x << " 鸡母:" << y << " 鸡雏:" << z << endl;
}
}
}
return 0;
}
示例3：1~50 中同时被 3、5 整除的数
#include <iostream>
using namespace std;
int main() {
for (int i = 1; i <= 50; i++) {
if (i % 3 == 0 && i % 5 == 0) cout << i << " "; // 15 30 45
}
return 0;
}
示例4：水仙花数（三位数，各位立方和等于自身）
#include <iostream>
using namespace std;
int main() {
for (int num = 100; num <= 999; num++) {
int h = num / 100;
int t = (num / 10) % 10;
int u = num % 10;
if (h * h * h + t * t * t + u * u == num) cout << num << " ";
}
return 0;
}
- 缩小边界：把取值范围小的变量放外层（如百钱百鸡里鸡翁最多 20，比鸡雏少，放外层）；
- 提前 break：找到唯一解就退出循环；
- 化简判断：循环内少做重复计算（如提前算好常量）。
26.4 枚举优化注意事项
- 精准缩小枚举边界，减少循环次数；
- 多层循环时把取值范围小的变量放外层；
- 简化判断条件，减少循环内计算；
- 找到唯一解时用
break提前终止。
26.5 选择题练习
1. 枚举算法的核心思想是？
A. 用递归分解问题
B. 遍历所有候选解并筛选
C. 每次取局部最优
D. 分而治之
点击展开参考答案与解析
答案：B
解析：枚举就是"遍历全部候选 + 筛选"，选 B。递归、贪心、分治分别是其他算法思想。
2. 百钱百鸡中，设鸡翁 x、鸡母 y、鸡雏 z，约束条件不应包含？
A. x + y + z = 100
B. 5x + 3y + z/3 = 100
C. x ≤ 20
D. x * y * z = 100
点击展开参考答案与解析
答案：D
解析：百钱百鸡的约束是数量和为 100、钱数和为 100、以及 x≤20（钱数上限推导）。x*y*z=100 不是题目约束，选 D。
3. 下列哪种情况不适合用枚举法直接求解？
A. 求 11000 内所有素数10^9 范围找满足条件的单个数
B. 在 1
C. 三位数水仙花数
D. 百钱百鸡
点击展开参考答案与解析
答案：B
解析：范围到 的暴力枚举会严重超时，不适合直接枚举，选 B。其余范围都很小。
4. 关于枚举法的缺点，正确的是？
A. 代码一定很长
B. 范围过大时会超时
C. 无法保证找到所有解
D. 只能用于数字问题
点击展开参考答案与解析
答案：B
解析：枚举最大的缺点是范围过大时循环次数爆炸导致超时，选 B。只要边界无遗漏，枚举一定能找全解（C 错）。
5. 为加快枚举，通常应该？
A. 把取值范围大的变量放最外层
B. 把取值范围小的变量放最外层
C. 不加任何边界
D. 用递归代替循环
点击展开参考答案与解析
答案：B
解析：把取值小的变量放外层，可大幅减少内层循环总次数，选 B。