#枚举法

#什么是枚举法

枚举算法（Enumeration Algorithm）是一种通过遍历所有可能的解来寻找问题答案的算法。它的核心思想是“穷举”，不放过任何可能的情况，逐一测试每一种情况，看是否符合问题的要求。因此枚举法也称穷举法或暴力求解法。

枚举算法通常用于解决那些没有明显规律或无法通过数学公式直接求解的问题。它的优点是简单直观，缺点是当问题的规模较大时，计算量会非常大，效率较低。

#枚举法的基本步骤

枚举法的基本步骤可以概括为：

1. 定义问题解的范围：确定所有可能的解的集合（范围）。
2. 遍历所有解：对每一个可能的解进行逐一验证。
3. 判断条件：根据题目要求对每个解进行条件判断，符合条件的留下，不符合的舍去。
4. 输出结果：按题目要求对符合条件的解输出。

例如，假设有这样的一个问题：在一个给定的数组中，找出两个数的和为指定值的情况。我们就可以使用枚举法，遍历数组中所有的两个数，逐一判断它们的和是否为指定值。

实际上，在前面的章节中很多问题都是用枚举法来解决的（只是没有专门用枚举法个说法）。如：求 1 ~ n 中所有满足是 2 的倍数，但不是 3 的倍数的数有哪些，共有多少个？

#练习：寻找两数之和为目标值的配对

#题目描述

给定一组数和一个目标值，寻找这组数中其中任意两个数之和为目标值的所有配对。

注意，不考虑配对的顺序，如 ${2, 5}$ 与 ${5,2}$ 为同一组配对，我们只取 $(i, j)$ 配对中，$i \le j$ 的情况。

#输入描述

输入为两行。 第一行包括两个数 $n$ 和 $x$，其中 $n$ 表示要输入的 $n$ 个数；$x$ 表示目标值。

#输出描述

所有的配对组合，每行一组配对。

#输入输出样例

输入1

输出

#示例：鸡兔同笼问题

#题目描述

有若干只鸡兔同在一个笼子里，从上面数，有 $n$ 个头，从下面数，有 $m$ 只脚。问笼中各有多少只鸡和兔？

#输入描述

输入为一行，包含两个整数 $n$ 和 $m$，用空格隔开，$n$ 代表头数，$m$ 代表脚数

#输出描述

输出为一行，满足题目要求的鸡和兔的数量，用空格隔开

#输入输出样例

输入数据 1

输出数据 1

#题目解析

鸡兔同笼是几乎所有人在小学都遇到过的一个题目，从数学的角度来看，有非常多种解决方法：列表法、假设法、列方程组法、图形法等等。

不过，当我们学了编程后，又多了一种方法，就是枚举法，这种方法思想非常简单，对人来说甚至很「笨」，但对计算机来说很擅长。

既然我们知道了头数，也就是鸡或兔的数量的范围可以确定的，以鸡为例，最少是 0 只鸡（因为可能全是兔），最多是 $n$ 只鸡。那我们用枚举法，将所有可能的鸡列出来，一旦鸡知道了，兔的数量就用 $n$ 减法鸡的数量就行了。鸡和兔的数量都知道了，那它们的总脚数也就知道了，对于每一种组合可能，去验证一下，它们的总脚数是不是等于题目要求的脚数。满足条件则输出。

#实现代码

#include <iostream>
using namespace std;

int main() {
    int n, m; // n 代表头数，m 代表脚数
    cin >> n >> m;
    
    for (int i = 0; i <= n; i++) { // 鸡的数量可能范围
      if (i * 2 + (n - i) * 4 == m) { // 验证条件是否满足
        cout << i << " " << n - i << endl;
      }
    }
    return 0;
}

#示例：百钱百鸡问题

#问题描述

用 100 元钱买 100 只鸡，公鸡，母鸡，小鸡都要有。

公鸡 5 元 1 只，母鸡 3 元 1 只，小鸡 1 元 3 只。

请问公鸡，母鸡，小鸡各应该买多少只？

#输入描述

无。

#输出描述

每种买法占一行，由 3 个数组成，顺序为 公鸡数 母鸡数 小鸡数。每个数字空格隔开。

输出时，按公鸡数从少到多，母鸡数从多到少的顺序输出，本题符合条件的第一组解为： 4 18 78 。

#代码实现

#include <bits/stdc++.h>

int main() {
  int i, j, k;
	// i, j, k 分别为公鸡、母鸡与小鸡的数量
  for(i = 1; i <= 100; i++)
    for(j = 100; j >= 1; j--)
      for(k = 1; k <= 100; k++) {
        if(5 * i + 3 * j + k / 3 == 100 && k % 3 == 0 && i + j + k == 100 ) {
            printf("%d %d %d\n", i, j, k);
        }
      }

  return 0;
}

#代码解析及优化

注意这里为了保证公鸡数从少到多，母鸡数从多到少，代表公鸡数的第一层循环 i 是从小到多，依次递增，代表母鸡第二层循环 j 是从多到少，依次递减。

如果再仔细想想，因为公鸡是 5 元 1 只，100 元最多也只能买 20 只公鸡；同理，100 元最多也只能买 33 只母鸡，因此在上面的循环体内，代表公鸡与母鸡的循环没有 100 次这么多。

经过第一次优化后的代码如下：

#include <bits/stdc++.h>

int main() {
  int i, j, k;
	// i, j, k 分别为公鸡、母鸡与小鸡的数量
  for(i = 1; i <= 20; i++)
    for(j = 33; j >= 1; j--)
      for(k = 1; k <= 100; k++) {
        if(5 * i + 3 * j + k / 3 == 100 && k % 3 == 0 && i + j + k == 100 ) {
            printf("%d %d %d\n", i, j, k);
        }
      }

  return 0;
}

循环的执行的次数从 100 * 100 * 100，共 100 万次，直接减到 20 * 33 * 100 ，共 66000 次。

再继续看，已知公鸡与母鸡的数量后，小鸡的数量就可以直接计算出来了，而没必要再来一层循环去枚举了。

经过再次优化后的代码如下：

#include <iostream>
using namespace std;

int main() {
  // i 是公鸡数，j 是母鸡数，k 是小鸡数  
  for (int i = 1; i <= 20; i++)  {
    for (int j = 33; j >= 1; j--) {
        int k = 100 - i - j;
        if ((i * 5 + j * 3 + k / 3 == 100) && (k % 3 == 0)) {
          printf("%d %d %d\n", i, j, k);
        }
      }
    }
  return 0;
}

这次优化后，循环执行的次数再次从 66000 次，减少到 20 * 33，只有 660 次。可以看到，一点代码修正，循环执次的次数减少得还是挺多的。

#示例：三色球问题

见 循环 章节中嵌套循环部分。

对于很多排列组合的问题，通过也可以应用枚举法求解。后面会讲到的搜索问题求解，本质上也是一种枚举，只是问题更复杂一些。

#题目描述

一个口袋里有 12 个球，其中有三个红球，三个白球，六个黑球 从其中取 8 个球，问有多少种颜色搭配？

#输入

无

#输出

输出搭配种类个数

#实现代码

#include <iostream>
using namespace std;

int main() {
  int cnt = 0;
  for (int i = 0; i <= 3; i++) {
    for (int j = 0; j <= 3; j++) {
      for (int k = 0; k <= 6; k++) {
        if (i + j + k == 8) {
          cnt++;
        }
      }
    }
  }
  
  cout << cnt << endl;
  return 0;
}

#示例：含 0 的数

#题目描述

请求出 1 ~ $n$ 中含有数字 0 的数，共有多少个？

#输入

一个整数 $n$（$n \le 999$）

#输出

一个整数，代表 1 ～ $n$ 中含有数字 0 的数的个数。

#输入输出样例

输入数据 1

输出数据 1

输入数据 2

输出数据 2

#题目解析

从题目描述来看，又是一个典型的枚举问题，遍历问题空间所有元素（1 ~ $n$ 中的所有数），判断该元素是否含有 0，若含有则计数加 1。

在判断元素是否含有 0 时，结合了前面遇到过的拆分数字问题，将数字中的每一位拆分出来，判断是否是 0，一旦是 0，则该数含有 0，且不需要再判断了。

例如：100，拆出个位是 0，根据条件，该元素满足计数，就不需要判断十位的 0 了，否则该数会被重复计数。

#代码实现

#include <iostream>
using namespace std;

int main() {
  int n, cnt = 0;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int j = i; // 避免 i 被改动，影响后续元素遍历
    while (j > 0) {
      if (j % 10 == 0) {
        cnt++;
        break; // 一旦含有 0，就不需要再计数了
      }
      j = j / 10;
    }
  }
  cout << cnt << endl;
  return 0;
}

#小结

枚举法，简言之，就是一个一个把可能的解列出来，根据题目条件去判断或计算，典型的大力出奇迹，所以有时也被称为暴力求解法，这种问题通常数据范围不大，难度并不高，通过枚举来暴力求解往往效果非常好。