跳转至

枚舉

本頁面將簡要介紹枚舉算法。

簡介

枚舉（英語：Enumerate）是基於已有知識來猜測答案的一種問題求解策略。

枚舉的思想是不斷地猜測，從可能的集合中一一嘗試，然後再判斷題目的條件是否成立。

要點

給出解空間

建立簡潔的數學模型。

枚舉的時候要想清楚：可能的情況是什麼？要枚舉哪些要素？

減少枚舉的空間

枚舉的範圍是什麼？是所有的內容都需要枚舉嗎？

在用枚舉法解決問題的時候，一定要想清楚這兩件事，否則會帶來不必要的時間開銷。

選擇合適的枚舉順序

根據題目判斷。比如例題中要求的是最大的符合條件的素數，那自然是從大到小枚舉比較合適。

例題

以下是一個使用枚舉解題與優化枚舉範圍的例子。

例題

一個數組中的數互不相同，求其中和為 \(0\) 的數對的個數。

解題思路

枚舉兩個數的代碼很容易就可以寫出來。

1
2
3
for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j)
    if (a[i] + a[j] == 0) ++ans;

1
2
3
4
for i in range(n):
    for j in range(n):
        if a[i] + a[j] == 0:
            ans += 1

1
2
3
for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j)
    if (a[i] + a[j] == 0) ++ans;

來看看枚舉的範圍如何優化。由於題中沒要求數對是有序的，答案就是有序的情況的兩倍（考慮如果 (a, b) 是答案，那麼 (b, a) 也是答案）。對於這種情況，只需統計人為要求有順序之後的答案，最後再乘上 \(2\) 就好了。

不妨要求第一個數要出現在靠前的位置。代碼如下：

1
2
3
for (int i = 0; i < n; ++i)
  for (int j = 0; j < i; ++j)
    if (a[i] + a[j] == 0) ++ans;

1
2
3
4
for i in range(n):
    for j in range(i):
        if a[i] + a[j] == 0:
            ans += 1

1
2
3
for (int i = 0; i < n; ++i)
    for (int j = 0; j < i; ++j)
        if (a[i] + a[j] == 0) ++ans;

不難發現這裏已經減少了 \(j\) 的枚舉範圍，減少了這段代碼的時間開銷。

我們可以在此之上進一步優化。

兩個數是否都一定要枚舉出來呢？枚舉其中一個數之後，題目的條件已經確定了其他的要素（另一個數）的條件，如果能找到一種方法直接判斷題目要求的那個數是否存在，就可以省掉枚舉後一個數的時間了。較為進階地，在數據範圍允許的情況下，我們可以使用桶1記錄遍歷過的數。

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

1
2
3
4
5
met = [False] * (MAXN * 2 + 1)
for i in range(n):
    if met[MAXN - a[i]]:
        ans += 1
    met[a[i] + MAXN] = True

1
2
3
4
5
boolean[] met = new boolean[MAXN * 2 + 1];
for (int i = 0; i < n; ++i) {
    if (met[MAXN - a[i]]) ++ans;
    met[MAXN + a[i]] = true;
}

複雜度分析

  • 時間複雜度分析：對 \(a\) 數組遍歷了一遍就能完成題目要求，當 \(n\) 足夠大的時候時間複雜度為 \(O(n)\)。
  • 空間複雜度分析：\(O(n+\max\{|x|:x\in a\})\)。

習題

腳註

  1. 桶排序 以及 主元素問題 以及 Stack Overflow 上對桶數據結構的講解（英文） ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Early0v0, frank-xjh, Great-designer, ksyx, qiqistyle, Tiphereth-A , Saisyc, shuzhouliu, Xeonacid, xyf007
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用