枚举算法的思想与实例讲解

枚举算法是我们在日常中使用到的最多的一个算法，本篇将会介绍枚举算法的思想与实例讲解，在使用频率上，枚举算法在蓝桥杯比赛里用的次数非常多，所以需要在平时多练习做题，毕竟实践检验真理，毕竟枚举在考试中出现的频率非常高，可谓是得枚举者得天下，下面我们就来讲讲枚举。

一、  枚举算法的思想

谈到枚举算法，所谓的枚举算法就是按问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解，若是，我们采纳这个解，否则抛弃它。在列举的过程中，既不能遗漏也不应重复。

（1）枚举算法的定义：

在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么该结论是可靠 的，这种归纳方法叫做枚举法。

（2）枚举算法的思想是：

将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，舍弃不合适的。

（3）使用枚举算法解题的基本思路如下：

1. 确定枚举对象、范围和判定条件。

2. 逐一枚举可能的解并验证每个解是否是问题的解。

（4）枚举算法步骤：

1. 确定解题的可能范围，不能遗漏任何一个真正解，同时避免重复。

2. 判定是否是真正解的方法。

3. 为了提高解决问题的效率，使可能解的范围将至最小。

（5）枚举算法的流程图如下所示：

先判断值是否在范围内，然后判断是否符合条件，最后输出或者取下一个值，直到结束，下面通过例题来学习一下这种算法思想。

二、枚举算法的实例

以下是一个使用枚举解题与优化枚举范围的例子。

例题：

一个数组中的数互不相同，求其中和为0的数对的个数。

解题思路：

枚举两个数的代码很容易就可以写出来。

// C++ Version
for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j)
    if (a[i] + a[j] == 0) ++ans;

# Python Version
for i in range(0, n):
  for j in range(0, n):
      if(a[i] + a[j] == 0):
          ans = ans + 1

来看看枚举的范围如何优化。由于题中没要求数对是有序的，答案就是有序的情况的两倍（考虑如果 (a, b) 是答案，那么 (b, a) 也是答案）。对于这种情况，只需统计人为要求有顺序之后的答案，最后再乘上2就好了。

不妨要求第一个数要出现在靠前的位置。代码如下：

// C++ Version
for (int i = 0; i < n; ++i)
  for (int j = 0; j < i; ++j)
    if (a[i] + a[j] == 0) ++ans;

# Python Version
for i in range(0, n):
  for j in range(0, i):
      if(a[i] + a[j] == 0):
          ans = ans + 1

不难发现这里已经减少了j 的枚举范围，减少了这段代码的时间开销。

我们可以在此之上进一步优化。

两个数是否都一定要枚举出来呢？枚举其中一个数之后，题目的条件已经确定了其他的要素（另一个数）的条件，如果能找到一种方法直接判断题目要求的那个数是否存在，就可以省掉枚举后一个数的时间了。较为进阶地，在数据范围允许的情况下，我们可以使用桶记录遍历过的数。

// C++ Version
bool met[MAXN * 2];
memset(met, 0, sizeof(met));
for (int i = 0; i < n; ++i) {
  if (met[MAXN - a[i]]) ans += 1;
  met[MAXN + a[i]] = true;
}

# Python Versionmet = [False] * MAXN * 2for i in range(0, n):
    if met[MAXN - a[i]]:
        ans = ans + 1
    met[a[i] + MAXN] = True