第二章 · 暴力枚举第一单元暴力枚举入门——让计算机替我们一个一个地试同学们欢迎来到算法王国的第二章在第一章中我们学习了一个重要本领拿到一道题不能急着敲代码而是要先分析题目判断可能使用什么算法。现在我们正式认识第一位算法探险家——暴力枚举它没有华丽的魔法也不会一眼看出答案。它的绝招只有一个把所有可能的情况有条理地检查一遍直到找到答案或者确认哪些答案符合要求。你可能会觉得“这不就是一个一个地试吗”没错但在计算机世界里很多看似简单的“一次次尝试”只要设计得合理就能解决非常有趣的问题。今天我们就跟随暴力枚举探险家进入藏宝洞、数字城堡和密码实验室学习如何把“一次次尝试”变成真正的算法。本单元包含概念理解暴力枚举到底是什么图示推演如何保证所有可能都没有遗漏基础代码用 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例如数字计算结果33 % 30符合44 % 31不符合66 % 30符合88 % 32不符合只要余数为 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三个数字之和为 6a 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、936918这里的sum是累加器每找到一个符合条件的数字就把它加到总和里。计数器和累加器的区别变量作用常见写法cnt统计数量cntsum计算总和sum ifound记录是否找到答案found true例题七检查是否存在幸运数字题目输入一个正整数 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; }十一、本单元知识地图十二、课后总结请带走这五句话暴力枚举不是乱试而是有顺序地检查所有候选情况。先确定范围再决定使用几层循环。判断条件必须准确既不能漏掉答案也不能把错误答案算进去。找一个答案可以考虑提前结束找所有答案就要继续检查。写出正确程序之后还要分析复杂度判断数据规模是否允许这样枚举。最后请记住一句话暴力枚举教会我们的不只是怎样写循环更是怎样把一个复杂问题拆成许多简单、清楚、能够逐一检查的小问题。下一课我们将继续研究暴力枚举怎样枚举所有组合、排列和子集当候选方案越来越多时又该怎样判断程序会不会超时 
长河君 · 2026/10/14 10:11:38 · 阅读 1.2k 小学生C++信息学竞赛课程----算法选择与思维训练（3、第二章 · 暴力枚举 第一单元：暴力枚举入门——让计算机替我们一个一个地试！）
第二章 · 暴力枚举第一单元暴力枚举入门——让计算机替我们一个一个地试同学们欢迎来到算法王国的第二章在第一章中我们学习了一个重要本领拿到一道题不能急着敲代码而是要先分析题目判断可能使用什么算法。现在我们正式认识第一位算法探险家——暴力枚举它没有华丽的魔法也不会一眼看出答案。它的绝招只有一个把所有可能的情况有条理地检查一遍直到找到答案或者确认哪些答案符合要求。你可能会觉得“这不就是一个一个地试吗”没错但在计算机世界里很多看似简单的“一次次尝试”只要设计得合理就能解决非常有趣的问题。今天我们就跟随暴力枚举探险家进入藏宝洞、数字城堡和密码实验室学习如何把“一次次尝试”变成真正的算法。本单元包含概念理解暴力枚举到底是什么图示推演如何保证所有可能都没有遗漏基础代码用 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例如数字计算结果33 % 30符合44 % 31不符合66 % 30符合88 % 32不符合只要余数为 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三个数字之和为 6a 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、936918这里的sum是累加器每找到一个符合条件的数字就把它加到总和里。计数器和累加器的区别变量作用常见写法cnt统计数量cntsum计算总和sum ifound记录是否找到答案found true例题七检查是否存在幸运数字题目输入一个正整数 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; }十一、本单元知识地图十二、课后总结请带走这五句话暴力枚举不是乱试而是有顺序地检查所有候选情况。先确定范围再决定使用几层循环。判断条件必须准确既不能漏掉答案也不能把错误答案算进去。找一个答案可以考虑提前结束找所有答案就要继续检查。写出正确程序之后还要分析复杂度判断数据规模是否允许这样枚举。最后请记住一句话暴力枚举教会我们的不只是怎样写循环更是怎样把一个复杂问题拆成许多简单、清楚、能够逐一检查的小问题。下一课我们将继续研究暴力枚举怎样枚举所有组合、排列和子集当候选方案越来越多时又该怎样判断程序会不会超时