企业官网建设流程全解析

第二章·暴力枚举 第三单元：让暴力枚举跑得更快——少走弯路，聪明搜索！

同学们，上一单元，我们帮助骑士排队、挑选队员，还学会了枚举宝物的所有子集。

但是，新的问题来了！

国王的宝库里有 10 万张数字卡片。如果我们每次都傻乎乎地从头检查到尾，甚至重复检查同一组卡片，程序就可能慢得像一只背着大石头爬山的乌龟。

今天，我们要把“暴力枚举”升级成一位聪明的侦探！

这位侦探有四个绝招：

1. 少检查一些：缩小枚举范围。

2. 不做重复劳动：避免重复枚举。

3. 找到答案就停：不要再做无用功。

4. 不可能的方案，早点放弃：利用条件提前排除。

先记住今天的核心思想：

暴力枚举不一定慢。真正聪明的枚举，是把该检查的检查清楚，把不必检查的尽早跳过！

第一站：绝招一 —— 缩小枚举范围

例题 1：寻找宝箱密码

故事背景

国王的密码是一个 1 到 100 之间的整数，而且国王悄悄告诉我们：

• 密码一定是偶数；

• 密码一定大于 50；

• 密码一定能被 6 整除。

请找出所有符合条件的密码。

第一步：最笨的方法

我们可以从 1 开始，枚举到 100：

for (int i = 1; i <= 100; i++) { if (i % 2 == 0 && i > 50 && i % 6 == 0) { cout << i << endl; } }

这个程序没有错。

但它检查了 1、2、3、4……一直到 100。

明明密码一定大于 50，我们为什么还要检查 1 到 50 呢？

第二步：缩小范围

既然密码一定大于 50，那么直接从 51 开始就可以了。

for (int i = 51; i <= 100; i++) { if (i % 2 == 0 && i % 6 == 0) { cout << i << endl; } }

我们甚至可以继续优化。

如果密码必须是 6 的倍数，那么它一定是：

6、12、18、24、30……

因此，可以直接枚举 6 的倍数，而不是检查每个整数！

#include <iostream> using namespace std; int main() { for (int i = 54; i <= 100; i += 6) { cout << i << endl; } return 0; }

这里为什么从 54 开始？

因为 54 是大于 50 的第一个 6 的倍数。

输出结果：

54 60 66 72 78 84 90 96

这些数字也都是偶数，所以符合全部条件。

算法小结

优化前： 从 1 检查到 100。

优化后： 直接从 54 开始，每次增加 6。

关键技巧： 如果题目已经告诉我们答案必须满足某种规律，就尽量利用这个规律设计循环，而不是盲目检查每个数字。

注意：缩小范围必须有依据，不能为了让程序跑得快，就随意跳过可能的答案。

第二站：绝招二——避免重复枚举

例题 2：寻找和为 10 的数字搭档

宝箱中有 5 张卡片：

1、3、5、7、9

请找出两张不同的卡片，使它们的数字之和等于 10。

我们在上一单元已经写过这样的程序。现在，我们来看看为什么有些写法会做重复劳动。

写法一：重复检查

int a[5] = {1, 3, 5, 7, 9}; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { if (i != j && a[i] + a[j] == 10) { cout << a[i] << " " << a[j] << endl; } } }

程序可能输出：

1 9 9 1 3 7 7 3

发现问题了吗？

1 9和9 1是同一对卡片，只不过交换了位置。

写法二：只检查一次

#include <iostream> using namespace std; int main() { int a[5] = {1, 3, 5, 7, 9}; 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; } } } return 0; }

输出：

1 9 3 7

关键就在这一句：

for (int j = i + 1; j < 5; j++)

当第一张卡片的位置确定后，第二张卡片只从它后面开始选。

这样就能保证：

• 不会选中同一个位置两次；

• 不会把同一对卡片重复检查；

• 不会漏掉任何一对不同位置的卡片。

举例理解

假设有 4 张卡片：A、B、C、D

从 A 出发，检查 B、C、D；从 B 出发，只检查 C、D；从 C 出发，只检查 D。每一对只出现一次。

算法小结

遇到“选两个不同元素，且不考虑顺序”的问题，可以优先想到：

for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // 检查一对元素 } }

不过要特别注意：如果题目要求统计的是有序数对，例如(1, 9)和(9, 1)算两种，那么就不能这样去重。

第三站：绝招三——找到答案就停，不要继续白忙活！

例题 3：寻找第一个魔法数字

魔法图书馆规定：从 1 开始寻找，找到第一个能被 7 整除的数字，就立刻停止。

请找出这个数字。

方法一：找到答案，但继续检查

for (int i = 1; i <= 100; i++) { if (i % 7 == 0) { cout << i << endl; } }

这个程序会输出很多个数字：

7 14 21 28 ...

但题目只要第一个，后面的答案对我们来说都是多余的。

方法二：使用break提前结束

#include <iostream> using namespace std; int main() { for (int i = 1; i <= 100; i++) { if (i % 7 == 0) { cout << i << endl; break; } } return 0; }

输出：

7

break是什么？

我们可以把循环想象成一座迷宫。

• for循环：继续往前探索；

• 找到答案：任务完成；

• break：立即离开当前循环。

例题 4：在数组中寻找第一个大于 50 的数字

数组中存放着：

12、25、38、56、71、90

要求找到第一个大于 50 的数字。

#include <iostream> using namespace std; int main() { int a[6] = {12, 25, 38, 56, 71, 90}; for (int i = 0; i < 6; i++) { if (a[i] > 50) { cout << a[i] << endl; break; } } return 0; }

输出：

56

程序检查 12、25、38，发现它们都不符合条件。检查到 56 时，发现答案，立刻结束循环。

71 和 90 就不用再检查了。

什么时候可以使用break？

适合以下情况：

• 题目只要求找到任意一个满足条件的答案；

• 题目要求找到第一个满足条件的答案，并且枚举顺序符合题目要求；

• 已经确定任务完成，不需要继续枚举。

但如果题目要求统计所有满足条件的答案，就不能找到第一个后直接退出。

例如，要统计 1 到 100 中有多少个 7 的倍数，就必须继续检查，或者使用其他准确的计数方法。

第四站：绝招四——提前排除不可能的方案

这一招非常重要。它不仅是暴力枚举的优化思想，也是以后学习 DFS、回溯和剪枝的基础。

例题 5：寻找和为 10 的三张数字卡片

有 5 张卡片：

2、4、6、8、10

请从中选出三张不同位置的卡片，使它们的数字之和等于 10。

第一步：直接枚举三个位置

我们可以用三层循环：

#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++) { for (int k = j + 1; k < 5; k++) { if (a[i] + a[j] + a[k] == 10) { cout << a[i] << " " << a[j] << " " << a[k] << endl; } } } } return 0; }

运行后没有输出。

为什么？

因为最小的三个数字是：

2+4+6 = 12

最小和都已经大于 10 了，其他三张卡片的和只会更大。因此不可能找到答案。

第二步：如果数字更多，怎样提前判断？

假设我们正在挑选三张卡片，已经选了两张，当前的和是 12，而目标是 10。

即使第三张卡片取最小的正数，最终的和也不会小于 12。

那么我们还需要继续尝试吗？

不需要！

这就是提前排除不可能的方案。

在算法竞赛中，这种思想经常被称为“剪枝”：像园丁剪掉多余的枝条一样，提前去掉不可能产生答案的搜索分支。

第三步：尝试写一个剪枝版本

我们可以在选第三张卡片前，先判断前两张的和是否已经达到目标。

#include <iostream> using namespace std; int main() { int a[5] = {2, 4, 6, 8, 10}; int target = 10; for (int i = 0; i < 5; i++) { for (int j = i + 1; j < 5; j++) { int sum = a[i] + a[j]; if (sum >= target) { continue; } for (int k = j + 1; k < 5; k++) { if (sum + a[k] == target) { cout << a[i] << " " << a[j] << " " << a[k] << endl; } } } } return 0; }

这段代码使用了continue：

if (sum >= target) { continue; }

它表示：跳过当前这一次外层循环中的后续语句，转到下一次循环。

不过，这个优化依赖于题目中的数字都是正数。如果数组中可能有负数，就不能简单地认为“当前和已经很大，后面一定无法得到目标”，必须重新分析后续数字可能带来的变化。

请记住：剪枝的前提是判断必须正确。不能因为觉得某种方案不太可能，就随意跳过它。

第五站：break、continue和普通if，有什么不同？

初学者经常把这三个概念混在一起，我们用一个小故事来区分。

想象你正在检查一排宝箱。

• if：判断当前宝箱是否符合要求。

• continue：当前宝箱不再继续处理，去检查下一个宝箱。

• break：整个当前循环停止，不再检查后面的宝箱。

看这个例子：

#include <iostream> using namespace std; int main() { for (int i = 1; i <= 10; i++) { if (i % 2 == 1) { continue; } if (i == 8) { break; } cout << i << " "; } return 0; }

我们一步一步看：

最终输出：

2 4 6

这里有个容易忽略的细节：当i == 8时，程序先判断它是不是奇数。8 不是奇数，因此不会执行continue，接着判断i == 8，最后执行break。

第六站：综合实战——为魔法学校挑选队员

前面我们学了四种技巧，现在把它们组合起来，解决一道更接近真实竞赛的题目。

例题 6：寻找最合适的两位队员

题目背景

魔法学校有 6 位候选队员，他们的能力值分别为：

3、5、7、9、11、13

校长要从中选择两位队员，要求：

1. 两位队员不能是同一个人；

2. 两人的能力值之和必须等于 20；

3. 每种队伍只输出一次。

请输出所有符合要求的队伍，并统计队伍数量。

第一步：建立候选名单

int a[6] = {3, 5, 7, 9, 11, 13};

数组中的每个位置代表一位候选队员。

第二步：枚举每一种组合

我们使用两层循环，并让第二个下标从i + 1开始，避免重复。

第三步：判断是否符合要求

如果：

a[i] + a[j] == 20

就输出这一组，并将队伍数量加 1。

完整参考程序

#include <iostream> using namespace std; int main() { int a[6] = {3, 5, 7, 9, 11, 13}; int cnt = 0; for (int i = 0; i < 6; i++) { for (int j = i + 1; j < 6; j++) { int sum = a[i] + a[j]; if (sum == 20) { cout << a[i] << " " << a[j] << endl; cnt++; } } } cout << "队伍数量：" << cnt << endl; return 0; }

输出结果：

7 13 9 11 队伍数量：2

第四步：看看我们用到了哪些技巧

组合枚举

j = i + 1，确保每对队员只检查一次。

条件判断

sum == 20，只保留符合要求的队伍。

计数器

每找到一支队伍，就执行cnt++。

枚举所有答案

本题要求找出所有队伍，所以不能找到第一组后就break。

这就是算法学习中很重要的一步：不要只会背一个模板，而要学会把多个小技巧组合起来。

第七站：课后闯关——你能成为枚举优化小专家吗？

下面 5 道题由浅入深。建议先自己写程序，再展开参考答案。

练习 1：寻找魔法倍数

找出 1 到 100 中所有能被 8 整除的数字。

要求：不要从 1 开始逐个判断，尝试直接枚举 8 的倍数。

参考程序：

#include <iostream> using namespace std; int main() { for (int i = 8; i <= 100; i += 8) { cout << i << " "; } return 0; }

练习 2：不重复的数字搭档

数组为a = {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; }

练习 3：找到第一个答案

从 1 开始，找到第一个大于 30、同时能被 5 整除的数字，找到后立即停止。

参考程序：

#include <iostream> using namespace std; int main() { for (int i = 1; i <= 100; i++) { if (i > 30 && i % 5 == 0) { cout << i << endl; break; } } return 0; }

练习 4：三张卡片的秘密

有数字卡片2、3、4、5、6，选出三张不同位置的卡片，使它们的和等于 12。输出所有组合。

参考程序：

#include <iostream> using namespace std; int main() { int a[5] = {2, 3, 4, 5, 6}; for (int i = 0; i < 5; i++) { for (int j = i + 1; j < 5; j++) { for (int k = j + 1; k < 5; k++) { if (a[i] + a[j] + a[k] == 12) { cout << a[i] << " " << a[j] << " " << a[k] << endl; } } } } return 0; }

练习 5：聪明的侦探

判断下面的程序为什么只输出2 4 6，而不会输出8 10。

for (int i = 1; i <= 10; i++) { if (i % 2 == 1) continue; if (i == 8) break; cout << i << " "; }

答案：

当i是奇数时，continue会跳过输出语句。当i到达 8 时，执行break，整个循环结束，因此 8 和 10 都不会输出。这题考查的是：continue只跳过本次循环，break则结束当前循环。

第八站：本单元知识地图

最后送给同学们一句话：

先保证答案不漏，

再想办法少算；

先理解为什么能跳过，

再写优化代码。

暴力枚举是许多高级算法的起点。下一单元，我们将进入第三章——贪心算法，学习如何每一步都做出一个看似最好的选择，并研究什么时候这种选择真的能得到全局最优解。