algo-enum.md

↑ 目录第 1 节 枚举法的思想

枚举（Enumeration）是所有算法中最朴素的一种：把可能的情况全部试一遍，找到满足条件的答案。听起来很"笨"，但它简单、可靠，是解决很多问题的起点。

枚举的三大要素：

• 范围：要枚举谁、从几到几？
• 条件：满足什么条件才算答案？
• 剪枝：哪些情况明显不可能，直接跳过？

↑ 目录第 2 节 例题 1：水仙花数

所谓水仙花数，是指一个三位数，它的各位数字的立方之和等于它本身。例如 153 = 1³ + 5³ + 3³。请输出所有的水仙花数。

思路：枚举从 100 到 999 的每一个数，拆出百位、十位、个位，验证条件。

#include <iostream>
using namespace std;

int main() {
    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;
        }
    }
    return 0;
}

153
370
371
407

↑ 目录第 3 节 例题 2：百钱买百鸡

公鸡 5 文钱一只，母鸡 3 文钱一只，小鸡 1 文钱三只。用 100 文钱买 100 只鸡，问公鸡、母鸡、小鸡各多少只？

设公鸡 x 只、母鸡 y 只、小鸡 z 只，则：

• x + y + z = 100
• 5x + 3y + z/3 = 100

#include <iostream>
using namespace std;

int main() {
    for (int x = 0; x <= 20; x++) {          // 公鸡最多 20 只
        for (int y = 0; y <= 33; y++) {      // 母鸡最多 33 只
            int z = 100 - x - y;              // 小鸡数量由总数确定
            if (z % 3 == 0 && 5*x + 3*y + z/3 == 100) {
                cout << x << " " << y << " " << z << endl;
            }
        }
    }
    return 0;
}

0 25 75
4 18 78
8 11 81
12 4 84

这里我们做了两处剪枝：

• 公鸡一只 5 文，最多只能买 20 只，所以 x <= 20；母鸡最多 33 只，所以 y <= 33。
• 小鸡必须 z % 3 == 0，否则按"三只一文"无法凑整数文钱。
• 枚举 x、y 后，z 由 100 - x - y 直接算出，少一层循环，这就是剪枝的威力。

↑ 目录第 4 节 例题 3：回文质数

既是回文数又是质数的数叫回文质数。例如 131 倒过来还是 131，且是质数。输出 10 到 999 之间的所有回文质数。

这道题把两个小技巧合在一起：判断质数（试除到 √n）＋ 判断回文（反转数字）。

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    for (int n = 10; n < 1000; n++) {
        int t = n, rev = 0;
        while (t) { rev = rev * 10 + t % 10; t /= 10; }
        if (rev == n && isPrime(n)) {
            cout << n << " ";
        }
    }
    cout << endl;
    return 0;
}

11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929

↑ 目录第 5 节 什么时候用枚举、复杂度怎么算

枚举适合的问题：

• 问题规模小：需要检查的总情况数在千万量级以内，1 秒内基本能跑完。
• 答案空间有限：比如求方案数、找满足条件的组合。
• 没有明显更优解时：先写枚举保证正确，再思考优化（如用数学推导缩小范围）。

复杂度怎么估？数一数最里层的代码会被执行多少次：

• 单层 for 从 1 到 n：约 n 次。
• 两层 for 各到 n：约 n × n 次，即 n²。

通常认为 1 秒大约能执行 10⁸（1 亿）次简单操作。所以三重循环每层 10000 就是 10¹² 次，必超时（TLE）；而 n = 1000 的二重循环（100 万次）毫无压力。

↑ 目录第 6 节 动手练习

基础练习：

• 求 1 到 1000 之间的完数（等于其真因数之和的数，如 6 = 1+2+3）。
• 打印九九乘法表。
• 输入一个整数 n，输出 1 到 n 之间所有既能被 3 整除又能被 5 整除的数。

挑战练习：

• 用 1 分、2 分、5 分硬币凑出 100 分，共有多少种方案？提示：三重循环枚举三种硬币数量，答案是一个三位数（先写对，再思考如何减到两重循环）。
• 寻找 2 到 100 之间的所有"孪生质数"（差为 2 的两个质数，如 3 和 5）。
• 翻硬币：有 n（n ≤ 20）枚硬币，正面为 1 反面为 0，枚举所有可能正反状态（提示：用 1 << n 表示所有状态，用位运算判断某一位）。