第 30 章 算法思维入门——暴力枚举
🏗️ 前情回顾：第 15 章你综合运用了分支和循环，其中"水仙花数"那道题用
for从 100 试到 999。这种方法有个学名——枚举。它看起来笨，却是算法世界的基石。这一章我们正式入门"算法思维"，从最朴素的枚举策略开始。
🎯 本章目标
学完这一章，你能：
- 说出枚举的核心思想："逐个尝试所有可能"
- 用循环实现单重和多重枚举
- 用"缩小范围"的方法优化枚举效率
- 独立解决百钱买百鸡、勾股数、方程整数解等经典枚举题
- 建立起"拿到题先想能不能枚举"的条件反射
- 估算枚举的大概次数，判断是否超时
📖 故事引入
小明忘了自行车密码锁的三位数密码。他有两个选择：
方案 A：坐在那里苦思冥想，"我那天设密码的时候在想什么来着……"——想了半小时，没想起来。
方案 B：从 000 开始一个个试，001、002、003……一只手转密码轮，另一只手拽锁，几秒试一个。十分钟后，在 247 处锁"咔嗒"开了。
方案 B 没有任何技巧，就是把所有可能的情况逐个试一遍。这就是枚举。
小明的爸爸是程序员，听说这事后说："你用十分钟试了 248 次，平均每秒试不到一个。要是写成程序，一秒能试一亿次——所有 1000 种可能瞬间试完，密码当场出来。"
枚举在人的世界里显得笨拙，但在计算机的世界里——它是最可靠的武器。因为计算机不会累、不会漏、不会烦。你只需要告诉它"怎么试"，它会用你想象不到的速度把所有可能扫一遍。
🧱 知识讲解
30.1 什么是枚举
枚举（Enumeration）：列出所有可能的情况，逐一检查是否满足条件。
一个枚举程序只有三个要素：
循环生成候选 → 检查是否符合条件 → 符合就记录/输出比如"找出 1~100 中的所有偶数"：
for (int i = 1; i <= 100; i++) { // 循环生成所有候选
if (i % 2 == 0) { // 检查条件
cout << i << " "; // 符合就输出
}
}三步走，清晰得像说明书。这就是枚举的魅力——你不需要灵光一现的巧思，只需要踏实列出来。
30.2 枚举的天敌：次数爆炸
枚举虽好，但不能无脑用。3 位密码锁才 1000 种组合，但 8 位密码锁有 1 亿种——虽然电脑也能试完，但在竞赛里，每道题有严格的时间限制（通常 1 秒）。
一个简单的估算准则：
| 枚举次数 | 大约耗时 | 是否可行 |
|---|---|---|
| 1 万 | 瞬间 | ✅ |
| 10 万 | 瞬间 | ✅ |
| 100 万 | ~0.01 秒 | ✅ |
| 1000 万 | ~0.1 秒 | ✅ |
| 1 亿 | ~1 秒 | ⚠️ 看情况 |
| 10 亿+ | >10 秒 | ❌ 太慢 |
经验法则：单重循环（10⁶ 级别）随便枚举；双重循环（10⁶ × 10³ = 10⁹）就要小心；三重循环（10³ × 10³ × 10³ = 10⁹）几乎必超时。
所以枚举的关键不是"会不会枚举"，而是**"能不能缩小枚举范围"**。
30.3 经典题①：百钱买百鸡
题目（源自中国古代数学）：公鸡一只 5 文钱，母鸡一只 3 文钱，小鸡三只 1 文钱。现在有 100 文钱，要买 100 只鸡，问公鸡、母鸡、小鸡各几只？
暴力版（三重循环）：
for (int gong = 0; gong <= 100; gong++) {
for (int mu = 0; mu <= 100; mu++) {
for (int xiao = 0; xiao <= 100; xiao++) {
if (gong + mu + xiao == 100 && // 100 只
5 * gong + 3 * mu + xiao / 3 == 100 && // 100 文
xiao % 3 == 0) { // 小鸡必须 3 的倍数
cout << "公鸡 " << gong << " 母鸡 " << mu << " 小鸡 " << xiao << endl;
}
}
}
}这个版本次数：101 × 101 × 101 ≈ 103 万次——能跑，但太浪费。
优化版（缩小范围）：
公鸡最贵，最多买 100/5 = 20 只。母鸡最多 100/3 ≈ 33 只。而且——前两种确定了，小鸡数自动由总数 100 推出来，不用再枚举！
for (int gong = 0; gong <= 20; gong++) {
for (int mu = 0; mu <= 33; mu++) {
int xiao = 100 - gong - mu; // 小鸡数直接算出！
if (xiao >= 0 && xiao % 3 == 0 &&
5 * gong + 3 * mu + xiao / 3 == 100) {
cout << "公鸡 " << gong << " 母鸡 " << mu << " 小鸡 " << xiao << endl;
}
}
}优化后：21 × 34 = 714 次。从 103 万降到 714——缩小了 1400 倍！
🎯 枚举优化的核心心法：能用已知条件直接推导出来的变量，就不要枚举它。
30.4 经典题②：勾股数
题目：找出 100 以内所有勾股数（a² + b² = c²，且 a < b < c）。
暴力：三重循环 a、b、c 从 1 到 100 → 100³ = 100 万次，还行。
优化：c 由 a 和 b 决定（c = √(a²+b²)），不需要枚举 c！而且 c ≤ 100。
for (int a = 1; a <= 100; a++) {
for (int b = a + 1; b <= 100; b++) { // b > a
int c2 = a * a + b * b;
int c = (int)(sqrt(c2) + 0.5); // 开方取整（加 0.5 防浮点误差）
if (c <= 100 && c * c == c2) { // 验证是否完全平方数
cout << a << " " << b << " " << c << endl;
}
}
}次数：约 100 × 100 = 1 万次。从 100 万降到 1 万，又快 100 倍。
30.5 经典题③：水仙花数（重温）
既然在学枚举，我们用枚举的眼光重看水仙花数：
// 枚举所有三位数（范围天然确定：100~999）
for (int n = 100; n <= 999; n++) {
int a = n / 100; // 百位
int b = n / 10 % 10; // 十位
int c = n % 10; // 个位
if (a*a*a + b*b*b + c*c*c == n) {
cout << n << endl;
}
}为什么不需要三重循环分别枚举百位、十位、个位？因为三位数天然就是连续的——
for (n = 100; n <= 999; n++)一行就够了。能一行枚举的，不拆成多层。
30.6 经典题④：方程整数解
题目：求方程 3x + 5y = 100 的所有自然数解（x, y ≥ 0）。
思路：x 从 0 到 100/3 ≈ 33，计算 y = (100 - 3x) / 5，判断是否是整数。
for (int x = 0; x <= 33; x++) {
int rest = 100 - 3 * x;
if (rest % 5 == 0) { // y 必须是整数
int y = rest / 5;
cout << "x = " << x << ", y = " << y << endl;
}
}一次循环 34 次，瞬间完成。枚举的魅力就在于——思路简单到不需要任何技巧，但靠计算机的速度硬算出来。
✋ 动手试试
试试 1：把百钱百鸡的三重循环版本敲进 IDE，运行。再敲优化版，对比感觉——714 次和 103 万次在感觉上其实一样快（都在毫秒级）。这说明：百万级别的枚举在现代计算机上完全不是问题。
试试 2：修改勾股数程序，找出 a+b+c=1000 的唯一一组勾股数（提示：a < b < c，且 c 不用枚举）。
试试 3：写程序找出 1~10000 之间的所有"自幂数"（各位数字的 n 次方之和等于自身，n 是位数）。
⚠️ 容易犯的错
错 1：枚举范围没算对
❌ for (int i = 100; i < 1000; i++) — 漏了 999 ✅ for (int i = 100; i <= 999; i++) — 包含 999
错 2：可以推导的量还在循环
❌ 三重循环分别枚举 a、b、c，实际上 a+b+c=100 时 c 自动确定 ✅ 变量之间有等式约束时，循环数 = 变量数 - 约束数
错 3：浮点比较用 ==
❌ sqrt(c2) 是浮点数，直接 == 可能因精度失败 ✅ 改成 int c = (int)(sqrt(c2) + 0.5); if (c * c == c2)
错 4：小鸡数忘了整数约束
❌ 百钱百鸡中直接用 xiao / 3，不检查 xiao % 3 == 0 ✅ 先判断 xiao % 3 == 0 再计算金额。这个条件写反了会导致整数除法静默出错。
📝 练习
基础题
1. 选择题：枚举 0~999 的所有三位密码，需要试多少次？ A. 100 B. 999 C. 1000 D. 900
2. 填空题：枚举优化的核心思路是 ____ 枚举范围，或者说 ____ 不需要枚举的变量。
3. 读代码：以下代码的作用是？
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= i; j++) {
cout << j << "×" << i << "=" << i*j << "\t";
}
cout << endl;
}提高题
4. 编程题 — 换硬币
用 1 元、2 元、5 元的硬币凑出 20 元，有多少种不同的凑法？输出所有组合。
5. 编程题 — 回文平方数
找出 1~10000 中所有满足"自己是回文数，且自己的平方也是回文数"的数。如 1²=1, 2²=4, 3²=9, 11²=121。提示：用循环翻转数字判断回文。
挑战题
6. 编程题 — 马驮瓦
100 匹马驮 100 块瓦。大马每匹驮 3 块，中马每匹驮 2 块，两匹小马合驮 1 块。问大、中、小马各几匹？列出所有解。
7. 编程题 — 四平方和定理
任意正整数可以表示为最多四个整数的平方和。输入 n（1 ≤ n ≤ 10000），输出四个不超过 √n 的整数 a、b、c、d，使 a²+b²+c²+d² = n。如有多个解，输出 a 最小的；如仍有多个，输出 b 最小的，以此类推。提示：枚举前三个，d 自动得出。
🧠 本章小结
枚举算法 —— 逐个尝试，暴力出奇迹：
【三步模板】
for 生成候选 → if 检查条件 → 符合就输出
【优化三法】
① 缩范围 — 根据题目约束缩小循环起止
② 减变量 — 能用等式推导的变量不枚举
③ 早退出 — 找到答案立刻 break（搜索类问题）
【经典题】
百钱百鸡 → 三重→两重（xiao 自动算出）
勾股数 → 三重→两重（c = √(a²+b²)）
水仙花数 → 单重（直接枚举 100~999）
方程整数解 → y = (100-3x)/5，判整除
【复杂度估算】
10⁶ 次 → 放心枚举 | 10⁸ 次 → 小心 | 10⁹+ → 换方法📝 配套练习
共9题。枚举从单重→多重→构造→剪枝→全排列，每道题练一种优化策略。。★核心（课堂必做） ◆拓展（课后练习）
| 级别 | 题号 | 链接 | 覆盖知识点 |
|---|---|---|---|
| ★ 核心 | luogu-P1008 | https://hydro.ac/p/luogu-P1008 | 循环枚举、范围缩小、减变量 |
| ◆ 拓展 | luogu-P1618 | https://hydro.ac/p/luogu-P1618 | 枚举+比例、动态范围 |
| ◆ 拓展 | luogu-P1149 | https://hydro.ac/p/luogu-P1149 | 枚举+预处理、火柴棒 |
| ◆ 拓展 | luogu-P1217 | https://hydro.ac/p/luogu-P1217 | 枚举构造、回文+质数、剪枝 |
| ◆ 拓展 | luogu-P1036 | https://hydro.ac/p/luogu-P1036 | 组合枚举、选数求和、质数判 |
| ◆ 拓展 | luogu-P1706 | https://hydro.ac/p/luogu-P1706 | next_permutation、全排列 |
| ◆ 拓展 | luogu-P2241 | https://hydro.ac/p/luogu-P2241 | 枚举、正方形+长方形计数 |
| ◆ 拓展 | luogu-P2089 | https://hydro.ac/p/luogu-P2089 | 多重枚举、烧烤配料 |
| ◆ 拓展 | CSPJ2019A | https://hydro.ac/p/ccf-CSPJ2019A | 枚举、计数、01串 |
💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 8 道◆拓展题，覆盖不同变式和细节。
配套练习
共9题。枚举从单重→多重→构造→剪枝→全排列，每道题练一种优化策略。★核心（课堂必做） · ◆拓展（课后练习）
| 级别 | 题号 | 链接 | 覆盖知识点 |
|---|---|---|---|
| ★ 核心 | luogu-P1008 | https://hydro.ac/p/luogu-P1008 | 循环枚举、范围缩小、减变量 |
| ◆ 拓展 | luogu-P1618 | https://hydro.ac/p/luogu-P1618 | 枚举+比例、动态范围 |
| ◆ 拓展 | luogu-P1149 | https://hydro.ac/p/luogu-P1149 | 枚举+预处理、火柴棒 |
| ◆ 拓展 | luogu-P1217 | https://hydro.ac/p/luogu-P1217 | 枚举构造、回文+质数、剪枝 |
| ◆ 拓展 | luogu-P1036 | https://hydro.ac/p/luogu-P1036 | 组合枚举、选数求和、质数判 |
| ◆ 拓展 | luogu-P1706 | https://hydro.ac/p/luogu-P1706 | next_permutation、全排列 |
| ◆ 拓展 | luogu-P2241 | https://hydro.ac/p/luogu-P2241 | 枚举、正方形+长方形计数 |
| ◆ 拓展 | luogu-P2089 | https://hydro.ac/p/luogu-P2089 | 多重枚举、烧烤配料 |
| ◆ 拓展 | CSPJ2019A | https://hydro.ac/p/ccf-CSPJ2019A | 枚举、计数、01串 |
练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 8 道◆拓展题，覆盖不同变式和细节。
自查清单：
- [ ] 我能说出枚举的核心思想
- [ ] 我会用"缩小范围"优化枚举
- [ ] 我能独立写出百钱百鸡的优化版
- [ ] 我知道三重循环什么时候会超时
- [ ] 我拿到新题会先想"能不能枚举"
- [ ] 我知道"能推导的变量不枚举"
🚀 下章预告
枚举是"把所有情况列出来"，但有些问题——比如"石头剪刀布，赢 3 局才算胜"——它的过程是一步步走的，每一步的结果影响下一步。这种题目不能简单枚举所有情况，而是要让程序模拟真实过程，一步步执行规则。
下一章，我们学习算法中最接地气的技巧——模拟。模拟题是竞赛的"送分大户"，只要读对题、写对步骤，分就是你的。