枚举

0、引子

你是数学课代表，今天收数学作业少了二份，请问你如何找出是谁没有交作业？

你可以核对一下班级名单，看看谁的名字没有出现在已交作业的名单中。

1、枚举（穷举）思想

根据题目描述确定答案的范围，然后对所有可能的情况都逐一验证，直到全部情况验证完毕。

枚举算法的本质就是从所有候选答案中去搜索正确的解,使用该算法需要满足两个条件：

• (1)可预先确定候选答案的数量；
• (2)候选答案的范围在求解之前必须有一个确定的集合。
• 优点：思路清晰直观、正确性明显、编码容易（一般为循环＋判断）。
• 缺点：效率低。

2、常见模式

枚举有一些常见的应用，需要熟练掌握，例如：

• 查找：在一个序列里找到第一个满足条件的元素
• 最大（最小）值：在一个序列里找最大（最小）值
• 求和（积、平均）：算一个序列的和（积、平均等）
• 计数：在一个序列里查找满足条件的元素，统计其个数
• 组合：多种状态组合，找到满足条件的组合 有时候，要在多维状态里进行枚举，比如常见的路径查找等。

3、抽象模型

3.1 要素

对于任何可计算的问题，都可以提炼出四个要素：维度、状态、判定、求解。

由一个（或多个维度），计算得到一个状态，每个状态都可以通过某个规则来判定是否满足条件，那么就可以通过枚举每一个状态（状态空间），判定其是否是（属于）问题的解（解空间）。

注意：同一个问题，会有不同的方案，可以挑选不同的维度、状态、判定，达到同样的效果。

3.2 判定

判定是计算理论的核心，通过对状态回答一个问题的结果是“真”还是“假”，计算机就可以知道某个状态是否是（属于）问题的解。

判定的方法可从问题中提炼出来，返回布尔值。有时候，复杂的判定也会有枚举的过程。如：

bool check(int n) {
return n%2 == 0;
}

3.3 状态空间

枚举的对象是状态，状态空间的大小决定了枚举的次数。

很多时候算法是循环维度来计算得到状态，有时会混淆我们对状态的理解。

3.4 维度到状态的映射

大部分试题，从维度到状态有一个映射关系，可以理解成一个函数，如：

int getState(int i) {
  return a[i];
}

特殊情况，映射函数描述比较困难，也就无法编码实现此函数。此时如果知道状态的区间范围，也可以直接对状态进行枚举。此时判定除了状态是否满足条件以外，往往还要加上状态与维度是否吻合的判断。

3.5 例子

例1：对于一个正整数序列，分别计算其中奇数、偶数的个数。

• 维度：下标
• 状态：值
• 判定：被2整除
• 求解：计数

例题
P185 练30.3 奇偶分家

例2：对于一个n个元素的递增序列，计算累加和（从第一个1位置往后累加），求出第一个超过m的累加和，输出对应的位置。

• 维度：下标1到n
• 状态：累加和
• 判定：累加和>m
• 求解：记录第一个判定成功的下标

例题
P1020 小于T的最大K

例3：给定日期的区间范围（两个8位的日期，yyyymmdd格式），计算其中回文日期的个数。

• 维度：日期（天）

• 状态：8位的日期

• 判定：是否回文

• 求解：计数

  循环每天计算8位的日期，需要考虑每月天数、每年月数等因素，计算比较困难。考虑到对于一个年份，回文日期是固定的（如2012的回文是20122102），那么直接对状态枚举，方案如下：

• 维度：年份

• 状态：回文日期

• 判定：是否正确日期

• 求解：计数

例题
P183 【基础】回文日期（date）