<style> .reveal p{text-align:left;}</style> # 枚举 || |:---:| || --- ## 0、引子 你是数学课代表，今天收数学作业少了二份，请问你如何找出是谁没有交作业？  ---- 你可以核对一下班级名单，看看谁的名字没有出现在已交作业的名单中。 --- ## 1、枚举（穷举）思想 根据题目描述确定答案的范围，然后对所有可能的情况都逐一验证，直到全部情况验证完毕。 --- 枚举算法的本质就是从所有候选答案中去搜索正确的解,使用该算法需要满足两个条件： 1. 可预先确定候选答案的数量； 2. 候选答案的范围在求解之前必须有一个确定的集合。 --- - **优点**：思路清晰直观、正确性明显、编码容易（一般为循环＋判断）。 - **缺点**：效率低。 --- ## 2、常见模式 枚举有一些常见的应用，需要熟练掌握，例如： - **查找**：在一个序列里找到第一个满足条件的元素 - **最大（最小）值**：在一个序列里找最大（最小）值 - **求和（积、平均）**：算一个序列的和（积、平均等） - **计数**：在一个序列里查找满足条件的元素，统计其个数 - **组合**：多种状态组合，找到满足条件的组合 有时候，要在多维状态里进行枚举，比如常见的路径查找等。 --- ## 3、抽象模型 --- ### 3.1 要素 对于任何可计算的问题，都可以提炼出四个要素：维度、状态、判定、求解。 由一个（或多个维度），计算得到一个状态，每个状态都可以通过某个规则来判定是否满足条件，那么就可以通过枚举每一个状态（状态空间），判定其是否是（属于）问题的解（解空间）。 注意：同一个问题，会有不同的方案，可以挑选不同的维度、状态、判定，达到同样的效果。 --- ### 3.2 判定 判定是计算理论的核心，通过对状态回答一个问题的结果是“真”还是“假”，计算机就可以知道某个状态是否是（属于）问题的解。 判定的方法可从问题中提炼出来，返回布尔值。有时候，复杂的判定也会有枚举的过程。如： ```c++ bool check(int n) { return n%2 == 0; } ``` --- ### 3.3 状态空间 枚举的对象是状态，状态空间的大小决定了枚举的次数。 很多时候算法是循环维度来计算得到状态，有时会混淆我们对状态的理解。 --- ### 3.4 维度到状态的映射 大部分试题，从维度到状态有一个映射关系，可以理解成一个函数，如： ```c++ int getState(int i) { return a[i]; } ``` --- 特殊情况，映射函数描述比较困难，也就无法编码实现此函数。此时如果知道状态的区间范围，也可以直接对状态进行枚举。此时判定除了状态是否满足条件以外，往往还要加上状态与维度是否吻合的判断。 --- ### 3.5 例子 例1：对于一个正整数序列，分别计算其中奇数、偶数的个数。 - 维度：下标 - 状态：值 - 判定：被2整除 - 求解：计数 |例题| |:---:| |[P185 练30.3 奇偶分家](http://39.99.183.126:8888/p/P185)| --- 例2：对于一个n个元素的递增序列，计算累加和（从第一个1位置往后累加），求出第一个超过m的累加和，输出对应的位置。 - 维度：下标1到n - 状态：累加和 - 判定：累加和>m - 求解：记录第一个判定成功的下标 |例题| |:---:| |[P1020 小于T的最大K](http://39.99.183.126:8888/p/1020)| --- 例3：给定日期的区间范围（两个8位的日期，yyyymmdd格式），计算其中回文日期的个数。 - 维度：日期（天） - 状态：8位的日期 - 判定：是否回文 - 求解：计数 --- 循环每天计算8位的日期，需要考虑每月天数、每年月数等因素，计算比较困难。考虑到对于一个年份，回文日期是固定的（如2012的回文是20122102），那么直接对状态枚举，方案如下： - 维度：年份 - 状态：回文日期 - 判定：是否正确日期 - 求解：计数 |例题| |:---:| |[P183回文日期（date）](http://39.99.183.126:8888/p/183)| ---