17. 枚举算法：暴力美学

前置学习：for 循环、嵌套循环

在数学中，遇到未知数我们需要列方程求解。但在计算机科学中，如果我们有一台每秒能计算上亿次的机器，最简单直接的方法是什么？ 答案是：把所有可能的答案全部猜一遍，哪个对了就是哪个！ 这种简单粗暴但极其有效的方法，我们称之为枚举（暴力搜索）。

1. 核心思想：不漏不重

枚举算法的核心就六个字：不重不漏地试。 通常我们会利用 for 循环生成所有可能的候选答案，然后在循环内部用 if 判断这个答案是否满足题目的所有条件。

2. 经典实战：百钱买百鸡

这是中国古代数学名著《算经》中的经典问题，也是全网最经典的枚举入门题。 题目描述： 公鸡 5 文钱一只，母鸡 3 文钱一只，小鸡 1 文钱买三只。现在你有 100 文钱，要求正好买 100 只鸡，而且每种鸡至少买 1 只。请问公鸡、母鸡、小鸡各买几只？

常规思路（三重循环）： 假设公鸡 $i$ 只，母鸡 $j$ 只，小鸡 $k$ 只。直接用三个循环嵌套，把所有可能的数量全组合一遍。

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 公鸡最多买 100/5 = 20 只
    for (int i = 1; i <= 20; i++) {
        // 母鸡最多买 100/3 = 33 只
        for (int j = 1; j <= 33; j++) {
            // 小鸡最多 100 只
            for (int k = 1; k <= 100; k++) {
                // 条件1：正好买了 100 只鸡。 条件2：小鸡数量必须是3的倍数。 条件3：正好花了 100 文钱。
                if (i + j + k == 100 && k % 3 == 0 && i * 5 + j * 3 + k / 3 == 100) {
                    cout << "公鸡:" << i << " 母鸡:" << j << " 小鸡:" << k << endl;
                }
            }
        }
    }
    return 0;
}

3. ⚠️ 算法优化：减少搜索空间

上面三重循环的代码绝对正确，但它要执行 $20 \times 33 \times 100 = 66000$ 次。 作为 OIer，我们一定要有优化时间的直觉：既然总共买 100 只鸡，如果公鸡 $i$ 只，母鸡 $j$ 只，那小鸡的数量是不是就已经固定只能是 100 - i - j 了？我们根本不需要第三个循环去猜小鸡的数量！

优化后的 OI 级代码（降维打击）：

for (int i = 1; i <= 20; i++) {
    for (int j = 1; j <= 33; j++) {
        int k = 100 - i - j; // 直接算出小鸡数量
        
        // 只需要判断钱是否花得正好，以及小鸡是不是3的倍数
        if (k % 3 == 0 && i * 5 + j * 3 + k / 3 == 100) {
            cout << "公鸡:" << i << " 母鸡:" << j << " 小鸡:" << k << endl;
        }
    }
}

优化效果： 循环次数瞬间从 66000 次降到了 660 次，速度提升了整整 100 倍！这就是算法的魅力。

4. 动手实践

1. 打开左下角的代码沙盒。
2. 试着编写程序寻找“水仙花数”。
3. 题目：水仙花数是指一个三位数，它的每个位上的数字的 3 次幂之和等于它本身。
   （例如：153 = 1^3 + 5^3 + 3^3）。
   利用枚举算法，找出 100 到 999 之间所有的水仙花数！