Direct Method（Straightforward Method）

「直接法」，可以直接算出答案來的問題，例如導個公式算出答案、觀察得到答案、依照流程進行最後得到答案、直接印出答案，這些都算是「直接法」。

UVa 488 10055 10370 10878 10929

Trial and Error（Generate and Test）

「嘗試錯誤法」、「試誤法」，是針對答案進行Enumerate與Search的策略。有些困難的問題，難以直接推導答案，既然推導不出來，就慢慢測試答案、慢慢驗算吧──確立答案的範圍，窮舉所有可能的答案，再從中搜尋正確答案。

試誤法注重的是題目的限制條件，以及答案的數值範圍，這兩者直接影響到空間複雜度與時間複雜度。問題的限制越嚴苛，答案的數值範圍越小，那麼試誤法就會越簡單越快。

直接法和試誤法一陰一陽，互為正反。直接法是由題目本身下手，進而推導出答案；試誤法則是逆向思考，從答案來下手，進而迎合題目需求。

大部分的問題，都無法直接製作出一個計算流程直接算出答案；一個問題，也不一定只有恰好一個答案，而有各式各樣的答案。這種情況下，可以採用試誤法來解決問題。

UVa 10167 10125 296 846 714

舉例：Exhaustive Key Search（Brute Force Attack）

在密碼學領域，破解密碼最簡單的方法叫做「暴力攻擊」。不知道密碼規則的情況下，就無法直接推導正確密碼；只好以試誤法一一檢驗所有可能的密碼，從中找出正確密碼。

延伸閱讀：One-way Function

「單向函數」是一種特別的函數，給定輸入很容易算出輸出，但是給定輸出卻很難算出輸入。

舉例來說，令一個函數的輸入是兩個質數，輸出是兩個質數的乘積。給定兩個質數可以輕易的在多項式時間內算出乘積，然而給定兩質數的乘積卻需要指數時間才能完成質因數分解。

如果給定一個單向函數的輸入，求其輸出，就適合用直接法，套用函數快速算得答案；如果給定一個單向函數的輸出，求其輸入，就適合用試誤法，嘗試各種輸入並套用函數快速驗證答案。

Enumerate

「枚舉」、「列舉」。把目標物一筆一筆列出來，一邊瀏覽，一邊紀錄、計算。把所有東西都瀏覽過一遍後，就能收集到充分的資訊，進而解決問題。

舉例：枚舉一百個平方數

以直接法的角度來看，依序枚舉數字1到100，在枚舉的過程中，一邊將數字平方得到平方數。

void generate_squares() { for (int i=1; i<=100; i++) cout << i*i << "是平方數"; }

以試誤法的角度來看，依序枚舉數字1到∞，在枚舉的過程中，一邊判斷這些數字是不是平方數。

void generate_squares() { for (int i=1; i<=100*100; i++) { int sqrt_i = sqrt(i); if (sqrt_i * sqrt_i == i) cout << i << "是平方數"; } }

Search

「搜尋」。列出所有東西，瀏覽一遍，從中找出需要的部份。

實做程式時，可以一邊列出東西，一邊瀏覽，一邊判斷是不是想要的東西；也可以列出全部的東西之後，再進行瀏覽。一旦找到了、找完了所有想要的東西，搜尋就可以即刻停止。

舉例：找出數列裡的特定數字

一邊瀏覽數列，一邊尋找特定數字，一旦找到了一個，就停止搜尋。

int array[10] = {4, -2, 4, 100, 9, -34, 17, 23, 55}; bool find_number(int n) { bool found = false; for (int i=0; i<10; i++) // 瀏覽數列 if (array[i] == n) // 判斷是不是想要的東西 { found = true; break; } return found; } bool find_number(int n) { for (int i=0; i<10; i++) // 瀏覽數列 if (array[i] == n) // 判斷是不是想要的東西 return true; return false; }

舉例：找出數列裡的極大值

一邊瀏覽數列，一邊比較數值大小，最後就求出了極大值。

int array[10] = {4, -2, 4, 100, 9, -34, 17, 23, 55}; void find_maximum() { int max = -1e9; for (int i=0; i<10; i++) // 瀏覽數列 if (array[i] > max) // 比較大小 max = array[i]; cout << "最大值是" << max << endl; }

Enumerative Method

「枚舉法」、「窮舉法」、「列舉法」是Enumerate與Search兩種動作的結合，大意是：嘗試枚舉全部情形、全部數據，一一比對檢查。窮舉法的特色是，所有情況無一遺漏。

窮舉法充分利用了電腦能做快速運算的特性。窮舉對人類來說，是曠日費時的工作；對電腦來說，是駕輕就熟了。不容易揣摩出答案的問題，都可以用電腦做窮舉，迅速的揣摩各種情形，瞬間推導出正確答案。

1. 找出不確定的因素（變數）。
2. Enumerate：列出所有可能性。
3. Search：逐一判斷正確的要素（數值）。

實作窮舉法，可以用迴圈、遞迴、條列大量判斷式等等方式。

先整理再搜尋

資料有先整理的話，搜尋會變得容易又快速。

我們可以先將資料依照大小順序排序，或者先將資料置入特別的資料結構當中，讓資料具有特性；然後運用該特性，設計特別的演算法，略過不相關的資料，快速判斷出想要找的資料。例如排序後使用Binary Search，又例如將資料置入Hash Table再搜尋等等。

我們也可以直接依照資料大小進行窮舉，或者依照特殊順序進行窮舉，一邊窮舉一邊搜尋，也能達到整理的功效。

特殊的窮舉法

Backtracking
窮舉多維度的數據，以遞迴方式進行。

State Space Search
窮舉所有的狀態，並依照衍生關係整理成樹狀圖或者網狀圖，在圖上搜尋。

舉例：中途相遇法

舉例：交互前進法

UVa 972 10464