第二章 · 暴力枚举
第一单元：暴力枚举入门——让计算机替我们一个一个地试！
同学们，欢迎来到算法王国的第二章！
在第一章中，我们学习了一个重要本领：拿到一道题，不能急着敲代码，而是要先分析题目，判断可能使用什么算法。
现在，我们正式认识第一位算法探险家——暴力枚举！
它没有华丽的魔法，也不会一眼看出答案。它的绝招只有一个：
把所有可能的情况有条理地检查一遍，直到找到答案，或者确认哪些答案符合要求。
你可能会觉得：“这不就是一个一个地试吗？”
没错！但在计算机世界里，很多看似简单的“一次次尝试”，只要设计得合理，就能解决非常有趣的问题。
今天，我们就跟随暴力枚举探险家，进入藏宝洞、数字城堡和密码实验室，学习如何把“一次次尝试”变成真正的算法。
本单元包含：
概念理解：暴力枚举到底是什么？
图示推演：如何保证所有可能都没有遗漏？
基础代码：用 C++ 编写枚举程序。
解题模板：遇到新题时，怎样快速搭建代码？
典型例题：从简单数字到数字组合，逐步升级。
第一站：暴力枚举到底是什么？
一、国王的藏宝任务
魔法国王有 10 个宝箱，编号分别是：
1、2、3、4、5、6、7、8、9、10
其中一个宝箱里藏着金钥匙。
国王告诉你：
金钥匙一定在这 10 个宝箱中。
每次只能检查一个宝箱。
检查后，就能知道里面有没有金钥匙。
你应该怎么办？
当然可以从 1 号宝箱开始，一个一个检查：
1 号没有？检查 2 号。
2 号没有？检查 3 号。
继续检查……
找到钥匙后，就可以结束。
这个过程就是暴力枚举的基本思想。
1. 给它一个正式的名字
暴力枚举：按照一定的规则，逐一检查所有可能的候选情况，并根据题目条件找出符合要求的答案。
这里有三个关键词。
关键词一：所有可能
先确定答案可能出现在哪里。例如，宝箱编号是 1 到 10，那么就不能只检查 1 到 5。
关键词二：逐一检查
用循环把候选答案依次拿出来，而不是手工重复劳动。
关键词三：判断条件
每检查一个候选答案，就判断它是否符合题目要求。不符合就继续，符合就记录或输出。
2. 暴力枚举不等于乱试
请比较下面两种做法。
做法 A： 想到哪个宝箱就检查哪个宝箱，检查过的还可能再检查一次。
做法 B： 从 1 号开始，按照 1、2、3……10 的顺序检查，每个宝箱只检查一次。
显然，做法 B 更清楚、更可靠。
所以，我们要记住：
暴力枚举不是没有计划地乱试，而是按照清晰的规则，把候选答案系统地检查一遍。
第二站：暴力枚举的四步探险法
二、每道枚举题，都先问自己四个问题
以后遇到一道可能使用暴力枚举的题目，不要马上写代码。先完成下面四步。
1、确定枚举范围
候选答案有哪些？从哪里开始，到哪里结束？
例如：枚举 1 到 100 的整数。
2、设计枚举方式
一个数字？两个数字？还是三种选择组成的组合？
一个数字通常用一层循环；两个数字的组合通常用两层循环。
3、写出判断条件
什么样的候选答案才是正确答案？
例如：i % 3 == 0表示i能被 3 整除。
4、处理找到的答案
根据题目要求，输出答案、统计数量，或者找到第一个答案后结束。
我们把这四步记成一句话：
定范围、选循环、写条件、处理答案。
这是本章最重要的解题模板之一。
第三站：第一个程序——寻找魔法数字
例题一：找出 1 到 20 中能被 3 整除的数字
题目故事
魔法学院的老师要挑选一批“幸运数字”。
规则很简单：数字必须能够被 3 整除。
请你找出 1 到 20 中所有符合条件的数字。
第一步：确定范围
所有候选数字是：
1、2、3、4、5、……、20
所以：
起点是 1。
终点是 20。
每次增加 1。
第二步：设计循环
我们只检查一个数字，因此使用一层for循环：
for (int i = 1; i <= 20; i++) { // 检查数字 i }这里有三个部分：
int i = 1：从 1 开始。i <= 20：只要没有超过 20，就继续检查。i++：每检查一次，i增加 1。
第三步：写出判断条件
怎样判断一个数能不能被 3 整除？
使用取模运算符%。
i % 3 == 0例如：
数字 | 计算 | 结果 |
|---|---|---|
3 |
| 0，符合 |
4 |
| 1，不符合 |
6 |
| 0，符合 |
8 |
| 2，不符合 |
只要余数为 0，就说明能够整除。
第四步：完整 C++ 程序
#include <iostream> using namespace std; int main() { for (int i = 1; i <= 20; i++) { if (i % 3 == 0) { cout << i << " "; } } cout << endl; return 0; }输出结果：
3 6 9 12 15 18第五步：图示推演
第六步：这道题的复杂度
如果把 20 改成 n ，程序就会从 1 检查到 n ，因此时间复杂度为：
O(n)
这里的 O(n) 可以粗略理解为：数据量扩大几倍，检查次数通常也会扩大几倍。
本题总结： 当每次只需要检查一个候选数字时，一层循环通常就足够了。
第四站：寻找所有答案，还是找到一个就停？
例题二：寻找第一颗魔法星星
题目故事
魔法学院排着 20 颗星星，编号从 1 到 20。
老师说：“请找到第一颗能被 7 整除的星星。找到后就可以回去休息啦！”
请问，程序应该怎样写？
第一步：分析区别
上一道题要求输出所有符合条件的数字。
这道题只要求找到第一个符合条件的数字。
所以，我们可以在找到答案后，立即结束循环。
第二步：参考程序
#include <iostream> using namespace std; int main() { for (int i = 1; i <= 20; i++) { if (i % 7 == 0) { cout << i << endl; break; } } return 0; }输出：
7第三步：break是什么？
break可以让程序立即跳出当前所在的循环。
执行过程如下：
什么时候使用break？
题目只要求找到第一个答案；
已经满足题目要求，没有必要继续枚举；
继续检查不会带来新的必要信息。
但是，如果题目要求统计所有答案，或者输出所有符合条件的数字，就不能随意在第一个答案出现时停止。
小口诀：找一个，可能提前停；找全部，必须继续检查。
第五站：从数字到数字搭档——双层循环登场
例题三：寻找和为 10 的两位骑士
题目故事
数字骑士团有 5 位骑士，他们的号码分别是：
1、3、5、7、9
国王希望找到两位不同的骑士，让他们的号码相加等于 10。
请你找出所有符合条件的组合。
第一步：为什么一层循环不够？
如果只用一个变量i，我们一次只能拿出一个数字。
但是，现在需要同时考虑两个数字：
a[i] + a[j] = 10
所以，我们需要两层循环：
外层循环：选择第一个数字。
内层循环：选择第二个数字。
第二步：先看最简单的双层循环
for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { // 检查 a[i] 和 a[j] } }当i固定时，j会从 0 到 4 全部走一遍。
例如：
但这样有两个问题：
(1,7)和(7,1)会被检查两次。(1,1)这种同一位置和自己配对的情况也会出现。
如果题目规定选择两个不同的骑士，并且不区分先后顺序，我们可以改进循环范围。
第三步：避免重复检查
让第二个下标从i + 1开始：
for (int i = 0; i < 5; i++) { for (int j = i + 1; j < 5; j++) { // 检查 a[i] 和 a[j] } }这样就保证：
i < j
每一组不同位置的组合只检查一次。
第四步：完整程序
#include <iostream> using namespace std; int main() { int a[5] = {1, 3, 5, 7, 9}; int cnt = 0; for (int i = 0; i < 5; i++) { for (int j = i + 1; j < 5; j++) { if (a[i] + a[j] == 10) { cout << a[i] << " " << a[j] << endl; cnt++; } } } cout << "组合数量：" << cnt << endl; return 0; }输出：
1 9 3 7 组合数量：2第五步：复杂度分析
如果数组有 n 个元素，双层循环会检查大约 n^2 级别的候选组合，因此时间复杂度通常是：
O(n^2)
这道题的数据量很小，使用暴力枚举非常合适。
本题总结： 当需要检查两个对象组成的所有组合时，可以考虑双层循环。若组合不区分顺序，通常可以通过j = i + 1避免重复。
第六站：三位数密码——三层循环怎么写？
例题四：寻找神秘的三位数
题目故事
魔法城堡有一个三位数密码锁。
密码必须满足：
是一个三位数；
百位、十位、个位上的数字互不相同；
三个数字的和等于 6。
请输出所有符合条件的密码。
第一步：拆解三位数
假设密码的百位、十位、个位分别是a、b、c。
那么：
密码 = 100a + 10b +c
其中：
百位
a从 1 到 9；十位
b从 0 到 9；个位
c从 0 到 9。
第二步：三个位置，三层循环
for (int a = 1; a <= 9; a++) { for (int b = 0; b <= 9; b++) { for (int c = 0; c <= 9; c++) { // 检查三位数字 } } }可以把它想象成三个转盘：
第一个转盘决定百位；
第二个转盘决定十位；
第三个转盘决定个位。
每确定前面的数字，后面的数字就继续尝试所有可能。
第三步：判断条件
三个数字互不相同：
a != b && a != c && b != c三个数字之和为 6：
a + b + c == 6合并条件：
if (a != b && a != c && b != c && a + b + c == 6)第四步：完整程序
#include <iostream> using namespace std; int main() { for (int a = 1; a <= 9; a++) { for (int b = 0; b <= 9; b++) { for (int c = 0; c <= 9; c++) { if (a != b && a != c && b != c && a + b + c == 6) { cout << 100 * a + 10 * b + c << endl; } } } } return 0; }第五步：还能怎样优化？
因为三个数字的和必须等于 6，所以百位不可能大于 6。
我们可以把外层循环改成：
for (int a = 1; a <= 6; a++)这样可以少检查一些不可能的情况。
这就是枚举的一个进阶技巧：
在保证不漏掉答案的前提下，尽早排除不可能的候选情况。
不过，本题只有 900 种左右的原始候选情况，直接枚举已经足够。初学时应先写出正确的程序，再考虑是否值得优化。
第七站：枚举中的小助手——计数器、累加器与标记
前面的例题中，我们除了检查候选答案，还做了其他工作。
例如：
统计找到了多少个数字；
计算所有符合条件的数字之和；
判断是否至少存在一个符合条件的答案。
这些操作都可以在枚举过程中完成。
例题五：数一数幸运数字
题目
输入一个正整数 n ，统计 1 到 n 中有多少个数字能够被 3 整除。
代码
#include <iostream> using namespace std; int main() { int n; cin >> n; int cnt = 0; for (int i = 1; i <= n; i++) { if (i % 3 == 0) { cnt++; } } cout << cnt << endl; return 0; }输入：
20输出：
6为什么cnt要从 0 开始？
因为刚开始还没有找到任何符合条件的数字，所以数量为 0。
每发现一个符合条件的数字，就执行：
cnt++;它等价于：
cnt = cnt + 1;这类变量叫作计数器。
例题六：计算所有幸运数字的总和
题目
输入一个正整数 n ，求 1 到 n 中所有能被 3 整除的数字之和。
代码
#include <iostream> using namespace std; int main() { int n; cin >> n; int sum = 0; for (int i = 1; i <= n; i++) { if (i % 3 == 0) { sum += i; } } cout << sum << endl; return 0; }输入：
10输出：
18因为符合条件的数字是 3、6、9：
3+6+9=18
这里的sum是累加器，每找到一个符合条件的数字，就把它加到总和里。
计数器和累加器的区别
变量 | 作用 | 常见写法 |
|---|---|---|
| 统计数量 |
|
| 计算总和 |
|
| 记录是否找到答案 |
|
例题七：检查是否存在幸运数字
题目
输入一个正整数 n ，判断 1 到 n 中是否存在能被 7 整除的数字。
#include <iostream> using namespace std; int main() { int n; cin >> n; bool found = false; for (int i = 1; i <= n; i++) { if (i % 7 == 0) { found = true; break; } } if (found) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; }例如输入20，输出YES；输入5，输出NO。
这里的found是一个布尔变量：
false表示还没有找到；true表示已经找到。
找到答案后，使用break结束循环，避免继续做不必要的检查。
第八站：数字侦探——用枚举寻找因数
例题八：城堡的因数守门员
题目故事
魔法城堡的编号是 12。守门员规定：只有能够把 12 平均分成若干份、没有余数的数字，才可以通过大门。
请你找出 12 的所有正因数。
第一步：什么是因数？
如果整数 n 除以整数 i ，余数是 0，那么 i 就是 n 的因数。
例如：
12 / 3 = 4
没有余数，所以 3 是 12 的因数。
而：
12 / 5 = 2 余 2
有余数，所以 5 不是 12 的因数。
第二步：枚举范围
12 的正因数一定在 1 到 12 之间。
所以，枚举：
for (int i = 1; i <= 12; i++)第三步：完整程序
#include <iostream> using namespace std; int main() { int n = 12; for (int i = 1; i <= n; i++) { if (n % i == 0) { cout << i << " "; } } cout << endl; return 0; }输出：
1 2 3 4 6 12第四步：把它变成通用程序
如果城堡编号不是固定的 12，而是由用户输入，就可以这样写：
#include <iostream> using namespace std; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { if (n % i == 0) { cout << i << " "; } } cout << endl; return 0; }输入18，输出：
1 2 3 6 9 18第五步：复杂度分析
最直接的方法需要检查 1 到 n 的所有整数，因此时间复杂度为 O(n) 。
对于小数字，这种方法非常直观。对于很大的数字，我们以后还会学习如何利用因数成对出现的性质，把检查范围缩小到平方根附近。
第九站：暴力枚举的万能代码模板
学了这么多例题，我们要把它们整理成几套可以反复使用的模板。
注意：模板是帮助我们快速开始思考的工具，不是让我们不分析题目就机械套用。
模板一：枚举一个数字
适用于：
筛选符合条件的整数；
查找因数；
统计满足条件的数字；
计算符合条件的数字之和。
for (int i = L; i <= R; i++) { if (满足条件) { // 输出答案、计数或累加 } }这里：
L是枚举起点；R是枚举终点；满足条件要替换成真正的 C++ 判断表达式。
例如，输出 1 到 100 中所有能被 5 整除的数字：
for (int i = 1; i <= 100; i++) { if (i % 5 == 0) { cout << i << " "; } }模板二：枚举两个数字
适用于：
寻找和为指定数值的数字对；
检查两个对象之间的组合；
统计符合条件的两两搭配。
for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (满足条件) { // 处理这组组合 } } }这个版本适合“选择两个不同位置的元素，且不区分顺序”的题目。
如果题目要求考虑顺序，或者允许重复选择，就必须根据题意修改循环范围。
模板三：枚举三个数字
适用于：
三个数字之和；
三个不同位置的元素组成的组合；
三个数字分别代表百位、十位、个位。
for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { if (满足条件) { // 处理这组三元组合 } } } }同样，这个模板只适用于需要检查三个不同位置、并且不区分顺序的组合。其他情况要重新设计范围。
模板四：找到第一个答案就停止
bool found = false; for (int i = L; i <= R; i++) { if (满足条件) { cout << i << endl; found = true; break; } } if (!found) { cout << "没有找到" << endl; }如果题目规定了特殊输出格式，应把“没有找到”替换成题目要求的内容。
模板五：统计符合条件的答案
int cnt = 0; for (int i = L; i <= R; i++) { if (满足条件) { cnt++; } } cout << cnt << endl;模板六：计算符合条件的答案之和
int sum = 0; for (int i = L; i <= R; i++) { if (满足条件) { sum += i; } } cout << sum << endl;这六套模板基本覆盖了初学阶段常见的枚举形式。遇到题目时，先判断它属于哪一类，再根据题目条件进行修改。
第十站：小探险家的综合训练营
前面的例题已经让我们学会了枚举数字、数字对、三位数密码、因数，以及计数和累加。
现在，轮到你自己成为小小算法探险家了！
建议先独立思考，再打开参考解析。每道题都可以按照四步来做：
确定范围 → 设计循环 → 写出条件 → 处理答案。
训练题一：寻找彩虹数字
题目： 输入一个正整数 n ，输出 1 到 n 中 所有能被 4 整除、但不能被 6 整除的数字。
输入：
30输出：
4 8 16 20 28思考：判断条件中为什么需要&&？
参考程序:
#include <iostream> using namespace std; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { if (i % 4 == 0 && i % 6 != 0) { cout << i << " "; } } cout << endl; return 0; }训练题二：神奇的数字搭档
题目： 有一组数字：
2 4 6 8 10
找出所有不同位置的数字对，使它们的和等于 12。每组只输出一次。
参考程序:
#include <iostream> using namespace std; int main() { int a[5] = {2, 4, 6, 8, 10}; for (int i = 0; i < 5; i++) { for (int j = i + 1; j < 5; j++) { if (a[i] + a[j] == 12) { cout << a[i] << " " << a[j] << endl; } } } return 0; }训练题三：神秘三位数
题目： 找出所有满足以下条件的三位数：
百位数字是 1；
三个数字互不相同；
三个数字之和等于 5。
参考程序:
#include <iostream> using namespace std; int main() { for (int b = 0; b <= 9; b++) { for (int c = 0; c <= 9; c++) { if (1 != b && 1 != c && b != c && 1 + b + c == 5) { cout << 100 + 10 * b + c << endl; } } } return 0; }训练题四：寻找完全平方数
题目： 输入正整数 \(n\)，输出所有不超过 \(n\) 的正完全平方数。
例如，输入30，输出：
1 4 9 16 25参考程序:
#include <iostream> using namespace std; int main() { int n; cin >> n; for (int i = 1; i * i <= n; i++) { cout << i * i << " "; } cout << endl; return 0; }十一、本单元知识地图
十二、课后总结：请带走这五句话
暴力枚举不是乱试，而是有顺序地检查所有候选情况。
先确定范围，再决定使用几层循环。
判断条件必须准确，既不能漏掉答案，也不能把错误答案算进去。
找一个答案，可以考虑提前结束；找所有答案，就要继续检查。
写出正确程序之后，还要分析复杂度，判断数据规模是否允许这样枚举。
最后，请记住一句话：
暴力枚举教会我们的，不只是怎样写循环，更是怎样把一个复杂问题拆成许多简单、清楚、能够逐一检查的小问题。
下一课，我们将继续研究暴力枚举：怎样枚举所有组合、排列和子集？当候选方案越来越多时，又该怎样判断程序会不会超时？
