CC++ & Algorithm

C++枚举算法

困难17
语言版本：C++Python
概述：枚举算法就是“把所有可能性都试一遍”，就像解开密码锁时，从0000试到9999一样。

枚举算法：把所有可能都试一遍

枚举算法是编程解决问题的“笨办法”，也是“最靠谱”的办法。它的思路非常简单：把所有可能的答案都列出来，然后一个个检查，挑出符合要求的那些。就像你忘记密码箱的密码时，从0000一直试到9999，总会找到正确的那一个。虽然看起来有点“傻”，但只要枚举得全面，就一定能找到正确答案。在C++三级考试中，枚举经常用来解决整数、组合、判断类的问题。

生活中的枚举——你早就用过

  • 开锁：三位数字密码锁，从000试到999，最多1000次就能打开。
  • 配颜色：你有5支彩笔，想找出哪两支放在一起最好看，就把所有两支组合都试一遍（共10种）。
  • 猜数字：小明心里想一个1~100之间的数，你每次猜一个，他告诉你“大了”或“小了”，你从头到尾猜一遍也能中——不过用二分法更快，但枚举也能行。

枚举算法的三个关键点

要写好枚举，必须想清楚三件事：

  1. 枚举什么（对象）——是数字、位置、还是物品的编号？
  2. 范围多大（范围）——从几到几？不能漏，也不能太浪费。
  3. 满足什么条件（判断）——用if语句检查，符合就输出。

举个例子：找出1到100之间所有既能被3整除又能被5整除的数。

  • 枚举对象：整数 num
  • 范围：1到100
  • 条件：num % 3 == 0 且 num % 5 == 0

C++代码中的枚举——从简单到复杂

例1：找出1~100中所有能被3整除的数（原有示例）

#include <iostream>
using namespace std;

int main() {
    cout << "1到100之间能被3整除的数有：";
    for (int i = 1; i <= 100; i++) {   // 枚举所有可能的数 i
        if (i % 3 == 0) {              // 检查条件：能被3整除
            cout << i << " ";          // 满足条件就输出
        }
    }
    cout << endl;
    return 0;
}

运行结果：

1到100之间能被3整除的数有：3 6 9 12 15 18 ... 99

例2：找出所有的“水仙花数”（三位数中，各位数字的立方和等于本身）

水仙花数是一个有趣的三位数，比如 153 = 1³ + 5³ + 3³。我们可以枚举所有三位数（100~999）来检查。

#include <iostream>
using namespace std;

int main() {
    cout << "水仙花数有：";
    for (int num = 100; num <= 999; num++) {   // 枚举所有三位数 num
        int a = num / 100;                     // 百位数字
        int b = (num / 10) % 10;              // 十位数字
        int c = num % 10;                     // 个位数字
        if (a*a*a + b*b*b + c*c*c == num) {   // 判断条件：立方和等于本身
            cout << num << " ";
        }
    }
    cout << endl;
    return 0;
}
// 输出：153 370 371 407

例3：鸡兔同笼——经典枚举

一个笼子里有鸡和兔，共有20个头、54只脚，问鸡和兔各几只？
鸡有1头2脚，兔有1头4脚。枚举鸡的数量chicken从0到20，那么兔的数量就是20 - chicken，检查脚数是不是54。

#include <iostream>
using namespace std;

int main() {
    int head = 20;   // 总头数
    int foot = 54;   // 总脚数
    bool found = false;                       // 是否找到答案

    for (int chicken = 0; chicken <= head; chicken++) {   // 枚举鸡的数量
        int rabbit = head - chicken;                      // 兔的数量
        if (chicken * 2 + rabbit * 4 == foot) {           // 判断脚数是否匹配
            cout << "鸡：" << chicken << "只，兔：" << rabbit << "只" << endl;
            found = true;
            break;    // 找到一组解就可以跳出循环（实际上鸡兔同笼只有一组解）
        }
    }
    if (!found) {
        cout << "没有找到答案" << endl;
    }
    return 0;
}
// 输出：鸡：13只，兔：7只

新手容易犯的错误

  1. 漏掉了边界
    比如要检查1~100，但循环写成了 for (int i = 1; i < 100; i++)，漏掉了100。记得包含端点，用<=。

  2. 条件判断反了
    比如要找能被3整除的数，却写成了 if (i % 3 != 0)，结果输出了所有不能被3整除的。一定要先看清题目要求。

  3. 枚举范围太大，导致程序很慢
    比如让你找1~1000000之间满足条件的数，用枚举也能做，但考试一般不会出那么大的范围。如果遇到很大的范围，要考虑优化（不过三级考试通常用枚举就够了）。

  4. 忘了初始化变量
    比如想统计有几个满足条件的数，用了 count = 0; 却忘记写。一定要先给变量赋初值。

完整可运行示例：找出“完全数”

完全数是指一个数，它所有真因子（除了它本身外的约数）之和等于它本身。比如6的真因子有1、2、3，1+2+3=6，所以6是完全数。下面用枚举找出1~1000之间所有的完全数。

#include <iostream>
using namespace std;

int main() {
    cout << "1~1000之间的完全数有：";

    for (int num = 2; num <= 1000; num++) {   // 枚举每个数字（1不是完全数，从2开始）
        int sum_factor = 0;                   // 用于累加真因子的和

        // 找 num 的所有真因子（从1到 num/2 就够了）
        for (int factor = 1; factor <= num / 2; factor++) {
            if (num % factor == 0) {          // 如果能整除，就是因子
                sum_factor += factor;         // 累加因子
            }
        }

        if (sum_factor == num) {              // 判断：真因子之和是否等于本身
            cout << num << " ";
        }
    }
    cout << endl;
    return 0;
}
// 输出：6 28 496

在这个例子中，外层循环枚举待检查的数字，内层循环枚举它的因子。这就是枚举的嵌套使用。

相关知识点

学完枚举算法，你还可以继续学习：

  • 循环：for和while是实现枚举的基础。
  • 条件判断：if、else if、else用来筛选结果。
  • 数组与枚举：有时需要枚举数组中的下标或元素。
  • 暴力求解：枚举是暴力算法的核心，适合数据量小的题目。
  • 优化思路：比如缩小枚举范围、提前跳出循环（break），可以让程序更快。

枚举就像一张最笨但最全的“地图”，拿着它，你永远不会迷路。在GESP三级考试中，很多问题都可以先用枚举试试看，至少能保证得分。等你熟练了，再学更巧妙的算法。

例题精讲

1单选题

在C++枚举算法中，枚举所有可能情况后，通常需要进行什么操作来找到正确解？

A排序
B判断
C输出
D递归
2判断题

枚举算法的时间复杂度与问题规模无关，只与枚举范围有关。

3填空题
计算1到100中所有能被3整除的数之和，请补充代码：
int sum = 0;
for(int i = 1; ___; i++) {
    if(i % 3 == 0) sum += i;
}