Skip to main content

2.1 枚舉介紹和全排列枚舉

  • 枚舉就是將所有答案的可能都跑過一次
  • 若有時候答案的可能樹太多，會導致超時，在這個單元中，就要學習如何以合理的時間複雜度找到答案

枚舉簡單題目

給定一個數字$n(1\leq n\leq 10^3)$問可以湊成幾對$a, b$買足$a\times b = n$?

  • 很直觀的做法，可以直接用$O(n^2)$的時間複雜度來完成 
    #include<iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
           if(i * j == n) {
                ans++;
           }
        }
    }
    cout << ans << endl;
    return 0;
}
  • 現在更改題目，將$n$的範圍改成$1\leq n\leq 10^5$，再去跑這個程式碼時，會發現程式遲遲跑不出結果來，因為很明顯地，$O(n^2)$會超時
  • 現在我們會有幾種想法
    1. 以這個$n$的大小，必須要用$O(n)$的時間複雜度才可能完成
    2. $a\times b = n$可以轉換成$a=\frac{n}{b}$
  • 用以上這兩種想法，相信你就可以想出如何使用$O(n)$解出這題了
  • 只需要枚舉$n$並看看$\frac{n}{b}$使否整除即可 
    #include<iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(n % i == 0) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}
  • 這個單元大部分時間都在學習如何將時間複雜度藉由特別的方法，改進到合理的範圍

全排列枚舉

  • 這種枚舉方法主要是要將所有排列都找出來，例如輸出所有$1~n$的排列
  • 在algorithm這個標頭檔中，有一個很好用的工具，稱作next_permutation
  • 他會將你給定的陣列找出下一個排列(以字典序排序)
  • 使用方法：next_permutation(左界(L), 右界(R))，接下來他就會針對這個左閉右開的區間做排列
  • 回傳值：若排列為字典序最大者，回傳0，反之，回傳1
  • 全排列枚舉裸題：Ex201
  • 記得要在上方引入algorithm標頭檔
  • 全排列枚舉程式碼 
    #include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int v[n];
    for(int i = 0; i < n; i++) {
        v[i] = i + 1;
    }
    do {
        for(int i = 0; i < n; i++) {
            cout << v[i] << ' ';
        }
        cout << endl;
    } while(next_permutation(v, v + n));
    return 0;
}

全排列枚舉例題

  • 題目連結：Ex202
  • 題目敘述：總共有$N$個城市，每個城市位於$(x_i, y_i)$，兩個城市之間的距離如下\[\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\]總共有$N!$種方法可以訪問所有城市，問你這$N!$的平均路徑長為和?
  • 這題很明顯的需要使用全排列枚舉去做，找到每一種排列方法後，再去計算總路徑長，即可求出平均值 
    #include<iostream>
#include<math.h>
#include<algorithm>
#include<iomanip>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int dx[n + 1], dy[n + 1];
    int cnt[n];
    for(int i = 0; i < n; i++) cnt[i] = i + 1;
    for(int i = 1; i <= n; i++) cin >> dx[i] >> dy[i];
    double ss = 0;
    int cc = 0;
    do
    {
        cc++;
        for(int i = 1; i < n; i++)
        {
            ss += sqrt((dx[cnt[i]] - dx[cnt[i - 1]]) * (dx[cnt[i]] - dx[cnt[i - 1]]) + (dy[cnt[i]] - dy[cnt[i - 1]]) * (dy[cnt[i]] - dy[cnt[i - 1]]));
        }
    } while (next_permutation(cnt, cnt + n));
    cout << fixed << setprecision(10) << ss / (double)cc << '\n';
    return 0;
}

練習題：P201給定一個字串請輸出此字串的所有排列方法

全排列枚舉應用

這是枚舉當中算最基礎的一個，務必要熟悉，以下提出幾點為常見的全排列枚舉應用

  • 求解數學問題：全排列枚舉可以用於求出各種數學問題，如排列組合、排列數學等。
  • 字串操作：全排列可以用於生成字串的所有排列。
  • 搜索問題：在搜索問題中，全排列枚舉可以用於生成搜索空間中的所有可能狀態，從而進行搜索和優化。
Back to top