第 27 课：暴力枚举

氪町博士想通过一个问题，带蛙蛙学习枚举知识，他想到了我国古代数学家张邱建在《算经》一书中提出的百钱买百鸡的问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一，百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？

意思是一只公鸡值 5 元，一只母鸡值 3 元，而 1 元可买 3 只小鸡。现有 100 元钱，想买 100 只鸡，可买公鸡、母鸡、小鸡各几只？

27.1 枚举的概念与案例实现

氪町博士告诉蛙蛙，可通过枚举来解这个题目。所谓枚举就是列出一个范围内的所有成员，或者说是将所有情况都举出，并判断其是否符合题目条件。

常见的枚举有以下几种。

1. 寻找可行解：某些问题可能的解处于一个有限的范围之内，这时就可以枚举全部可能的解，然后逐一检查这些解是否符合问题的要求，像氪町博士提出的百钱买百鸡的问题就是寻找可行解。

2. 确定最优解：在一些求最优值的问题中，可通过枚举所有可能的情况，再比较每种情况的目标值，从而确定最优解。

3. 预处理数据：在处理复杂问题时，可先通过枚举对数据进行预处理，获取一些必要的信息，从而简化后续的计算。

4. 缩小搜索范围：枚举部分条件，能够缩小后续搜索的范围，减少不必要的计算。

5. 验证算法正确性：在设计出一个复杂算法之后，可使用枚举算法对一些小规模的特殊情况进行求解，再将结果与复杂算法的结果进行对比，以此验证复杂算法的正确性。或者通过枚举所有可能的输入情况，检查程序在每种情况下的输出是否符合预期，从而定位和修复程序中的错误。

案例实现

蛙蛙准备先使用数学知识来解决这个问题，他先假设共买了 x 只公鸡、y 只母鸡、z 只小鸡，接着列出了一个方程组，即：

• 总只数：x + y + z = 100（只）
• 总钱数：5x + 3y + z / 3 = 100（元）

根据题目要求，同时满足上述两个条件的 x、y、z 值就是所求，但是蛙蛙通过数学知识实在不知道该如何去求解，还是要用到编程。

为了解决以上问题，蛙蛙准备通过三重循环将所有的情况都列举一遍，最外层循环遍历公鸡数量、第二层循环遍历母鸡数量、第三层循环遍历小鸡数量，然后通过 if 判断是不是满足条件，如果满足条件，便输出。

参考代码

#include <iostream>
using namespace std;
int main()
{
    for (int x = 0; x <= 100; x++) // 遍历公鸡数量
        for (int y = 0; y <= 100; y++) // 遍历母鸡数量
            for(int z = 0; z <= 100; z++) // 遍历小鸡数量
                if (x + y + z == 100 && 5 * x + 3 * y + z / 3 == 100)
                    cout << x << " " << y << " " << z << endl;
    return 0;
}

运行结果：

0 25 75
3 20 77
4 18 78
7 13 80
8 11 81
11 6 83
12 4 84

蛙蛙观察运行结果，发现有几组输出是不符合条件的，比如 3 20 77，不可能有 77 只小鸡，因为一元可以买 3 只小鸡，所以小鸡的数量一定是 3 的倍数。所以除了要满足 x + y + z == 100 && 5 * x + 3 * y + z / 3 == 100 外，还需要加上一个条件 z % 3 == 0。改完之后编译运行，结果如下：

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

于是蛙蛙很开心地告诉氪町博士，一共有上述四种情况。氪町博士很开心，因为蛙蛙不仅回答对了问题，而且在无意间也学会了枚举。蛙蛙首先枚举了公鸡的所有情况，再枚举了母鸡的所有情况，最后还枚举了小鸡的所有情况，符合条件就将其输出。

但是氪町博士补充道，这并不是一个很好的枚举程序，因为其时间复杂度相对来说较高，可以对其进行优化。

时间复杂度

时间复杂度是用来衡量算法运行时间与输入规模之间关系的一个概念。它描述了随着输入规模的增长，算法执行时间的增长趋势，通常用大 O 符号来表示，比如 O(1)、O(n)、O(n²) 等。

1. O(1) 意味着算法的执行时间与输入规模无关，始终是一个固定的常数。例如，访问数组中的一个特定元素，无论数组大小如何，都可以在常数时间内完成。

2. O(n) 意味着算法的执行时间与输入规模成正比。例如，遍历一个长度为 n 的数组，对每个元素进行一次操作，操作次数与数组长度 n 直接相关。

3. O(n²) 常出现于双层嵌套循环的算法，例如冒泡排序，其执行时间与输入规模的平方成正比。当 n 增大时，执行时间增长较快。

4. 其他的时间复杂度，例如 O(log n)、O(2ⁿ)，我们后续都会遇到。

案例优化

公鸡最多买 100 / 5 只，所以 x 的取值范围是 0 到 100 / 5，母鸡最多买 100 / 3，所以 y 的取值范围是 0 到 100 / 3，依此来分析，小鸡的取值范围是 0 到 3 × 100，由于最多买 100 只鸡，所以小鸡的取值范围依然是 0 到 100。

在确定公鸡和母鸡的数量之后，小鸡的数量便可以由公鸡和母鸡的数量推算出来。因为要买 100 只鸡，所以小鸡的数量 = 100 − 公鸡的数量 − 母鸡的数量。

所以我们便可以将三重 for 循环的程序优化成两重，同时优化每一层遍历的次数，但别忘了小鸡的数量是 3 的倍数。代码优化后如下：

#include <iostream>
using namespace std;
int main()
{
    for (int x = 0; x <= 100 / 5; x++) // 公鸡数量
        for (int y = 0; y <= 100 / 3; y++) // 母鸡数量
        {
            int z = 100 - x - y; // 小鸡数量
            if (5 * x + 3 * y + z / 3.0 == 100)
                cout << x << " " << y << " " << z << endl;
        }
    return 0;
}

27.2 枚举的优缺点

优点

1. 实现简单：代码实现的逻辑较为直接、简单，易于理解和实现，只需确定枚举的范围和判断条件，然后遍历所有可能的情况进行检查即可。

2. 覆盖所有的解：枚举可以覆盖问题所有的可能情况，保证不遗漏任何一个解，在一些需要找出所有可行解的问题中，枚举算法能确保找到所有符合条件的答案。

3. 结果准确：由于枚举算法会对所有可能的情况进行检查，所以其得到的结果是准确可靠的。

4. 便于调试：枚举算法的逻辑简单，代码结构清晰，所以在调试过程中容易发现问题；当程序出现错误时，可以很方便地检查每一个枚举步骤和判断条件，找出错误所在。

缺点

1. 效率低下：枚举算法的时间复杂度通常较高，尤其是当枚举范围较大时，计算量会急剧增加。

2. 空间需求大：在某些情况下，枚举算法可能需要存储大量的中间结果或状态信息，从而占用较多的内存空间。

3. 不适用于复杂问题：对于一些复杂的问题，枚举的范围可能非常大或者难以确定，使用枚举算法不具有可行性。

这就是为什么枚举常被叫作暴力枚举。暴力虽然出奇迹，但是在大多数情况下都不可取。枚举仅适用于一些规模较小的问题，否则可能会超时。

27.3 实例讲解

例 1：换钱

氪町博士想将手中的一张面值 100 元的人民币换成 10 元、5 元、2 元和 1 元面值的纸币，他想要换 40 张，且每种纸币至少一张。他想考考蛙蛙的枚举知识学得如何，于是问他：有哪些换法？

【输入格式】无

【输出格式】输出 n 行，每行 4 个数，分别表示 10 元、5 元、2 元、1 元的数量。

解析

1. 先假设 10 元、5 元、2 元和 1 元的纸币数量分别为 x、y、z、k。

2. 约束条件 a. 每种纸币至少一张：这意味着 x ≥ 1，y ≥ 1，z ≥ 1，k ≥ 1。 b. 总张数为 40 张：即 x + y + z + k = 40，由此可以推导出 k = 40 - x - y - z。 c. 总面值为 100 元：也就是 10x + 5y + 2z + k = 100。

3. 枚举范围确定 a. 对于 10 元纸币数量 x：由于每种纸币至少有一张，且总面值为 100 元，若全部为 10 元纸币，最多只能有 10 张，但因为还有其他面值的纸币，所以 x 的取值范围是从 1 到 9（即 1 ≤ x < 10）。 b. 对于 5 元纸币数量 y：同理，若全部为 5 元纸币，最多可以有 20 张，但要考虑其他面值纸币的存在以及每种纸币至少一张的条件，所以 y 的取值范围是从 1 到 19（即 1 ≤ y < 20）。 c. 对于 2 元纸币数量 z：若全部为 2 元纸币，最多可以有 50 张，结合其他条件，z 的取值范围是从 1 到 49（即 1 ≤ z < 50）。

参考代码

#include <iostream>
using namespace std;
int x, y, z, k;
int main()
{
    for (x = 1; x < 10; x++)
        for (y = 1; y < 20; y++)
            for (z = 1; z < 50; z++)
            {
                k = 40 - x - y - z;
                if (10 * x + 5 * y + 2 * z + k == 100 && k > 0)
                {
                    cout << x << " " << y << " " << z << " " << k << endl;
                }
            }
    return 0;
}

例 2：独特的三位数

在数学世界里，有着一些独特的三位数，它们隐藏着有趣的规律。以整数 543 为例，它具有一个特殊的性质：其百位数字的平方恰好等于十位数字的平方与个位数字的平方之和，即 5² = 4² + 3²。现在，请你编写一个程序，找出所有符合这种特殊性质的三位数，并将它们一一输出。

【输入格式】无

【输出格式】输出 n 行，每行一个三位数。

解析

1. 假设这个三位数是 xyz（如 543，即 x = 5，y = 4，z = 3），根据题目要求得知百位数字的平方等于十位数字的平方与个位数字的平方之和，即：x * x = y * y + z * z，代码如下：

if (x * x == y * y + z * z)
    cout << x << y << z;

2. 根据题目要求我们得知，xyz 是一个三位数，所以 x 不为 0，最外层循环为百位数 x，从 1 开始，小于 10；中层循环为十位数 y，从 0 开始，小于 10；内层循环为个位数 z，从 0 开始，小于 10，即：

for (x = 1; x < 10; x++)
    for (y = 0; y < 10; y++)
        for (z = 0; z < 10; z++)

参考代码

#include <iostream>
using namespace std;
int main()
{
    for (int x = 1; x < 10; x++)
        for (int y = 0; y < 10; y++)
            for (int z = 0; z < 10; z++)
            {
                if (x * x == y * y + z * z)
                    cout << x << y << z << endl;
            }
    return 0;
}

例 3：银行取钱

蛙蛙来到银行柜台，准备将自己银行卡里剩余的钱全部取出，用于即将开始的旅行。

蛙蛙查询后得知，银行卡里恰好还剩下 n 元。然而，近期由于银行资金调配的情况，目前银行储备的纸币只有 5 元、2 元和 1 元这三种面值。

现在，蛙蛙好奇地想知道，将这 n 元全部取出来，到底会有多少种不同的纸币组合办法呢？

【输入格式】输入一行，一个正整数 n，n ≤ 10000。

【输出格式】输出一行，一个数，表示取钱的组合数量。

【输入样例】50

【输出样例】146

解析

先枚举 5 元纸币和 2 元纸币的张数，然后根据总金额 n 计算出 1 元纸币的张数，最后判断计算出的 1 元纸币张数是否为非负整数。如果是，则说明找到了一种有效的组合方式。

参考代码

#include <iostream>
using namespace std;
int main()
{
    int n, count = 0, k;
    cin >> n;
    for (int i = 0; i <= n / 5; i++) // 枚举 5 元纸币
    {
        for (int j = 0; j <= n / 2; j++) // 枚举 2 元纸币
        {
            k = n - i * 5 - j * 2; // 计算 1 元纸币
            if (k >= 0)
                count++; // 找到了一种有效的组合方式
        }
    }
    cout << count << endl;
    return 0;
}