Incremental Method

「遞增法」是符合電腦運作特性的方法。電腦執行程式，一次只做一個動作，完成了一件事才做下一件事。當一個問題太大太多時，化整為零、一個一個解決吧！

合抱之木，生於毫末；九層之臺，起於累土；千里之行，始於足下。謹以此句與大家共勉。

範例：加總數字

無論電腦再怎麼強，還是得一個一個累加數字。

void summation() { int array[5] = {3, 6, 9, -8, 1}; int sum = 0; for (int i=0; i<5; i++) sum += array[i]; cout << "總和是" << sum; } int summation(int array[], int n) { int sum = 0; for (int i=0; i<n; i++) sum += array[i]; return sum; }

範例：複製字串

無論電腦再怎麼強，還是得逐字複製。

void copy() { char s[15] = "incremental"; char t[15]; int i; for (i=0; s[i] != '\0'; i++) t[i] = s[i]; t[i] = '\0'; cout << "原本字串" << s; cout << "複製之後的字串" << t; } void copy(char* s, char* t) { int i; for (i=0; s[i]; i++) t[i] = s[i]; t[i] = '\0'; }

範例：選擇排序法（Selection Sort）

找到第一小的數字，放在第一個位置；再找到第二小的數字，放在第二個位置。一次找一個數字，如此下去就會把所有數字按照順序排好了。

void selection_sort() { int array[5] = {3, 6, 9, -8, 1}; for (int i=0; i<5; i++) { // 從尚未排序的數字當中，找到第i小的數字。 int min_index = i; for (int j=i+1; j<5; j++) if (array[j] < array[min_index]) min_index = j; // 把第i小的數字，放在第i個位置。 swap(array[i], array[min_index]); } // 印出排序結果。 for (int i=0; i<5; i++) cout << array[i]; } void selection_sort(int array[], int n) { for (int i=0; i<n; i++) { // 從尚未排序的數字當中，找到第i小的數字。 int min_index = i; for (int j=i+1; j<n; j++) if (array[j] < array[min_index]) min_index = j; // 把第i小的數字，放在第i個位置。 swap(array[i], array[min_index]); } }

範例：印出直角三角形

多字成行，多行成直角三角形。由細微的東西開始，一件一件組起來。

// 多字成行 void print_line(int n) // n 是一行的長度 { for (int i=1; i<=n; i++) cout << '@'; cout << '\n'; } // 多行成直角三角形 void print_triangle(int n) // n 是行數 { for (int i=n; i>=1; i--) print_line(i); }

UVa 488 10038 10107 10370

範例：人潮最多的時段（Interval Partitioning Problem）

一群訪客參加宴會，我們詢問到每一位訪客的進場時刻與出場時刻，請問宴會現場擠進最多人的時段。

換個視角。想像會場門口裝著一支監視器。有訪客進入，會場就多一人；有訪客離開，會場就少一人。如此就很容易統計會場人數。遞增的標的是時刻，而不是訪客。

【註：這個技巧在中文網路稱作「離散化」。】

struct Guest {int arrival, leave;} g[10]; bool cmp(int i, int j) { return abs(i) < abs(j); } void maximum_guest() { vector<int> time; for (int i=0; i<10; i++) { time.push_back(+g[i].arrival); time.push_back(-g[i].leave); } sort(time.begin(), time.end(), cmp); int n = 0, maximum = 0; for (int i=0; i<time.size(); i++) { if (time[i] >= 0) n++; else n--; maximum = max(maximum, n); } cout << "人潮最多的時段有" << maximum << "人"; }

此處僅找出人數。找出人潮最多的時段，就留給各位自行嘗試吧。

UVa 688 972 10613 10585 10963

UVa 308 837

範例：儲存座標

遞增的標的，主為點，次為座標軸。

struct Point {float x, y;} p[5] = { {0, 1}, {1, 2}, {3, 0}, {2, 2}, {3, 1} };

遞增的標的，主為座標軸，次為點。

float x[5] = {0, 1, 3, 2, 3}; float y[5] = {1, 2, 0, 2, 1};

範例：印出轉換成小寫的字串

有需要改變的，只有大寫字母──如果是大寫字母，就轉換成小寫字母並且印出；如果不是大寫字母，就直接印出。

void print_lowercase() { char s[15] = "Hello World!"; for (int i=0; s[i]; i++) if (s[i] >= 'A' && s[i] <= 'Z') cout << (char)(s[i] - 'A' + 'a'); else cout << s[i]; }

也可以一步一步進行：（一）複製一份字串（二）字串轉換成小寫（三）印出字串。

void print_lowercase() { char s[15] = "Hello World!"; char t[15]; // 第一波：複製一份字串 for (int i=0; s[i]; i++) t[i] = s[i]; // 第二波：字串轉換成小寫 for (int i=0; s[i]; i++) if (t[i] >= 'A' && t[i] <= 'Z') t[i] = t[i] - 'A' + 'a'; // 第三波：印出字串 cout << t; } void print_lowercase() { char s[15] = "Hello World!"; char t[15]; // 每一波的程式碼可以自行包裝成為函式， // 亦可套用標準函式庫。 my_copy(s, t); // 複製字串 my_lowercase(t); // 換成小寫 cout << t; // 印出字串 }

第一種解法稱作one-pass，資料只會讀取一遍。讀取資料的同時，也一口氣處理掉所有事情。

第二種解法稱作multi-pass，資料會重複讀取許多遍。所有事情劃分成數個階段，逐步處理，每個階段只專心處理一件事情。

one-pass的優點是：程式碼簡短、執行時間也短。缺點是：程式碼不易編修。

multi-pass的優點是：程式碼一目了然，容易編修、測試、除錯；程式碼可以包裝成為函式，也有機會套用標準函式庫。缺點是：需要額外的暫存記憶體。

這兩種方式各有利弊。程式員必須自行取捨。

範例：對調數字

利用一個變數，暫存其中一個數字，以便對調。

void swap_int() { int a = 0, b = 1; // 交換a與b int temp = a; a = b; b = temp; cout << a << ' ' << b; } void swap_int(int& a, int& b) { int temp = a; a = b; b = temp; }

範例：對調陣列

節省記憶體的方法：採用遞增法，逐一對調數字。

void swap_int_array() { int a[5] = {3, 6, 9, -8, 1}; int b[5] = {9, 8, 7, 6, 5}; // one-pass for (int i=0; i<5; i++) { int temp = a[i]; a[i] = b[i]; b[i] = temp; } }

浪費記憶體的方法：建立一條陣列，暫存其中一條陣列。

void swap_int_array() { int a[5] = {3, 6, 9, -8, 1}; int b[5] = {9, 8, 7, 6, 5}; // multi-pass int temp[5]; for (int i=0; i<5; i++) temp[i] = a[i]; for (int i=0; i<5; i++) a[i] = b[i]; for (int i=0; i<5; i++) b[i] = temp[i]; } void swap_int_array() { int a[5] = {3, 6, 9, -8, 1}; int b[5] = {9, 8, 7, 6, 5}; // multi-pass int temp[5]; my_copy(a, temp); my_copy(b, a); my_copy(temp, b); }

Memoization

「記憶法」是符合電腦運作特性的方法。電腦擁有大量儲存空間。只要將計算過的數值，儲存於記憶體，往後就能直接使用記憶體儲存的資料，不必再浪費時間重複計算一遍。

Memoization（Tabulation）
演算法執行過程之中，即時更新數值，儲存於記憶體。
例如堆疊的大小。

Precomputation（Precalculation）（Preprocessing）
演算法開始之時，預先計算數值，儲存於記憶體。
例如圓周率、字串的長度、質數的表格。

如果要儲存大量的、同性質的數值，我們可以將這些數值整理成一個表格（通常是陣列），以方便查閱──稱作「查詢表lookup table」。例如質數表便是一個「查詢表」。

範例：陣列大小

使用一個變數，記錄資料數量，以便迅速地增加資料。

void array_size() { int array[100]; int n = 0; // 使用一個變數，記錄資料數量。 array[n++] = 3; // 以便迅速地增加資料。 array[n++] = 6; array[n++] = 9; cout << n; }

C++標準函式庫的stack，事實上也額外隱含了一個變數，記錄資料數量。當堆疊塞入資料、彈出資料的時候，也就是呼叫push函式、呼叫pop函式的時候，就默默更新資料數量。

void stack_size() { stack<int> s; // C++標準函式庫的stack s.push(1); // 默默地n++ s.pop(); // 默默地--n cout << s.size(); // 把n印出來 }

範例：加總數字

利用一個變數，累計數字的總和。

void summation() { int array[5] = {3, 6, 9, -8, 1}; int sum = 0; for (int i=0; i<5; i++) sum += array[i]; cout << "總和是" << sum; } int summation(int array[], int n) { int sum = 0; for (int i=0; i<n; i++) sum += array[i]; return sum; }

範例：統計字母數量

建立26格的陣列，讓字母a到z依序對應陣列的每一格，作為lookup table。一邊讀取字串，一邊累計字母出現次數。

void count_letter_frequency() { char s[15] = "Hello World!"; int c[26] = {}; // 字母一律換成小寫 for (int i=0; s[i]; i++) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a'; // 統計字母數量 for (int i=0; s[i]; i++) if (s[i] >= 'a' && s[i] <= 'z') c[s[i] - 'a']++; // 印出統計結果 for (int i=0; i<26; i++) cout << char('a'+i) << ':' << c[i] << '\n'; }

UVa 10260 10082 10222 12626

範例：統計數字數量

當數字範圍太大，無法建立那麼大的陣列，可以改用hash table、binary search tree等等資料結構作為lookup table。

void histogram() { int array[10] = { 1, 3, 4, 10, 11, 1000000000, 23, 99, 123, 514 }; // int c[1000000000] = {}; map<int, int> c; // binary search tree // 統計數字數量 for (int i=0; i<10; i++) c[array[i]]++; // 印出統計結果 for (auto i: c) cout << i.first << ':' << i.second << '\n'; }

UVa 11572 141

範例：計數排序法（Counting Sort）

建立足夠長的陣列，讓數字對應陣列的每一格，作為lookup table。統計每個數字的出現次數。由小到大讀取lookup table，順便排序數字。

void counting_sort() { int array[5] = {3, 6, 9, 9, 1}; int c[9 + 1] = {}; // 統計數字數量 for (int i=0; i<5; i++) c[array[i]]++; // 由小到大讀取lookup table，順便排序數字。 for (int j=0, i=0; j<10 && i<5; j++) while (c[j] > 0) { c[j]--; array[i++] = j; } }

範例：求1到n的全部整數的立方和，n的範圍由1到10。

以直接的方式，累加每個立方數。（儘管這個問題有公式解，但是為了方便舉例，所以這裡不採用公式解。）

int sum_of_cubes(int n) { int sum = 0; for (int i=1; i<=n; i++) sum += i * i * i; return sum; } void print_sum_of_cubes() { int n; while (cin >> n && n > 0) cout << sum_of_cubes(n); }

使用Memoization。建立11格的陣列，每一格依序對應0到10的立方數，作為lookup table。一旦計算完畢，就儲存至表格；往後就直接讀取表格，不需重複計算。

int sum_of_cubes(int n) { // 其值為 0 表示沒有存入答案 static int answer[10 + 1] = {}; // 如果已經計算過，就直接讀取表格的答案。 if (answer[n] != 0) return answer[n]; // 如果不曾計算過，就計算一遍，儲存答案。 int sum = 0; for (int i=1; i<=n; i++) sum += i * i * i; return answer[n] = sum; } void print_sum_of_cubes() { int n; while (cin >> n && n > 0) cout << sum_of_cubes(n); }

使用Preprocessing。

void print_sum_of_cubes() { // 預先建立立方數表格 int cube[10 + 1]; for (int i=1; i<=10; i++) cube[i] = i * i * i; int n; while (cin >> n && n > 0) { // 直接讀取表格的立方數 int sum = 0; for (int i=1; i<=n; i++) sum += cube[i]; cout << sum; } }

Preprocessing當然也可以直接算答案啦。

int sum_of_cubes(int n) { int sum = 0; for (int i=1; i<=n; i++) sum += i * i * i; return sum; } void print_sum_of_cubes() { // 預先計算所有答案 int answer[10 + 1]; for (int i=1; i<=10; i++) answer[i] = sum_of_cubes(i); // 直接讀取表格的答案 int n; while (cin >> n && n > 0) cout << answer[n]; }

最後是Preprocessing的極致。

void print_sum_of_cubes() { // 預先計算答案，寫死在程式碼裡面。 int answer[10 + 1] = { 0, 1, 9, 36, 100, 225, 441, 784, 1296, 2025, 3025 }; // 直接讀取表格的答案 int n; while (cin >> n && n > 0) cout << answer[n]; }

UVa 10738 10894

範例：印出方框

建立二維陣列：陣列的格子，依序對應視窗的文字。

不直接印出方框，而是間接填至陣列。不必數空白鍵，只需兩條水平線和兩條垂直線。

void print_square_border() { // 建立記憶體 char array[5][5]; // 預先填入空白鍵 for (int i=0; i<5; i++) for (int j=0; j<5; j++) array[i][j] = ' '; // 填入方框：兩條水平線、兩條垂直線 // 即便相互重疊也無所謂 for (int i=0; i<5; i++) array[0][i] = '@'; for (int i=0; i<5; i++) array[4][i] = '@'; for (int i=0; i<5; i++) array[i][0] = '@'; for (int i=0; i<5; i++) array[i][4] = '@'; // 印出方框 for (int i=0; i<5; i++) { for (int j=0; j<5; j++) cout << array[i][j]; cout << '\n'; } }

UVa 105 706

範例：拆開迴圈（Loop Unrolling）

迴圈語法的功能是：一段指令，重覆實施數次，但是每次都稍微變動一點點。

事實上，我們可以反璞歸真，拆開迴圈，還原成數行指令。如此一來，就節省了迴圈每次累加變數的時間，也節省了迴圈每次判斷結束條件的時間。

拆開迴圈是一種Preprocessing，預先計算迴圈變量、預先計算迴圈結束條件。

拆開迴圈之後，雖然降低了程式的執行時間，但是也降低了程式可讀性。程式員必須自行取捨。

Enumeration

「枚舉法」利用了電腦無與倫比的計算速度。找到不確定的變數，枚舉所有可能性，逐一判斷正確性。

Enumerate
一筆一筆列出所有資料。
對應到程式語言的for。

Search
瀏覽所有資料，找出需要的部份。
對應到程式語言的for加if。

收集充分資訊，就能解決問題。

範例：枚舉一百個平方數

採用直接法：依序枚舉數字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 << "是平方數"; } }

範例：尋找陣列裡的最小值

由小到大枚舉陣列索引值，逐一比較陣列元素。

void find_minimum() { int array[5] = {3, 6, 9, -8, 1}; int min = 2147483647; for (int i=0; i<5; i++) // 枚舉索引值 if (array[i] < min) // 比較元素 min = array[i]; // 隨時記錄最小值 cout << "最小的數字是" << min; } int find_minimum(int array[], int n) { int min = 2147483647; for (int i=0; i<n; i++) // 枚舉索引值 if (array[i] < min) // 比較元素 min = array[i]; // 隨時記錄最小值 return min; }

範例：尋找陣列裡的特定數字（Sequential Search）

找到所有特定數字：瀏覽一遍所有數字。

void find_all_number() { int array[5] = {3, 6, 9, -8, 1}; for (int i=0; i<5; i++) // 枚舉 if (array[i] == 6) // 搜尋 cout << i << ':' << array[i] << '\n'; }

找到其中一個特定數字：一旦找到，立即停止瀏覽，以節省時間。

void find_number() { int array[5] = {3, 6, 9, -8, 1}; for (int i=0; i<5; i++) // 枚舉 if (array[i] == 6) // 搜尋 { cout << i << ':' << array[i]; break; } } int find_number(int array[], int n, int num) { for (int i=0; i<n; i++) if (array[i] == num) return i; return -1; }

範例：尋找二維陣列裡的特定數字

多個元素成為一個橫條、多個橫條成為一個陣列。內層先枚舉元素，外層再枚舉橫條，就能枚舉所有元素。

方才是由內而外、由小到大進行思考，其實也可以由外而內、由大到小進行思考：外層先枚舉每一個橫條，內層再枚舉一個橫條的每一個元素，就能枚舉所有元素。

bool find_number(int n) { int array[3][5] = { {3, 6, 9, -8, 1}, {2, 4, 6, 8, 10}, {11, 7, 5, 3, 2} }; // 外層枚舉每一個橫條 for (int i=0; i<3; i++) // 內層枚舉一個橫條的每一個元素 for (int j=0; j<5; j++) // 就能枚舉所有元素 if (array[i][j] == n) return true; return false; }

此處再介紹一種特別的思考方式：第一層枚舉每一個橫條，第二層枚舉每一個直條，就能枚舉所有直條與橫條的交錯之處。

雖然前後兩個思考方式完全不同，但是前後兩支程式碼卻完全相同。

bool find_number(int n) { int array[3][5] = { {3, 6, 9, -8, 1}, {2, 4, 6, 8, 0}, {7, 5, 3, 2, 1} }; // 第一層枚舉每一個橫條 for (int i=0; i<3; i++) // 第二層枚舉每一個直條 for (int j=0; j<5; j++) // 就能枚舉所有橫條與直條交錯之處 if (array[i][j] == n) return true; return false; }

範例：平面上距離最近的兩個點（Closest Pair）

第一層枚舉第一個點，第二層枚舉第二個點。為了避免重複枚舉相同的一對點，第二層只枚舉索引值更高的點。

void closest_pair() { float point[10][2] = { {3, 3}, {1, 5}, {4, 6}, {2, 8}, {9, 9}, {2, 1}, {7, 2}, {6, 5}, {9, 4}, {5, 9} }; // 距離最近的兩個點的距離 float d = 1e9; // 枚舉第一點 for (int i=0; i<10; i++) // 枚舉第二點 for (int j=i+1; j<10; j++) { // 計算第一點到第二點的距離 float dx = point[i][0] - point[j][0]; float dy = point[i][1] - point[j][1]; float dij = sqrt(dx * dx + dy * dy); // 記錄最短的距離 if (dij < d) d = dij; } cout << "距離是" << d; }

可以把計算距離的程式碼，抽離出來成為一個函式。好處是程式碼變得清爽許多，增加程式碼可讀性。壞處是大量呼叫函式，導致執行時間變長。

struct Point {float x, y;}; // 計算兩點之間的距離 float dist(Point a, Point b) { float dx = a.x - b.x; float dy = a.y - b.y; return sqrt(dx * dx + dy * dy); } void closest_pair() { Point point[10] = { {3, 3}, {1, 5}, {4, 6}, {2, 8}, {9, 9}, {2, 1}, {7, 2}, {6, 5}, {9, 4}, {5, 9} }; float d = 1e9; for (int i=0; i<10; i++) for (int j=i+1; j<10; j++) // 記錄最短的距離 d = min(d, dist(point[i], point[j])); cout << "距離是" << d; }

魚與熊掌不可兼得，這兩種程式碼各有優缺點，沒有絕對的好壞。程式員必須自行取捨。

範例：字串搜尋（String Searching）

從長字串之中，找到短字串的出現位置。

第一層先枚舉所有可以對齊的位置，第二層再枚舉所有需要對齊的字元。

void string_searching() { char text[15] = "It's a pencil."; char pattern[6] = "a pen"; // 枚舉所有可以對齊的位置 for (int i=0; i<15; i++) { // 枚舉所有需要對齊的字元 bool find = true; for (int j=0; j<5; j++) if (text[i+j] != pattern[j]) find = false; if (find) cout << "短字串出現在第" << i << "個字元"; } }

因為短字串不會超出長字串末段，所以第一層枚舉範圍可以再略微縮小。

因為只要一個相異字元，就足以表明對齊位置錯誤，所以第二層的枚舉過程可以提早結束。

void string_searching() { char text[15] = "It's a pencil."; char pattern[6] = "a pen"; // 仔細估量枚舉範圍 for (int i=0; i<15-6+1; i++) { bool find = true; for (int j=0; j<5; j++) if (text[i+j] != pattern[j]) { find = false; break; } if (find) cout << "短字串出現在第" << i << "個字元"; } }

範例：統計字母數量

第一層先枚舉26種英文字母，第二層再枚舉字串的所有字元，計算一種字母的數量。

void count_letter() { char s[15] = "Hello World!"; // 字母統一換成小寫 for (int i=0; s[i]; i++) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a'; // 枚舉26種英文字母 for (int i=0; i<26; i++) { // 枚舉字串的所有字元 int c = 0; for (int j=0; s[j]; j++) if (s[j] == 'a' + i) c++; // 印出一種字母的數量 cout << (char)('a' + i) << ':' << c; } }

先前曾經介紹過統計字母數量的範例。先前範例當中，雖然耗費記憶體空間，但是執行時間短──簡單來說就是空間大、時間小。此處範例當中，則是空間小，時間大，恰恰相反。這兩種方式各有優缺點，程式員必須自行取捨。

範例：反轉字串

兩個枚舉，一個從頭到尾，一個從尾到頭，步調相同，逐步對調字元。雖然是兩個枚舉，卻只有一個迴圈。

void reverse_string() { char s[15] = "Hello World!"; // 兩個枚舉，一個從頭到尾，一個從尾到頭。 for (int i=0, j=12; i<j; i++, j--) swap(s[i], s[j]); cout << "反轉之後的字串是" << s; } void reverse(char* s) { int n = strlen(s); for (int i=0; i<n/2; i++) swap(s[i], s[n-1-i]); }

UVa 1595

範例：尋找總和為10的區間

假設陣列元素只有正數。

兩個枚舉，枚舉區間左端以及枚舉區間右端，都是從頭到尾，保持一左一右，視情況輪流枚舉。雖然是兩個枚舉，卻只有一個迴圈。

void find_interval() { int array[5] = {3, 6, 1, 7, 2}; int sum = 0; for (int i=0, j=-1; j<5; ) // 枚舉區間[i, j] { if (sum > 10) { // 總和太大，區間左端往右縮短。 sum -= array[i]; i++; } else if (sum < 10) { // 總和太小，區間右端往右伸長。 j++; sum += array[j]; } else if (sum == 10) { // 總和剛好， // 區間左端往右縮短， // 亦得區間右端往右伸長。 // 任選一種皆可。 // sum -= array[i]; // i++; j++; sum += array[j]; } if (sum == 10) cout << '[' << i << ',' << j << ']'; } } void find_interval(int array[], int n, int num) { int sum = 0; for (int i=0, j=0; j<=n; ) // 枚舉區間[i, j) { if (sum > num) sum -= array[i++]; else sum += array[j++]; if (sum == num) cout << '[' << i << ',' << j-1 << ']'; } }

讀者可以想想看：陣列元素若有零、有負數，是否要調整枚舉方式？

UVa 972 10464 11536 11572

範例：尋找陣列之中的最小值，陣列已經由小到大排序

找到其中一個最小值：經常整理房間，尋找東西就快；預先排序資料，搜尋速度就快。

void find_minimum() { int array[5] = {3, 3, 6, 6, 9}; cout << "最小的數字是" << array[0]; }

找到所有最小值：讀者請自行嘗試。

範例：尋找陣列之中的特定數字，陣列已經由小到大排序

找到其中一個特定數字：首先找到陣列中央的數字，依其數字大小，繼續搜尋左半段或者右半段。

void find_number() { int array[15] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 }; int left = 0, right = 15-1; while (left <= right) { int mid = left + (right - left) / 2; if (array[mid] < 29) left = mid + 1; // 繼續搜尋剩下的右半段 else if (array[mid] > 29) right = mid - 1; // 繼續搜尋剩下的左半段 else if (array[mid] == 29) { // 找到了其中一個數字 cout << mid << ':' << array[mid]; return; } } cout << "找不到29"; }

找到所有特定數字：讀者請自行嘗試。

範例：平面上距離最近的兩個點（Closest Pair）

找到距離最近的其中一對點：預先依照X座標排序所有點，搜尋得以略過大量情況。

struct Point {float x, y;}; // 計算兩點之間的距離 float dist(Point a, Point b) { float dx = a.x - b.x; float dy = a.y - b.y; return sqrt(dx * dx + dy * dy); } bool cmp(Point a, Point b) { return a.x < b.x; } void closest_pair() { Point point[10] = { {3, 3}, {1, 5}, {4, 6}, {2, 8}, {9, 9}, {2, 1}, {7, 2}, {6, 5}, {9, 4}, {5, 9} }; // 依照X座標排序所有點 sort(point, point+10, cmp); float d = 1e9; for (int i=0; i<10; i++) for (int j=i+1; j<10; j++) { // 兩個點的X座標已經相距太遠，直接略過， // 繼續枚舉下一個左端點。 if (point[j].x - point[i].x > d) break; d = min(d, dist(point[i], point[j])); } cout << "距離是" << d; }

找到距離最近的每一對點：讀者請自行嘗試。

範例：英文單字從單數變複數

枚舉各種情況，寫成大量判斷式。

void plural(string s) { int n = s.length(); if (s.back() == 'y') cout << s.substr(0, n-1) << "ies"; else if (s.back() == 's' || s.back() == 'x') cout << s << "es"; else if (s.substr(n-2) == "sh" || s.substr(n-2) == "ch") cout << s << "es"; else if (s.substr(n-3) == "man") cout << s.substr(0, n-3) << "men"; else cout << s << 's'; }

範例：小畫家倒墨水（Flood Fill Algorithm）

電腦圖片可以想成是一張方格紙，每個方格都填著一種顏色。現在要實現小畫家倒墨水的功能：以某一格為起點，只要相鄰方格顏色一樣，就染成同一個顏色。

運用大量指令，枚舉上下左右四個方向；運用遞迴，枚舉相鄰同色方格。

必須避免已經枚舉過的方格又重複枚舉，否則程式在有生之年都不會結束。

int image[10][10]; // 圖片的大小為 10x10 void flood(int x, int y, int new_color, int old_color) { if (x>=0 && x<10 && y>=0 && y<10) // 不能超出邊界 if (image[x][y] == old_color) // 同色方格才枚舉 { // 染色 image[x][y] = new_color; // 枚舉上下左右四個方向 flood(x+1, y, new_color, old_color); flood(x-1, y, new_color, old_color); flood(x, y+1, new_color, old_color); flood(x, y-1, new_color, old_color); } } void ink() { // 在座標(7,6)的方格，淋上1號顏色。 flood(7, 6, 1, image[7][6]); }

大量指令，亦得寫成一個迴圈。

void flood(int x, int y, int new_color, int old_color) { if (x>=0 && x<10 && y>=0 && y<10) if (image[x][y] == old_color) { image[x][y] = new_color; // 寫成一個迴圈 for (int i=0; i<4; i++) { static int dx[4] = {1, -1, 0, 0}; static int dy[4] = {0, 0, 1, -1}; flood(x + dx[i], y + dy[i], new_color, old_color); } } }

多層判斷式，亦得拆解成一層一層的判斷式。

void flood(int x, int y, int new_color, int old_color) { if (!(x>=0 && x<10 && y>=0 && y<10)) return; if (image[x][y] != old_color) return; image[x][y] = new_color; for (int i=0; i<4; i++) { static int dx[4] = {1, -1, 0, 0}; static int dy[4] = {0, 0, 1, -1}; flood(x + dx[i], y + dy[i], new_color, old_color); } }

UVa 260 280 352 469 572 601 657 776 782 784 785 871 10267 10336 10946

ICPC 4792 5130

範例：三維函數繪圖

當問題太過困難，就增加限制，將部分變數改成常數。

一、固定X值，計算Y值Z值；嘗試各種X值。

二、固定Y值，計算X值Z值；嘗試各種Y值。

三、固定Z值，計算X值Y值；嘗試各種Z值。

Straightforward Method / Trial and Error

「直接法」，直接算出答案。例如按照流程進行得到答案、套用公式計算答案、直接印出答案。

UVa 488 10055 10370 10878 10929

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

UVa 10167 10125 296 846 714

直接法和試誤法剛好相反。直接法是由題目本身下手，推導答案；試誤法則是從答案下手，讓答案迎合題目需求。

範例：印出直角三角形

先前介紹直接法，現在介紹試誤法。

窮舉一個正方形的所有位置，一一判斷是否屬於三角形區域。

void print_triangle(int n) { for (int i=0; i<n; i++) { for (int j=0; j<n; j++) if (i + j < n) cout << '@'; cout << '\n'; } }

範例：印出方框

先前介紹直接法，現在介紹試誤法。

窮舉一個正方形的所有位置，一一判斷是否屬於方框區域。

void print_square_border(int n) { for (int i=0; i<n; i++) { for (int j=0; j<n; j++) if (i == 0 || i == n-1 || j == 0 || j == n-1) cout << '@'; else cout << ' '; cout << '\n'; } }

Backtracking

「回溯法」。枚舉多維度數值的方法。

由於內容較多較雜，另以專門頁面介紹。

Iterative Method

繁中「疊代法」、簡中「迭代法」、本站「遞推法」。不斷利用目前求得的數值，再求得新數值。

UVa 997

範例：字串變整數

直覺的方式是遞增法。個、十、百、千、萬、……，每個位數分別乘上10的次方，通通加起來。此處按照高位數到低位數的順序進行處理，以符合字串的儲存順序。

// 計算字串長度 int string_length(char* s) { int n = 0; while (s[n]) n++; return n; } // 計算10的exp次方 int pow10(int exp) { int n = 1; for (int i=0; i<exp; i++) n *= 10; return n; } void string_to_integer() { char s[10] = "26962869"; // 預先計算字串長度。 int length = string_length(s); // 依序處理高位數到低位數。 int n = 0; for (int i=0; i<length; i++) n += (s[i] - '0') * pow10(length - 1 - i); cout << n; }

更好的方式是遞推法！由高位數到低位數、也就是由左到右讀取字串，每讀取一個字元，就將數值乘以十、加上當前字元的對應數字。

void string_to_integer() { char s[10] = "26962869"; int n = 0; for (int i=0; s[i]; i++) n = n * 10 + s[i] - '0'; cout << n; }

同一個問題，有著不同的解法。有著程式碼很長、執行時間很長的方法，也有著程式碼很短，執行時間很短的方法。一支程式的好壞，除了取決於正確性和可讀性之外，同時也取決於計算方法。

UVa 759

範例：多項式函數求值（Horner's Rule）

多項式函數，代入數值。一乘一加，不斷更迭，求得函數值。完全不需要次方運算。

範例：除法

不斷乘以十、除以除數，就是一種遞推。

範例：牛頓法（Newton's Method）

找到連續函數等於零的位置。一開始隨便設定一個位置，不斷利用斜率求出下一個位置，就是一種遞推。

Xn+1 = Xn - f(Xn) / f'(Xn)

範例：3n+1猜想（Collatz Conjecture）

猜想的內容是這樣的：有一個整數，如果是偶數，就除以2；如果是奇數，就乘以3再加1。一個整數不斷這樣操作下去，最後一定會變成1。這個操作的過程就是一種遞推。

至今尚未有人能夠證明其正確性。有趣的是，目前也尚未檢查出任何反例。

UVa 100 371 694

範例：生命遊戲（Cellular Automaton）

一個二維的方格平面，每個格子都有一個細胞，可能是活的，可能是死的。細胞的生命狀況，隨時間變動，變動規則如下：

復活：一個死細胞，其八個鄰居，有三個活細胞，則下一刻復活。
存活：一個活細胞，其八個鄰居，有兩個或三個活細胞，則下一刻存活。
死於孤單：一個活細胞，其八個鄰居，只有零個或一個活細胞，則下一刻死亡。
死於擁擠：一個活細胞，其八個鄰居，有四個以上活細胞，則下一刻死亡。

實作時，我們可以弄兩張地圖，第一張地圖儲存現在這個時刻的狀態，第二張地圖儲存下一個時刻的狀態。兩張地圖交替使用，以節省記憶體空間。

實作時，我們可以切割概念、包裝成函式，讓程式碼易讀。

至今尚未有人能夠預測細胞最終會滅亡或延續。

// 印出狀態 void print_board(bool board[5][5]) { for (int x=0; x<5; ++x) { for (int y=0; y<5; ++y) cout << (board[x][y] ? '@' : ' '); cout << '\n'; } cout << '\n'; } // 八個鄰居中，還活著的細胞數目。 int count_neighbor(int x, int y, bool board[5][5]) { static const int dx[8] = {-1,-1,-1,0,0,1,1,1}; static const int dy[8] = {-1,0,1,-1,1,-1,0,1}; int n = 0; for (int i=0; i<8; ++i) { int mx = x + dx[i]; int my = y + dy[i]; if (mx >= 0 && mx < 5 && my >= 0 && my < 5) n += board[mx][my]; } return n; } // 判斷細胞死活 void go(int x, int y, bool board[5][5], bool next[5][5]) { int n = count_neighbor(x, y, board); if (!board[x][y]) if (n == 3) // 復活 next[x][y] = true; else // 仍舊死亡 next[x][y] = board[x][y]; else if (n == 2 || n == 3) // 存活 next[x][y] = true; else if (n == 0 || n == 1) // 死於孤單 next[x][y] = false; else if (n >= 4) // 死於擁擠 next[x][y] = false; } // 清空細胞 void clear_board(bool board[5][5]) { for (int x=0; x<5; ++x) for (int y=0; y<5; ++y) board[x][y] = false; } // 預先設定一些活的細胞 void load_board(bool board[5][5]) { board[3][1] = true; board[3][2] = true; board[3][3] = true; board[2][3] = true; board[1][2] = true; } void cellular_automaton() { bool board[2][5][5] = {}; clear_board(board[0]); load_board(board[0]); print_board(board[0]); // 遞推四回合 for (int t=0; t<4; ++t) { for (int x=0; x<5; ++x) for (int y=0; y<5; ++y) go(x, y, board[t%2], board[(t+1)%2]); print_board(board[(t+1)%2]); } }

UVa 447 457 10443 10507

範例：蘭頓的螞蟻（Langton's Ant）

跟生命遊戲相似，不過這個遊戲更神奇。

一、格子有黑與白兩種顏色。
二、螞蟻走入白格則右轉，走入黑格則左轉。
三、螞蟻離開格子時，格子顏色顛倒。

驚人的是，乍看完全沒有規律的路線，卻在10647步之後開始循環。原因至今不明。

UVa 11664 ICPC 7478 7479

範例：數學歸納法（Mathematical Induction）

數學歸納法的第二步驟，就是證明可不可以遞推！第二步驟的證明過程中一定會用到遞推！

1. 先證明 n = 1 成立。（有時候不見得要從1開始。）
2. 假設 n = k 成立，證明 n = k+1 也會成立。

當 1. 2. 得證，就表示 n = 1 ... ∞ 全部都成立。

範例：插入排序法（Insertion Sort）

從表面上來看，這是遞增法與枚舉法：第一層是遞增法，逐一把每個數字插入到左方已排序的陣列。第二層是枚舉法，搜尋插入位置；再將大量數字往右挪，以騰出空間插入數字。

但是從另一個視角來看，利用目前排序好的陣列，再求出更長的陣列，其實就是遞推法。

範例：以試除法建立質數表

從表面上來看，這是兩層的枚舉法：第一層先枚舉正整數，一一試驗是否為質數；第二層再枚舉所有已知質數，一一試除。

但是從另一個視角來看，利用目前求得的質數，再求出更多質數，其實就是遞推法。

範例：十分逼近法

數線分割成十等份區間，從中找出正確區間，把對應的小數位數添到答案末端，然後不斷十等分下去。

利用目前求得的小數，再求出更多的小數，其實就是遞推法。

範例：書塔（Book Stacking Problem）

將書本一本一本疊起來，成為一座斜塔，越斜越好。

對於任何一本書來說，其上方所有書本的整體重心，必須落在這本書上，這本書才能平穩地支撐住上方所有書本。

將書本插入到書塔底部，讓書塔的重心落在書本邊緣，就可以讓書塔最斜。插入書本到書塔底部之後，就更新書塔的重心位置，以便稍後插入下一本書本。

不斷插入書本到書塔底部、更新書塔重心，運用先前的書塔求得新的書塔──這段過程就是一種遞推。

範例：交卷

考試結束了，學生要交卷，老師要收卷。大家將手上的考卷，不斷傳遞給其他人，不斷匯集給老師。一個人不能同時交卷和收卷，一個人不能同時交卷給多人（搗亂），一個人不能同時向多人收卷（手忙腳亂）。假設每個人交卷速度一致，請讓整個過程越短越好。

每個人隨時都在收卷交卷，一定最省時。老師亦然，一直處於收卷狀態，一定最省時。

遞增的標的，選定為老師。老師每次收卷，直接複製貼上前面幾次收卷的部屬方式，是最好的──這段過程就是一種遞推。

Recursive Method

繁中「遞迴法」、簡中「递归法」、本站「遞歸法」。重複運用相同手法，縮減問題範圍，直到釐清細節。

UVa 10994 10212 10471 10922

範例：碎形（Fractal）

利用相同手法繪圖，繪圖範圍越來越精細。

圖中的碎形稱作Sierpinski triangle。凡是尖端朝上的正三角形，就在當中放置一個尖端朝下的正三角形；放置之後，圖形就變得更細膩，範圍就變得更小了。

圖中的碎形稱作Kosh snowflake。一條邊三等分，去除中段，朝外補上兩段，形成尖角。

圖中的碎形稱作Pythagoras tree。不斷繪製正方形、直角三角形，看起來像是一棵茂密的樹。

UVa 177 10609

範例：質因數分解（Integer Factorization）

不斷抽取出質因數，使數值不斷變小，直到成為質因數。

範例：L形磁磚

有一個邊長為2的3次方的正方形，右上角缺了一角邊長為1的正方形。現在要以L形磁磚貼滿這個缺了一角的正方形，該如何貼呢？

巧妙地將一塊L形磁磚放在中央的位置，就順利的把正方形切成四個比較小的、亦缺了一角的正方形。接下來只要遞迴處理四個小正方形，就解決問題了。

這個問題也可以改成缺口在任意一處，各位可以想想看怎麼解。

UVa 10230

範例：輾轉相除法（Euclid's Algorithm）

兩個數字輪流相除、求餘數，最後就得到最大公因數（greatest common divisor, gcd）。相信大家小時候都有學過。

我們可以把最大公因數想像成磚塊、把兩個數字都看成是最大公因數的倍數。

兩數相減所得的差值，一定是最大公因數的倍數。更進一步來說，兩數相除所得的餘數，一定是最大公因數的倍數。輾轉相除法的過程當中，兩數自始至終都是最大公因數的倍數。

運用這個性質，我們把兩數相除、求餘數，使得原始數字不斷縮小，直到得到最大公因數。真是非常巧妙的遞歸法！

// 運用程式語言的迴圈語法。 int gcd(int a, int b) { // 令 a 比 b 大，比較容易思考。 while (b != 0) { int t = a % b; a = b; b = t; } return a; } // 運用程式語言的遞迴語法。 int gcd(int a, int b) { // 令 a 比 b 大，比較容易思考。 if (b == 0) return a; else return gcd(b, a % b); }

注意到：遞推法、遞歸法，不等於程式語言的迴圈、遞迴。遞推法、遞歸法是分析問題的方法，用來得到計算過程、用來得到演算法。至於編寫程式時，我們可以自由地採用迴圈或者遞迴。

範例：過橋問題（Bridge and Torch Problem）

月黑風高的夜晚，有一座不長不短的獨木橋，只能同時容兩人併行。

此時正好有四個寂寞難耐、悲苦淒涼，事實上是窮極無聊的四個人路經此地。他們手邊僅帶著一支手電筒，想要通過這危險的獨木橋。那橋下可是暗潮洶湧，一失足成千古恨，奔流到海不復回。

幸好四人閒閒沒事就常走這座橋，對路況簡直熟悉到不行，閉著眼睛走都可以，於是乎四人知道自己過橋分別需時1分鐘、2分鐘、5分鐘、10分鐘。但是不管他們的腳程不可思議的快、莫名其妙的慢，四人都是貪生怕死之徒，要是手上沒有握著手電筒，誰都不敢過橋；四人也都是視財如命之徒，就是誰也不想浪費錢，去附近的便利商店買支手電筒，寧可摔到水裡隨波逐流環遊世界去。

最後他們只好協議說，一次兩人同時持手電筒過橋，再請其中一人送回手電筒，沒事做的人就在橋邊哭爹喊娘等手電筒回來，如此一來四人最終都能夠順利過橋。

兩人同時過橋時必須配合走得慢的人的速度，請問全員過橋最快要多久時間？

有一些規矩你是知道的，例如不能把手電筒用丟的丟過河，不能四個人疊羅漢一起過橋，不能把橋拆了做木筏之類的。

題目終於說完了，現在來談解題手法：

腳程快的人送手電筒回來那是最好的；相對地，腳程慢的人就應該讓他留在彼岸不要回來。不管先走後走，人人都還是要過橋，所以先試試看把腳程最慢的人送到對岸吧！

當人數眾多，至少四人時，令A與B是最快與次快，C與D是次慢與最慢。讓最慢的兩個人過橋主要有兩種方式，第一種是AB去A回、CD去B回，第二種是AD去A回、AC去A回，至於其它方式所花的時間恰好跟這兩種方式一樣。採用比較快的那一種方式，讓最慢的兩個人過橋之後，問題範圍就縮小了。

// 每個人的過橋時間，從小到大排序。 int a[8] = {1, 2, 5, 10, 15, 16, 30, 31}; void bridge_and_torch() { int n, t = 0; for (n=8-1; n>=3; n-=2) { int t1 = a[0] + a[1]*2 + a[n]; int t2 = a[0]*2 + a[n-1] + a[n]; t += min(t1, t2); } if (n == 2) t += a[0] + a[1] + a[2]; else if (n == 1) t += a[1]; else t += a[0]; cout << "所有人過橋的總時間為" << t; }

UVa 10037

範例：組合（Combination）

從N個人抓M個人出來組團，有哪些組團方式呢？

N個人當中的其中一個人，叫做甲君好了。我們將所有組團方式分類成兩種情形：甲君在團中、甲君不在團中。兩種情形綜合起來就是答案。

甲君在團中：演變成剩下N-1個人還要抓M-1個人出來組團。

甲君不在團中：演變成剩下N-1個人仍要抓M個人出來組團。

兩種情形正好等同原問題，問題範圍縮小了，形成遞歸。

// 累計所有組團方式 // 順帶一提，更好的做法是Dynamic Programming。 int combination(int n, int m) { if (n < m) return 0; if (m == 0) return 1; return combination(n-1, m-1) + combination(n-1, m); } // 列出所有組團方式 // 順帶一提，更好的做法是Backtracking。 void combination(int n, int m, vector<int> group) { if (n < m) return; if (m == 0) { for (int people: group) cout << people << ' '; cout << '\n'; return; } // 甲君不在團中 combination(n-1, m, group); // 甲君在團中 group.push_back(n); combination(n-1, m-1, group); }

範例：河內塔（Tower of Hanoi）

三根柱子、一疊盤子，盤子大小皆不同。盤子中間還得打個洞，這樣盤子才能穿在柱子上。所有盤子都疊在第一根柱子，大的在下面，小的在上面。現在要將整疊盤子移到第三根柱子。每次只能搬動一個盤子到別根柱子，而且大的盤子一定要保持在小的盤子下面。

想要移動最大的盤子到第三根柱子，必須先挪開上方整疊盤子到第二根柱子。移動上方整疊盤子，正好等同原問題，問題範圍縮小了，形成遞歸。

解題過程因而簡化成三個步驟：一、上方整疊盤子移到第二根柱子；二、最大的盤子移到第三根柱子；三、方才的整疊盤子移到第三根柱子。

// 累計步驟數量 int tower_of_hanoi(int n) { if (n == 0) return 0; return tower_of_hanoi(n - 1) * 2 + 1; } // 列出步驟過程 void move(int n, int s, int t) { if (n == 0) return; move(n-1, s, 6-s-t); cout << "從" << s << "移到" << t << '\n'; move(n-1, 6-s-t, t); } void tower_of_hanoi(int n) { // 所有盤子，從第一根柱子移到第三根柱子。 move(n, 1, 3); }

UVa 10017

遞推法、遞歸法，一體兩面，同時存在。

遞推法與遞歸法恰好顛倒：遞推法是針對已知，逐步累積，直至周全；遞歸法是針對未知，反覆拆解，直至精確。

遞推法是由小到大，遞歸法是由大到小。

範例：多項式函數求值（Horner's Rule）

遞推法是不斷配x，擴增已知；遞歸法是不斷提x，減少未知。

a ⋅ x² + b ⋅ x¹ + c

Iterative Method:
{a} ⋅ x² + b ⋅ x¹ + c
{a, ⋅x} ⋅ x¹ + b ⋅ x¹ + c
{a, ⋅x, +b} ⋅ x¹ + c
{a, ⋅x, +b, ⋅x} + c
{a, ⋅x, +b, ⋅x, +c}

Recursive Method:
{a ⋅ x² + b ⋅ x¹ + c}
{a ⋅ x² + b ⋅ x¹}, +c
{a ⋅ x¹ + b}, ⋅x, +c
{a ⋅ x¹}, +b, ⋅x, +c
{a}, ⋅x, +b, ⋅x, +c

雖然遞推法與遞歸法的推理方向是相反的，但是遞推法與遞歸法的計算方向是一樣的，兩者都是由小範圍算到大範圍。

Iterative Method:
a, ⋅x, +b, ⋅x, +c

Recursive Method:
a, ⋅x, +b, ⋅x, +c

UVa 498 10268

範例：巴斯卡三角形（Pascal's Triangle）

組合數，排列成三角形。

每一格的答案，由左上格（甲君在團中）、右上格（甲君不在團中）相加而得。從上往下是遞推，從下往上是遞歸。

UVa 369 485

範例：爬樓梯

眼前有五階樓梯，一次只能踏一階或踏兩階，那麼爬到五階總共有哪幾種踏法？例如(1,1,1,1,1)是其中一種踏法，(1,2,2)是另一種踏法。

這個問題可以用遞推法，也可以用遞歸法。

首先採用遞推法。試著只爬少少的幾階樓梯，觀察一下踏法。

爬到一階的踏法：很明顯的只有一種，(1)。

爬到兩階的踏法：有兩種，(1,1)和(2)。

爬到三階的踏法：因為一次只能踏一階或踏兩階，所以只可能從第一階或從第二階踏上第三階。只要綜合(爬到一階的踏法,2)與(爬到兩階的踏法,1)，就是爬到三階的踏法。

爬到四階的踏法：同理，綜合(爬到兩階的踏法,2)與(爬到三階的踏法,1)即得。

遞推下去，就可求出爬到五階的踏法。

Forward Iterative Method:
爬到一階　(1)
爬到兩階　(1,1) (2) 
爬到三階　即是(爬到一階,2)與(爬到二階,1)
　　　　　(1,2)
　　　　　(1,1,1) (2,1)
爬到四階　即是(爬到二階,2)與(爬到三階,1)
　　　　　(1,1,2) (2,2)
　　　　　(1,2,1) (1,1,1,1) (2,1,1)
爬到五階　即是(爬到三階,2)與(爬到四階,1)
　　　　　(1,2,2) (1,1,1,2) (2,1,2)
　　　　　(1,1,2,1) (2,2,1) (1,2,1,1) (1,1,1,1,1) (2,1,1,1)

前面是採用上樓梯的順序進行遞推，由第一階遞推到第五階。也可以採用下樓梯的順序進行遞推，由第五階遞推到第一階。

Backward Iterative Method:
降到四階　(1)
降到三階　(1,1) (2)
降到二階　即是(2,降到四階)與(1,降到三階)
　　　　　(2,1)
　　　　　(1,1,1) (1,2)
降到一階　即是(2,降到三階)與(1,降到二階)
　　　　　(2,1,1) (2,2)
　　　　　(1,2,1) (1,1,1,1) (1,1,2)
降到平面　即是(2,降到二階)與(1,降到一階)
　　　　　(2,2,1) (2,1,1,1) (2,1,2)
　　　　　(1,2,1,1) (1,2,2) (1,1,2,1) (1,1,1,1,1) (1,1,1,2)

有一些問題，比如爬樓梯問題，雙向都可以遞推。數值由小到大的方向稱為「正向」或「順向」（forward），數值由大到小的方向稱為「反向」或「逆向」（backward）。

接著採用遞歸法。由踏出的最後一步開始分析。

要「爬到五階」，最後一步一定是踏上第五階。要踏上第五階，只可能從第四階和第三階踏過來，也就是綜合(爬到四階的踏法,1)與(爬到三階的踏法,2)。

但是我們尚不知如何「爬到四階」和「爬到三階」，所以只好再分別研究「爬到四階」與「爬到三階」。不斷追究到「爬到一階」與「爬到兩階」的時候，就能確認答案了！

Forward(?) Recursive Method:
爬到五階　即是(爬到四階,1)與(爬到三階,2)
爬到四階　即是(爬到三階,1)與(爬到二階,2)
爬到三階　即是(爬到二階,1)與(爬到一階,2)
爬到兩階　(2) (1,1)
爬到一階　(1)

當然也可以雙向遞歸。就不贅述了。

Divide-and-Conquer Method

「分治法」。分割問題、各個擊破。將一個大問題，分割成許多小問題。如果小問題還是很難，就繼續分割成更小的問題，直到問題變得容易解決。

分割出來的小問題，稱作「子問題subproblem」。解決一個問題，等價於解決所有子問題。

用樹狀圖表達原問題與子問題的關係，最好不過！

分治法著重分割問題的方式──要怎麼分割問題，使得子問題簡單又好算？各位讀者可以藉由本文的範例，體會分割問題的方式。

範例：分解動作

想要學習「從中場帶球上籃」，我們可以將此動作分割為「跑步運球」、「跑步收球」、「單手將球放入籃框」等動作，分別學習。每一項動作都熟練之後，組合起來便是帶球上籃了。

如果覺得「跑步運球」還是太難，可以更細分成「原地運球」、「走動運球」、「運球時護球」等動作，克服了之後便能夠順利解決「跑步運球」的問題了。

範例：方格法求面積

左邊為原問題，右邊放大並細分的圖是其中一個子問題。

範例：分類數數

左邊最大的框框是原問題，將原問題的數字進行分類後再統計，分類後的每一個框框都是一個子問題。

UVa 11038

Recursive Method

在分治法當中，亦得遞迴地分割問題，其實就是遞歸法。

程式碼細分為三個階段：Divide、Conquer、Combine。Divide階段是把原問題分割成小問題，Conquer階段是解決小問題，Combine階段是運用小問題的解答，整理出原問題的解答。

divide_and_conquer(原問題) { /* Divide */ 先將原問題分割成許多小問題; /* Conquer */ 遞迴呼叫函式，求得子問題的解; 解答1 = divide_and_conquer(子問題1); 解答2 = divide_and_conquer(子問題2); ...... /* Combine */ 用小問題的解答，算出原問題的解答; 原問題解答 = 解答1 + 解答2 + ......; return 原問題解答; }

UVa 620 10101 10144 10998

範例：合併排序法（Merge Sort）

Divide階段：資料分割成兩堆。

Conquer階段：兩堆資料各自從事Merge Sort。

Combine階段：兩堆已排序過的資料，合併成一堆。

void merge(int array[], int left, int right, int mid) { int n = right - left + 1; int* x = new int[n]; int i = left, j = mid + 1; for (int k=0; k<n; k++) { if (i == mid + 1) x[k] = array[j++]; else if (j == right + 1) x[k] = array[i++]; else if (array[i] <= array[j]) x[k] = array[i++]; else x[k] = array[j++]; } for (int k=0; k<n; k++) array[left + k] = x[k]; delete[] x; } void merge_sort(int array[], int left, int right) { if (left >= right) return; /* Divide */ int mid = left + (right - left) / 2; /* Conquer */ merge_sort(array, left, mid); merge_sort(array, mid+1, right); /* Combine */ merge(array, left, right, mid); } void merge_sort(int array[], int n) { merge_sort(array, 0, n-1); }

範例：快速排序法（Quicksort）

Divide階段：任意挑選一個數字當作基準（例如最右端），把資料分割成左右兩堆。左堆數字小於等於基準，右堆數字大於基準。

Conquer階段：左右兩堆資料各自從事Quicksort。

Combine階段：不做任何事。

int partition(int array[], int left, int right) { int pivot = array[right]; // 基準 int i = left; for (int j = left; j < right; ++j) if (array[j] <= pivot) { swap(array[i], array[j]); i++; } swap(array[i], array[right]); return i; // pivot的位置 } void quicksort(int array[], int left, int right) { if (left >= right) return; /* Divide */ int k = partition(array, left, right); /* Conquer */ quicksort(array, left, k-1); // 左堆 quicksort(array, k+1, right); // 右堆 /* Combine */ } void quicksort(int array[], int n) { quicksort(array, 0, n-1); }

Prune-and-Search Method

「修剪搜尋法」是分治法的特例。去除不重要的子問題，只搜尋重要的子問題。

UVa 920

範例：二元搜尋法（Binary Search）

在已排序陣列裡面，尋找特定數字。

陣列由中央切成兩邊，一邊數字較小、一邊數字較大。這兩邊一定有一邊不是我們所要的，可以去除，只需要繼續尋找其中一邊。

int binary_search(int array[], int n, int key) { int left = 0, right = n-1; while (left <= right) { int mid = left + (right - left) / 2; if (array[mid] < key) left = mid + 1; else if (array[mid] > key) right = mid - 1; else if (array[mid] == key) return mid; } return -1; // 找不到 }

UVa 10077

範例：快速選擇法（Quickselect）

在未排序陣列裡面，尋找第k小數字。

運用Quicksort 的分割手法，把陣列切成兩邊，一邊數字較小、一邊數字較大。這兩邊一定有一邊不是我們所要的，可以去除，只需要繼續尋找其中一邊。

int quickselect(int array[], int n, int k) { int left = 0, right = n-1; while (left <= right) { int i = partition(array, left, right); if (k < i) right = i - 1; else if (k > i) left = i + 1; else if (k == i) return array[i]; } return -1; // 找不到 }

範例：尋找假幣（Counterfeit Coin Problem）

一堆硬幣，當中一枚硬幣是假幣，重量比真幣輕，肉眼無法分辨差異。手邊的工具僅有一台天平，但沒有砝碼，該如何藉由天平判斷假幣？

當硬幣總數為一，那麼該幣就是假幣。當硬幣總數為二，則兩枚硬幣分別放在天平兩端秤重，較輕的一端就是假幣。當硬幣總數為三以上，一定有辦法找出假幣，以下介紹兩種策略。

採用遞增法。每次取兩枚硬幣，放在天平兩端秤重。當天平平衡，表示這兩枚硬幣都是真幣，接著繼續處理剩餘硬幣。當天平傾斜，比較輕的硬幣就是假幣。

採用分治法。兩枚硬幣放在天平兩端秤重，當天平平衡，表示這兩枚硬幣都是真幣。接著只剩下N-2枚硬幣要尋找假幣──問題遞迴縮小了！

剩下N-2枚，太多了一點。一次取多一點硬幣，同時放在天平兩端秤，問題就能縮小更多了！

把所有硬幣平均分成三份，取兩份放在天平兩端秤重。當天平平衡，表示剩下的一份含有假幣，問題一次便縮小為1/3。當天平傾斜，表示比較輕的一份含有假幣，問題一次便縮小為1/3。

讀者可以想想看：如果硬幣數量不是三的倍數怎麼辦？如果一開始不知道假幣與真幣孰輕孰重怎麼辦？

UVa 12732 12733

Dynamic Programming

「動態規劃」。分治法輔以記憶法。當分治法分割出來的問題，一而再、再而三出現，就運用記憶法儲存這些問題的答案，避免重複求解，以空間換取時間。

由於內容較多較雜，另以專門頁面介紹。

Greedy Method

「貪心法」。以Incremental Method或Iterative Method製造答案的方法，大致上分為兩類：

一、填答案：從沒有答案開始，逐步填滿答案。

二、改答案：先隨便弄個答案，逐步修飾答案。

觀察問題特徵，擬定一個看似最好的原則，依照原則填答案、改答案。

UVa 120 311 410 514 538 668 757 10148 10201 10249 10366 10382 10440 10602 10716 10718 10982 ICPC 3752 4788

範例：找零錢

你去商店買東西，你掏出了一張一百元，買了一包23元的零食。店員須找零錢給你，但是你希望店員找給你的硬幣數目越少越好，如此口袋會輕一點。那麼店員會給你幾個硬幣呢？

填答案的原則是：先找給你面額較高的硬幣。

金額越少，找給你的硬幣數目也就越少。先找給你面額較高的硬幣，金額下降的最多──如此一來，往後找給你的硬幣數目就一定是最少了。

注意到：當錢幣面額很特別時，這個方法才正確。詳情請參考「Change-Making Problem」。

範例：文章換行（Word Wrap）

一大段的英文段落，適當的將文章換行，讓文字不超過紙張邊界，盡量節省紙張空間。

填答案的原則是：字儘量往前擠，擠不下就換行。

範例：騎士周遊問題（Knight's Tour）

西洋棋盤上，請找到一條路線，讓騎士恰好經過棋盤上每一格各一次。

填答案的原則是：走向出路選擇較少的格子。如果遇到出路選擇一樣多的格子，就走向位於下方的格子。如果又遇到一樣低的格子，就走向位於左方的格子。

這種填答案的方式，耗盡死路，保留活路，將來走入死胡同的機會就變少了。有一種「置之死地而後生」的味道。

注意到：這個方法不一定會成功。我們根本無法證明這個方法會成功，只是乍看起來比較容易成功。

我們當下所做的最佳決定，以長遠的眼光來看，不一定是最佳決定。儘管貪心法不見得得到正確的、最好的答案，卻是個快速得到答案的好方法。

範例：活動選擇問題（Activity Selection Problem）

暑假到了，有好多好多有趣的營隊可以參加囉！攀岩、潛水、單車環島團、吉他營、電腦營、……，每個營隊都好有趣，好想每個營隊都參加──可是卻有好多營隊的活動期間都互相卡到，沒辦法同時參加。到底要參加哪些營隊活動才好呢？當然是越多種越好！

填答案的原則很簡單：優先選擇最早結束的活動，就能剩下最多時間來安排其他活動。

仔細分成兩種情況進行討論：一、最早結束的活動，與其他活動的時間不重疊；二、最早結束的活動，與某些活動的時間重疊。

一的狀況下，參加最早結束的活動，顯然是最理想的──憑空多參加了一個活動，又不耽誤到其他活動。

此觀念可以用Recursive Method詮釋：去除最早結束的活動、遞迴縮小問題。

二的狀況下，最早結束的活動、以及時間與之重疊的活動當中，只能選擇其中一個參加。此時參加最早結束的活動，得以剩下比較多的時間，仍是最理想的。

此觀念可以用Recursive Method詮釋：去除最早結束的活動、去除因而無法參加的活動，遞迴縮小問題。

填答案的原則是：所有活動按照結束時間排序，依序參加活動。如果時間允許就參加，如果時間衝突就不參加。

UVa 10020 ICPC 4328 5105

範例：函數的局部極小值

改答案的原則是：一開始x隨意設定一個數值，例如設定x = 0。微調x值，並且計算f(x)──如果f(x)減少，就更新x；如果f(x)沒減少，就不更新x。不斷修改x值，最後就到達局部極小值。

範例：交換相鄰數字的排序法

改答案的原則是：每當發現相鄰兩個數字，左邊數字大於右邊數字，兩個數字就交換位置。

不斷交換位置，導致大數字逐漸往右端移動、小數字逐漸往左端移動，最後一定能完成排序。

讀者可以想想看：交換任意兩個數字的排序法，成立嗎？

順帶一提，排序過程反向操作，可以得到一個結論：排序過的陣列，經由兩兩相鄰交換，一定可以得到各種排列方式。

範例：平面上距離最近的兩個點（Closest Pair）

採用遞增法，逐次增加一個點；採用枚舉法，計算新點到其他點的距離。每當發現更近的兩個點，下次即可減少橫向搜尋範圍。

運用目前得到的答案，藉此得到更好的答案！可以看作是間接地、改答案的原則。

另外，還可以減少縱向搜尋範圍。除了新點以外，兩點之間的距離，至少都是上次的最短距離，不能太密太擠。在橫向搜尋範圍之內，進行縱向排序（採用即時排序的資料結構，效率較佳），只需檢查新點的上兩點、下兩點，就一定能檢查到半圓內所有點！

儘管無法直接得到正確的點，但是只需檢查少數幾點！可以看作是間接地、填答案的原則。

UVa 10245 ICPC 7581

Scaling Algorithm

「縮放演算法」。將數值拆解為不同數量級，每個數量級分別計算一次答案，並且累計每次計算成果。

範例：乘法

數量級從小到大：乘數拆解為不同數量級，先以個位數相乘一次，再以十位數相乘一次，……，再以最高位數相乘一次，累加起來，得到正確結果。

範例：基數排序法（Radix Sort）

數量級從小到大：所有數字先以個位數排序一次，再以十位數排序一次，……，再以最高位數排序一次，得到正確結果。

數量級從大到小：所有數字先以最高位數排序一次，再以前兩高位數排序一次，……，再以全部位數排序一次，得到正確結果。

改善計數排序法的效率，不必建立一長串陣列。

範例：多重解析度字串搜尋（Multiscale String Searching）

從宏觀到微觀，從粗糙到細膩。短字串跳N格實施比對。若足夠相似，才跳N/2格實施比對。……。若足夠相似，才跳1格實施比對。

改善字串搜尋的效率，不必每次都比對一大串字元。

範例：Shell排序法（Shell Sort）

從宏觀到微觀，從粗糙到細膩。跳N個數字為同一組，每組分別實施插入排序法。跳N/2個數字為同一組，各組分別實施插入排序法。……。跳1個數字為同一組，所有數字實施插入排序法。

改善插入排序法的效率，不必每次都挪動一大串數字。

I/O-efficient Algorithm（External Memory Algorithm）

儲存容量大，存取時間長；儲存容量小，存取時間短。魚與熊掌不可兼得。自然而然形成階層架構：暫存器、快取、記憶體、硬碟，儲存容量越來越大，存取時間越來越久。

需要計算的變數，儲存在暫存器；不在暫存器，就找快取；不在快取，就找記憶體；不在記憶體，就找硬碟。

簡中譯作寄存器、缓存、内存、硬盘。

實務上，硬碟可以換成光碟、隨身碟、雲碟、顯示器、揚聲器。

簡中譯作光盘、闪存盘、云盘、显示器、扬声器。

對電腦來說，最花時間的動作，不是運算，而是讀寫：從硬碟讀入資料到記憶體、從記憶體寫出資料到硬碟。

每當資料不在記憶體，就從硬碟讀入資料到記憶體。根據硬碟運轉速率，等待硬碟籌備資料；根據傳輸通道大小，讀入一堆資料。

異地資料，讀寫時間約是計算時間的一千倍！此時我們關心讀寫時間，不太關心計算時間。「輸入輸出效率演算法」或者「外部記憶體演算法」目的是減少讀寫時間。或者簡單來說，減少讀寫次數。

順帶一提，I/O-efficient Algorithm是新興詞彙，目前較少見；External Memory Algorithm是原始詞彙，目前仍常見。

範例：動態陣列（Dynamic Array）

不知資料多寡，只好準備一塊記憶體空間，暫存資料。每當空間滿了，才擴充空間。

C++標準函式庫的vector，即是動態陣列。

void dynamic_array() { vector<int> v; v.push_back(3); v.push_back(6); v.push_back(9); v.push_back(-8); v.push_back(1); }

範例：緩衝區（Buffer）

不知資料生成時刻，只好準備一塊記憶體空間，暫存資料。每當資料夠了，才處理資料。

printf/scanf、cin/cout，內含緩衝區。

void print() { printf("It's a pencil."); fflush(stdout); // 立即清空緩衝區 setbuf(stdout, NULL); // 不使用緩衝區 cout << "It's a pencil."; cout << flush; // 立即清空緩衝區 cout << endl; // 等同 cout << '\n' << flush; cout << unitbuf; // 每次都清空緩衝區（不使用緩衝區） };

範例：合併排序法（Merge Sort）

排序硬碟資料。

一、資料分段排序：每段資料符合記憶體容量，假設分成了k段。k段資料分別讀入、排序、寫出。

二、資料合併排序：記憶體配置k塊輸入、1塊輸出緩衝區。k段資料合併成排序資料。

在步驟一，當資料分段太多，則遞迴處理。

範例：桶子排序法（Bucket Sort）

排序硬碟資料。

一、資料分類排序：記憶體配置1塊輸入、k塊輸出緩衝區。一段資料分散於k個桶子，依照數字大小。

二、資料分段排序：k段資料分別讀入、排序、寫出。

在步驟二，當一段資料太長，則遞迴處理。

範例：選擇排序法暨二元搜尋法（Selection Sort & Binary Search）

不排序硬碟資料，不使用其他硬碟空間，直接輸出排序結果。

篩選最小的數字們、排序、輸出。以二元搜尋法，調整篩選範圍。如果硬碟未讀完、緩衝區已滿溢，則減少篩選範圍，重新來過；如果硬碟已讀完，緩衝區未滿溢，則排序、輸出、更新篩選範圍。

小心處理同一數字數量非常多的情況。

int MIN = -1000000000; // 數字的最小值 int MAX = +1000000000; // 數字的最大值 const int M = (1 << 18); const int N = (1 << 19); int in[M]; // 篩選前的數字 int out[N]; // 篩選後的數字 // 讀取檔案裡面所有數字，篩選大於等於L、小於等於R的數字。 int read(ifstream& fin, int L, int R) { int n = 0; fin.clear(); // 回復讀寫狀態 fin.seekg(0, fin.beg); // 回到檔案開頭 while (true) { // 讀取檔案裡面的數字 fin.read((char*)in, sizeof(int)*M); int c = fin.gcount() / sizeof(int); if (c <= 0) break; // 沒有數字就結束 // 篩選數字 for (int i = 0; i < c; i++) if (in[i] >= L && in[i] <= R) if (L == R) { if (n < N) out[n++] = in[i]; else n++; // 同一數字出現許多次 } else { if (n < N) out[n++] = in[i]; else return -1; // 存不下 } } return n; } // 選擇排序法暨二元搜尋法 // 屢次從檔案裡面篩選最小的數字們、排序、輸出。 // 如果記憶體滿溢，則將篩選範圍減半，重新來過。 void sort_file() { ifstream fin("number.in", ios::binary); ofstream fout("number.out", ios::binary); // 選擇排序法暨二元搜尋法 for (int L = MIN, R = MAX; L <= R; ) { int M = (L + R) / 2; int n = read(fin, L, M); if (n < 0) // 記憶體滿溢。篩選範圍減半。 R = M; else if (n == 0) // 查無數字。處理另一半範圍。 L = M + 1; else // 記憶體未滿溢。排序。輸出。 { if (L == M) { for ( ; n > N; n -= N) fout.write((char*)out, sizeof(int)*N); if (n > 0) fout.write((char*)out, sizeof(int)*n); } else { sort(out, out + n); fout.write((char*)out, sizeof(int)*n); } // 處理其餘範圍 L = M + 1; R = MAX; } } fin.close(); fout.close(); }

Cache-efficient Algorithm

方才討論了記憶體與硬碟的讀寫。「快取效率演算法」則是考慮快取與記憶體的讀寫。

對中央處理器來說，最花時間的動作，不是運算，而是讀寫：從記憶體讀入資料到快取、從快取寫出資料到記憶體。

每當資料不在快取，就從記憶體讀入資料到快取，讀入資料所在的那一個區塊。區塊大小等於通道大小。快取大小是其倍數。

資料不在快取，稱作cache miss。「快取效率演算法」目的是減少cache miss、減少讀入次數。

順帶一提，cache-efficient細分為cache-aware和cache-oblivious。前者充分瞭解硬體規格，知道區塊大小、快取大小。後者無視硬體規格，不知道詳細數據。

範例：陣列與串列

陣列在記憶體裡是連續的。串列在記憶體裡通常不是連續的。

枚舉陣列元素，偶爾載入區塊，不會重複載入，速度快。

枚舉串列元素，經常載入區塊，甚至重複載入，速度慢。

範例：變數型態

int = 4 byte，short = 2 byte，雖然儲存空間不一樣大，但是加法運算卻一樣快，都是一單位時間。

雖然兩數加法一樣快，但是多數總和就不一樣快。short array空間小，區塊少，速度快。

short summation() { short array[1000] = {}; // short array，空間小，區塊少，速度快。 short sum = 0; for (int i=0; i<1000; i++) sum += array[i]; return sum; } int summation() { int array[1000] = {}; // int array，空間大，區塊多，速度慢。 int sum = 0; for (int i=0; i<1000; i++) sum += array[i]; return sum; }

範例：二維陣列的總和

依序枚舉二維陣列的所有元素，累計總和。

枚舉橫條元素，偶爾載入區塊，速度快。

枚舉直條元素，不斷載入區塊，速度慢。

int summation() { int array[1000][1000] = {}; // 橫條為主，速度快。 // 外層枚舉每一個橫條，內層枚舉一個橫條的每一個元素。 int sum = 0; for (int i=0; i<1000; i++) for (int j=0; j<1000; j++) sum += array[i][j]; return sum; } int summation() { int array[1000][1000] = {}; // 直條為主，速度慢。 // 外層枚舉每一個直條，內層枚舉一個直條的每一個元素。 int sum = 0; for (int j=0; j<1000; j++) for (int i=0; i<1000; i++) sum += array[i][j]; return sum; }

範例：矩陣轉置（Matrix Transpose）

矩陣轉置：沿著左上右下對角線翻轉矩陣。

輸入矩陣偶爾載入區塊，輸出矩陣不斷載入區塊。

void matrix_transpose() { int a[1000][1000] = {}; int b[1000][1000] = {}; for (int i=0; i<1000; i++) for (int j=0; j<1000; j++) b[j][i] = a[i][j]; } void matrix_transpose(int a[], int b[], int x, int y) { for (int i=0; i<x; i++) for (int j=0; j<y; j++) b[x*j+i] = a[y*i+j]; }

分塊矩陣轉置：基本單位從元素變成分塊。

調整枚舉順序，優先枚舉分塊。雖然輸入矩陣載入區塊略增，但是輸出矩陣載入區塊驟減。

void block_transpose(int _a[], int _b[], int _x, int _y, int x, int y) { for (int i=0; i<_x; i++) for (int j=0; j<_y; j++) _b[x*j+i] = _a[i*y+j]; } void matrix_transpose(int a[], int b[], int x, int y) { int xblock = sqrt(x); // 分塊數量 int yblock = sqrt(y); int xq = x / xblock; // 分塊寬度 int yq = y / yblock; int xr = x - (xblock - 1) * xq; // 最後一個分塊寬度 int yr = y - (yblock - 1) * yq; for (int i=0; i<xblock; i++) for (int j=0; j<yblock; j++) { int* _a = a + y*(xq*i) + (yq*j); int* _b = b + x*(yq*j) + (xq*i); int _x = (i < xblock-1) ? xq : xr; int _y = (j < yblock-1) ? yq : yr; block_transpose(_a, _b, _x, _y, x, y); } }

範例：小畫家倒墨水（Flood Fill Algorithm）

建立二維陣列或者一維陣列，盤面格子依序對應陣列索引值，區塊形成橫條。一個格子，左右通常是相同區塊，上下通常是不同區塊。墨水填充過程，經常載入區塊。

建立一維陣列，盤面格子重新對應陣列索引值，區塊從橫條變方塊。墨水填充過程，不常載入區塊。

Parallel Algorithm

循序（Sequential）就是逐一，平行（Parallel）就是一齊，兩者是相對概念。

「平行演算法」。當多個數值需要計算，就可以使用多個計算器一齊計算。優點是減少計算時間，缺點是增加硬體、增加電力。

計算器有兩種類型：SIMD與MIMD。

SIMD：多個計算器只能一齊執行相同指令。

MIMD：多個計算器可以分頭執行不同指令。

SIMD富含巧思，MIMD缺乏變化，所以我們只談SIMD。

當每一輪迴圈之間的變數不互相使用，就可以讓每一個計算器一齊計算。

平行計算的架構：記憶體傳遞資料給多個計算器，多個計算器一齊計算，多個計算器傳遞資料給記憶體。

籌備規劃平行計算，需要額外時間空間。因此平行計算不一定比循序計算好。程式員必須自行取捨。

Parallel Algorithm補充說明

平行計算的經典弱點：

kernel launch overhead：籌備規劃平行計算，需要額外時間空間。
shared memory bank conflict：共享記憶體，需要排隊等待，需要額外時間。
barrier synchronization overhead：結束平行計算，需要等待執行最久的計算器，需要額外時間。
branch divergence overhead：if敘述，後續指令略有不同，難以一齊計算。

平行計算的層級與稱呼：

層級       計算器                平行計算
---------+---------------------+-----------------------------------
微處理器 | 實體 processor core | 多行程、多进程（multiprocessing）
作業系統 | 虛構 thread         | 多執行緒、多线程（multithreading）
異質系統 | 實體 processor      | 異構計算（heterogeneous computing）
網際網路 | 實體 computer       | 分散式計算（distributed computing）

平行計算的程式語言與函式庫：

類型   語言   函式庫             標頭檔         備註
-----+------+------------------+-------------+----------------------
SIMD |      | OpenMP           | <omp.h>     | GCC、MSVC編譯器已內建
SIMD | CUDA |                  |             | 僅適用NVIDIA公司的產品
MIMD | C++  | standard library | <thread>    |
MIND | C    | C POSIX library  | <pthread.h> | 僅適用類UNIX作業系統

平行計算的組合語言與指令集：

類型   語言   指令集   備註
-----+------+-------+--------------------------
SIMD | x86  | SSE   | 各種基本運算
SIMD | x86  | AVX   | SSE增加輸入輸出的位元長度
SIMD | x86  | FMA   | 形如a = b × c + d的運算

範例：複製字串

理論：各個字元分頭複製。n步變1步。

實務：籌備n個執行緒，需要額外時間空間，跟循序計算沒兩樣，弄巧成拙。因此，字串切成數段，分頭複製。

void copy() { char s[15] = "incremental"; char t[15]; // 必須預先知道字串長度，才能明確訂定平行計算範圍。 int n = 11; // 分段數量交由編譯器決定 #pragma omp parallel for for (int i=0; i<n; i++) t[i] = s[i]; t[n] = '\0'; cout << "原本字串" << s; cout << "複製之後的字串" << t; } void copy(char* s, char* t, int n) { #pragma omp parallel for for (int i=0; i<n; i++) t[i] = s[i]; t[n] = '\0'; }

範例：加總數字

理論：數字雙雙相加。n步變log₂n步。

實務：陣列切成數段，分頭計算總和。最後累加各段總和。

void summation() { int array[5] = {3, 6, 9, -8, 1}; // 陣列切成兩段，分頭計算總和。 int sum = 0; #pragma omp parallel for num_threads(2) reduction(+:sum) for (int i=0; i<5; i++) sum = sum + array[i]; cout << "總和是" << sum; } int summation(int array[], int n) { int sum = 0; #pragma omp parallel for num_threads(2) reduction(+:sum) for (int i=0; i<n; i++) sum += array[i]; return sum; }

範例：生命遊戲（Cellular Automaton）

理論：兩層的平行化，外層是地圖的每一個細胞，內層是八個鄰居細胞數量總和。8⋅x⋅y步變log₂8步。

實務：只平行化每一個細胞，放棄平行化細胞數量總和。

void cellular_automaton() { // 包裝成函式，讓程式碼易讀！ bool board[2][5][5] = {}; clear_board(board[0]); load_board(board[0]); print_board(board[0]); // 遞推四回合 for (int t=0; t<4; ++t) { // 只平行化每一個細胞，放棄平行化細胞數量總和。 #pragma omp parallel for collapse(2) for (int x=0; x<5; ++x) for (int y=0; y<5; ++y) go(x, y, board[t%2], board[(t+1)%2]); print_board(board[(t+1)%2]); } }

範例：矩陣乘法（Matrix Multiplication）

理論：兩層的平行化，外層是輸出矩陣的每一個元素，內層是數列點積。x⋅y⋅z步變1+log₂y步。

實務：只平行化每一個元素，放棄平行化數列點積。

void matrix_multiply() { const int x = 3, y = 3, z = 3; int a[x][y] = {{1,0,0},{0,1,0},{0,0,1}}; int b[y][z] = {{1,2,3},{4,5,6},{7,8,9}}; int c[x][z]; // 只平行化每一個元素 #pragma omp parallel for collapse(2) schedule(static) for (int i=0; i<x; i++) for (int j=0; j<z; j++) { // 放棄平行化數列點積 c[i][j] = 0; for (int k=0; k<y; k++) c[i][j] += a[i][k] * b[k][j]; } cout << "矩陣是" << '\n'; for (int i=0; i<x; i++) { for (int j=0; j<z; j++) cout << c[i][j] << ' '; cout << '\n'; } } void multiply_matrix(int a[], int b[], int c[], int x, int y, int z) { // 只平行化每一個元素 #pragma omp parallel for collapse(2) schedule(static) for (int i=0; i<x; i++) for (int j=0; j<z; j++) { // 放棄平行化數列點積 c[z*i+j] = 0; for (int k=0; k<y; k++) c[z*i+j] += a[y*i+k] * b[z*k+j]; } }

進一步考慮I/O-efficient Algorithm。

矩陣乘法：各個執行緒重複讀寫相同元素。x⋅z個執行緒，各自讀取2⋅y個元素。總共讀取2⋅x⋅y⋅z個元素。

分塊矩陣乘法：矩陣切割為b⋅b個分塊，每次計算一個輸出矩陣分塊，減少讀寫時間。b⋅b⋅b個執行緒，每b個執行緒共享(x/b + z/b)⋅y個元素。總共讀取b⋅(x+z)⋅y個元素。

註：此層級的平行計算，無法讓部分執行緒共享部分記憶體。但是分塊矩陣乘法起碼有Cache-efficient Algorithm的效果。

void clear_block(int* _c, int _x, int _z, int z) { for (int i=0; i<_x; i++) for (int j=0; j<_z; j++) _c[z*i+j] = 0; } void multiply_block(int* _a, int* _b, int* _c, int _x, int _y, int _z, int y, int z) { for (int i=0; i<_x; i++) for (int j=0; j<_z; j++) { // c[i][j] += a[i][k] * b[k][j]; int t = 0; for (int k=0; k<_y; k++) t += _a[y*i+k] * _b[z*k+j]; _c[z*i+j] += t; } } void multiply_matrix(int* a, int* b, int* c, int x, int y, int z) { const int block = 1; // 分塊數量（單邊） int xq = x / block; // 分塊寬度 int yq = y / block; int zq = z / block; int xr = x - (block - 1) * xq; // 最後一個分塊寬度 int yr = y - (block - 1) * yq; int zr = z - (block - 1) * zq; #pragma omp parallel for collapse(2) schedule(static) for (int i=0; i<block; i++) for (int j=0; j<block; j++) { // c[i][j] = 0; int* _c = c + (xq * z * i) + (zq * j); int _x = (i < block-1) ? xq : xr; int _z = (j < block-1) ? zq : zr; clear_block(_c, _x, _z, z); // c[i][j] = a[i][k] * b[k][j]; #pragma omp parallel for schedule(static) for (int k=0; k<block; k++) { int* _a = a + (xq * y * i) + (yq * k); int* _b = b + (yq * z * k) + (zq * j); int _y = (k < block-1) ? yq : yr; multiply_block(_a, _b, _c, _x, _y, _z, y, z); } } }

Pipelined Algorithm

「流水線演算法」。原理如同工廠的裝配線、生產線。

不同功能的計算器，各自負責專門指令。一連串指令，依序交給每一種計算器。每一輪迴圈當中的一連串指令，接連交給計算器。

當每一輪迴圈之間的變數不互相使用、且迴圈之中的指令不重複，就可以讓每一種計算器不停計算。

CPU已經內建流水線功能，程式員不必親自設計流水線演算法。因此流水線演算法目前不是顯學。

Randomized Algorithm

「隨機化演算法」。隨便的計算數值、計算順序。難得糊塗。

範例：隨機數字（Random Number）

隨機數字又稱亂數。亂七八糟、毫無章法、什麼都有可能。

如何製造亂數呢？沒人知道！數學家尚未釐清「亂」是什麼。計算學家則創造了形形色色的算式，偽造亂數，聊勝於無。

簡易算式：乘上一數、加上一數，遞推下去。

int rand() { // 使用unsigned int，即便溢位也不會當機。 static unsigned int seed = 0; // 乘上一數、加上一數。 seed = seed * 1103515245U + 12345U; // 符合int上限範圍，得到[0, 2³¹-1]之間的亂數。 return int(seed % 2147483648U); }

C標準函式庫，已經有亂數了。

void random_number() { // 設定亂數表，之後才能使用rand()。 srand(time(0)); // 印出10個亂數，範圍是整數0到整數4。 for (int i=0; i<10; i++) cout << rand() % 5; }

範例：雜湊函數（Hash Function）

一種特別的函數：數字變成特定範圍數字。

雜湊函數應用廣泛，衍生許多變化，其中一種經典變化是：數字變成特定範圍亂數。隨便導致分散──亂數四散，不會太集中。

int hash(int num, int range) { // 以給定的資料，製造一個亂數，位於[0, range-1]。 unsigned int hash = num; // num是負數也沒關係 hash = hash * 1103515245U + 12345U; return int(hash % 2147483648U) % range; }

C++標準函式庫，已經有雜湊函數了，但是不是亂數版本。不會變成亂數，而是變成原本數字，喜感十足。

void hash_function() { // 印出數字0到9的雜湊值，位於[0, 2³¹-1]。 hash<int> int_hash; for (int i=0; i<10; i++) cout << int_hash(i); // 印出數字0到9的雜湊值，位於[0, 2³¹-1]。 for (int i=0; i<10; i++) cout << hash<int>{}(i); }

範例：雜湊表（Hash Table）

以簡短陣列儲存資料，以雜湊函數決定儲存位置。隨便導致分散──資料四散，不會太集中。

優點是搜尋迅速，只需瀏覽少數資料，不必瀏覽全部資料。

const int range = 5; void add_number(vector<int> table[range], int num) { // 以雜湊函數決定存放位置 int h = hash(num, range); // 儲存至陣列 table[h].push_back(num); } bool find_number(vector<int> table[range], int num) { // 只需瀏覽少數資料，不必瀏覽全部資料。 int h = hash(num, range); for (auto x: table[h]) // 窮舉 if (x == num) // 搜尋 return true; return false; }

範例：均勻隨機數字（Uniform Random Number）

亂數雖分散，卻不見得均勻。於是計算學家另行創造算式，偽造均勻亂數。由於需要背景知識，此處不多提。

又亂、又均勻，很匪夷所思吧！譯作亂數真的沒問題嗎？

C++標準函式庫，已經有均勻亂數了。

void random_number() { // 亂數生成器 default_random_engine g; // 均勻亂數，範圍[0, 5)。 uniform_int_distribution<int> rand(0, 4); // 印出10個亂數，範圍是整數0到整數4。 for (int i=0; i<10; i++) cout << rand(g); }

範例：隨機抽樣（Simple Random Sampling）

隨機挑選一物，機率均等。

// 差勁的做法。不均勻。 int simple_random_sampling(int array[], int n) { srand(time(0)); return array[rand() % n]; } // 比較優秀的做法。比較均勻。 int simple_random_sampling(int array[], int n) { default_random_engine g; uniform_int_distribution<int> rand(0, n-1); return array[rand(g)]; }

範例：隨機混洗（Random Shuffle）

隨機排列，打亂順序，機率均等。

void random_shuffle(int array[], int n) { srand(time(0)); // 數字0到n-1 int permutate[n]; for (int i=0; i<n; i++) permutate[i] = i; // 逐次挑出一個數字 for (int i=0; i<n-1; i++) { // 剩下的數字，隨機挑出一個數字（的位置）。 int j = i + rand() % (n - i); // 挑出的數字，挪至前面。 swap(permutate[i], permutate[j]); } // 重新排列 int temp[n]; for (int i=0; i<n; i++) temp[i] = array[i]; for (int i=0; i<n; i++) array[permutate[i]] = temp[i]; }

與其先排列再交換，不如直接交換。

void random_shuffle(int array[], int n) { srand(time(0)); // 逐次挑出一個數字 for (int i=0; i<n-1; i++) { // 剩下的數字，隨機挑出一個數字（的位置）。 int k = i + rand() % (n - i); // 挑出的數字，挪至前面。 swap(array[i], array[k]); } }

範例：隨機化搜尋法（Randomized Search）

隨便挑一個位置，直到找到為止、直到無處可尋為止。程式可能永不結束。

int randomized_search(int array[], int n, int num) { srand(time(0)); // 建立表格，記錄已經找過的位置。 // 一開始所有位置皆未找過。 bool visit[n] = {}; // 錯誤的實作方式。 // 程式可能永不結束，儘管機率趨近0。 for (int i=0; i<n; i++) { int j; do j = rand() % n; while (visit[j]); if (array[j] == num) return j; visit[j] = true; } return -1; }

從其餘位置當中隨便挑一個位置，直到找到為止、直到無處可尋為止。程式一定結束。

int randomized_search(int array[], int n, int num) { srand(time(0)); for (int i=0; i<n-1; i++) { // 從其餘位置當中隨便挑一個位置 int j = i + rand() % (n - i); if (array[j] == num) return j; // 已經找過的數字，挪至前面，永不再找。 swap(array[i], array[j]); } return -1; }

綜觀過程，是以一種順序讀取各個數字。因此隨機的計算順序，可以等價交換成隨機的輸入順序、循序的計算順序。

int randomized_search(int array[], int n, int num) { // 隨機排列 random_shuffle(array, array+n); // 循序搜尋 for (int i=0; i<n; i++) if (array[i] == num) return i; return -1; } int randomized_search(int array[], int n, int num) { // 額外建立索引值、指標，避免改變陣列內容。 int index[n]; for (int i=0; i<n; i++) index[i] = i; // 隨機的計算順序 random_shuffle(index, index+n); for (int i=0; i<n; i++) if (array[index[i]] == num) return i; return -1; }

搜尋次數的期望值是(n+1)/2。

正確數字在每個位置的出現機率都一樣多，都是1/n。
正確數字出現在第1個位置，讀取第1個數字就能找到。
正確數字出現在第i個位置，讀取第i個數字才能找到。
  (1/n) × 1 + (1/n) × 2 + ... + (1/n) × n
= (1/n) × (1 + ... + n)
= (1/n) × (1+n)n/2
= (1+n)/2

範例：隨機化排序法（Randomized Sort）

隨便挑兩個位置，若數字順序不對則交換，直到無處可尋為止。

交換次數的期望值是多少呢？

只挑相鄰位置，期望值會比較少嗎？

儘管缺乏實用價值，但是如果你會分析，麻煩教我。

範例：矩陣乘法驗算（Matrix Product Verification）

矩陣乘法，通盤檢查太久，抽樣檢查較快。

第二個矩陣，隨機挑選一個向量來驗算。驗算一次，僥倖通過機率是(n-1)/n；驗算k次，僥倖通過機率是(n-k)/n。

第二個矩陣，隨機挑選多個向量，以向量總和來驗算。驗算一次，僥倖通過機率是1/2；驗算k次，僥倖通過機率是(1/2)ᵏ。效果好多了。

const int N = 10; typedef int Matrix[N][N]; // Freivalds' Algorithm bool verify_matrix_product(Matrix A, Matrix B, Matrix C) { srand(time(0)); // 驗算5次 for (int t=0; t<5; t++) { // 第二個矩陣，隨機挑選多個向量。 // 0是沒選中，1是選中。 bool column[N] = {}; for (int i=0; i<N; ++i) column[i] = rand() % 2; // 計算向量總和 int sumB[N] = {}; for (int k=0; k<N; k++) for (int j=0; j<N; j++) if (column[j]) sumB[k] += B[k][j]; // 以向量總和來驗算 // 逐次檢查各個元素 for (int i=0; i<N; i++) { int sumAB = 0; for (int k=0; k<N; k++) sumAB += A[i][k] * sumB[k]; int sumC = 0; for (int j=0; j<N; j++) if (column[j]) sumC += C[i][j]; if (sumAB != sumC) return false; } } return true; }

範例：集合相似度（Set Similarity）

此處將集合相似度設為交聯比：交集大小除以聯集大小。

交集與聯集，通盤計算需額外記憶體，抽樣計算以節省記憶體。

集合有兩種資料結構：循序儲存、索引儲存。

如果是循序儲存，隨機挑選一個數字，判斷是不是交集元素、聯集元素。大量抽樣，統計比例。累計越多次，答案越準確。

陣列還可以改成雜湊表，節省搜尋時間。

const int range = 10; double set_similarity(vector<int> A[range], vector<int> B[range]) { srand(time(0)); int c = 0; // 交集大小 int d = 0; // 聯集大小 for (int i=0; i<5; i++) // 抽樣5次 { int x = rand(); bool inA = find_number(A, x); // 搜尋雜湊表 bool inB = find_number(B, x); if (inA && inB) c++; if (inA || inB) d++; } return (double)c / d; }

如果是索引儲存，隨機抽樣改成隨機排列，然後挑選首個標記位置來比對。

隨機排列還可以改成雜湊函數，節省排列時間。

// MinHash double set_similarity(bool A[], bool B[], int range) { int c = 0; // 交集大小 int d = 0; // 聯集大小（和抽樣次數一樣，其實可以省略。） for (int i=0; i<5; i++) // 抽樣5次 { // 創造新的雜湊函數（此處沒有實作，這是虛擬碼。） int (*hash)(int,int) = new_hash_function(); int headA = 2147483647; for (int j=0; j<range; j++) if (A[j]) headA = min(headA, hash(j, range)); int headB = 2147483647; for (int j=0; j<range; j++) if (B[j]) headB = min(headB, hash(j, range)); if (headA == headB) c++; d++; } return (double)c / d; }

範例：快速排序法（Quicksort）

挑選一個數字當作基準，所有數字分成大的一邊和小的一邊，遞迴下去。

無論挑選哪一個數字當作基準，最終都會得到正確結果。

然而，隨機挑選基準，不是最好的方式。挑選中位數當作基準，讓數字對半分，讓遞迴次數最少，才是最好的方式。

中位數無法預測。實務上是將陣列三等份，以三個中央數的中位數當作基準。因為上一層遞迴已經數字分成兩邊、大致排序過了，所以這種方式更容易接近中位數。

範例：平面上距離最近的兩個點（Closest Pair）

挑選一個點對距離當作方格寬度，建立方格紙。最近點對只會在相同方格、相鄰方格。窮舉田字，窮舉田字裡面所有點對，取距離最小者。

無論挑選哪一個距離當作寬度，最終都會得到正確結果。

然而，隨機挑選距離，不是最好的方式。實務上是挑選最近距離三倍以下的距離當作方格寬度。做法請參考：

Streaming Algorithm

現在是資訊爆炸的年代，資料不斷增加。「串流演算法」就是處理源源不絕的輸入資料。大家關注的有：

online：隨時處理資料，甚至隨時計算正確答案。
one-pass：只讀取一次資料，盡量計算正確答案。
memory-bounded：資料無法盡數儲存，盡量計算正確答案。

範例：統計數字數量

先排序，再統計。

void histogram(int array[], int n) { sort(array, array+n); int c = 1; for (int i=1; i<n; i++) if (array[i] == array[i-1]) c++; else { // 印出統計結果 cout << array[i-1] << ':' << c << '\n'; // 重新計數 c = 1; } // 印出統計結果 cout << array[n-1] << ':' << c << '\n'; }

變成串流。建立陣列，根據數值大小，累計至對應位置。

void histogram(istream& in) { int c[1000000] = {}; int num; while (in >> num) { c[num]++; cout << c[num]; } }

減少記憶體。格子少於數值範圍，只好使用雜湊函數。相異數字可能存入相同格子，無法精確統計。

int hash(int num, int range) { return num % range; } void histogram(istream& in) { // 統計表格，範圍0到9。 int c[10] = {}; int num; while (in >> num) { // 以雜湊函數決定累計位置。 int h = hash(num, 10); c[h]++; cout << c[h]; } }

建立多個統計表格，使用不同雜湊函數，分散風險。推定最小值為統計結果。

int hash1(int num) {return num % 10;} int hash2(int num) {return num % 9;} int hash3(int num) {return num * num % 10;} // Count–Min Sketch void histogram(istream& in) { // 3個統計表格 int c[3][10] = {}; // 3種雜湊函數 int (*hash[3])(int) = {hash1, hash2, hash3}; int num; while (in >> num) { int count_min = 2147483647; for (int i=0; i<3; i++) { // 以雜湊函數決定累計位置，分散風險。 int h = hash[i](num); c[i][h]++; // 取最小值 count_min = min(count_min, c[i][h]); } cout << count_min; } }

範例：相異數字個數

先排序，再統計。

int count_distinct(int array[], int n) { sort(array, array+n); int x = 0; if (n > 0) x = 1; for (int i=1; i<n; i++) if (array[i] != array[i-1]) x++; return x; }

變成串流。建立陣列，根據數值大小，累計至對應位置。

void count_distinct(istream& in) { int c[1000000] = {}; int x = 0; int num; while (in >> num) { if (!c[num]) x++; c[num]++; cout << x; } }

減少記憶體。格子少於數值範圍，只好使用雜湊函數。相異數字可能存入相同格子，無法精確統計。

void count_distinct(istream& in) { // 統計表格，範圍0到9。 int c[10] = {}; int x = 0; int num; while (in >> num) { // 以雜湊函數決定累計位置。 int h = hash(num, 10); if (!c[h]) x++; c[h]++; cout << x; } }

再減少記憶體。任意一個二進位數字，最低的位元1，不存在的機率差不多是0，位於第一低位數的機率是1/2，位於第二低位數的機率是1/4，……，位於第i低位數的機率是1/2ⁱ。

更進一步，任意2ⁱ個相異二進位數字，最低的位元1，涵蓋前i低位數的機率差不多是1。邏輯有點奇怪，姑且當作是這樣吧。

每讀一個數字，先套用雜湊函數得到新數字，再找到最低位元1，並紀錄其位置。若涵蓋前i低位數，則推定2ⁱ是相異數字個數。

雜湊函數宛如隨機排列。重新打亂數字，讓位元1均勻分布，以便迎合上述機率。重新打亂數字，不影響相異數字個數。

// Flajolet–Martin Sketch void count_distinct(istream& in) { // 統計表格，總共32位元，僅使用其中31位元。 // 範圍0到2147483647。 unsigned int mask = 0; int num; while (in >> num) { int h = hash(num, 2147483647); // 找到最低位元1 int lsb1 = 31; for (int i=0; i<31; i++) if (h & (1 << i) == 1) { lsb1 = i; break; } // 並紀錄其位置 // mask |= (1U << lsb1); if (h > 0) mask |= (1U << lsb1); // 避免之後溢位 // 找到連續的位元1 // 換句話說，找到最低位元0。 int lsb0 = 31; for (int i=0; i<31; i++) if (mask & (1U << i) == 0) { lsb0 = i; break; } // 推定2ⁱ是相異數字個數 cout << (1U << lsb0); } } // Flajolet–Martin Sketch void count_distinct(istream& in) { unsigned int mask = 0; int num; while (in >> num) { int h = hash(num, 2147483647); // 利用內建函式，得到最低的位元1。 if (h > 0) mask |= (1U << __builtin_ctz(h)); // 利用內建函式，得到最低的位元0。 unsigned int x = 1U << __builtin_ctz(mask + 1U); // 經實驗發現，除以0.77351，答案更精準。 cout << floor(double(x) / 0.77351); } }

範例：尋找陣列裡的最小值

趁早找到最小值，不想看遍全部數字。

前n/e個，記錄最小值。第n/e + 1個以後，如果小於最小值，就推定為答案。

實際應用：找伴侶、買水果、炒短線。

// Gilbert–Mosteller Strategy int find_minimum(int array[], int n) { int k = floor((double)n / exp(1)); int min = 2147483647; for (int i=0; i<k; i++) if (array[i] < min) min = array[i]; for (int i=k; i<n; i++) if (array[i] < min) return array[i]; return min; }

範例：隨機抽樣（Random Sampling）

隨機挑選一物，機率均等。

int random_sampling(int array[], int n) { srand(time(0)); return array[rand() % n]; }

變成串流。使用動態陣列。

void random_sampling(istream& in) { vector<int> array; // 動態陣列 int num; for (int i=0; in >> num; i++) { array.push_back(num); cout << array[rand() % (i+1)]; } }

節省記憶體，只需儲存一物。從1開始編號，遭遇第i物時，儲存機率1/i，捨棄機率1 - 1/i。

最終得到第i物的條件是：保留第i物，捨棄第i+1物到第n物。機率恰是1/n：

   1           1             1                   1
  ——— × ( 1 - ——— ) × ( 1 - ——— ) × ... × ( 1 - ——— )
   i          i+1           i+2                  n 

   1     i    i+1         n-1    1
= ——— × ——— × ——— × ... × ——— = ———
   i    i+1   i+2          n     n

最終得到各物的機率，推導過程如法炮製，機率均是1/n。

// Reservoir Sampling void random_sampling(istream& in) { srand(time(0)); int result = 0, num; for (int i=0; in >> num; i++) { if (rand() % (i+1) < 1) result = num; cout << result; } }

範例：隨機混洗（Random Shuffle）

遭遇第i物時，第i物與後面挑一物對調。

// 產生[0,x)的隨機整數。 inline int rand(int x) {return rand() % x;} // 產生[x,y)的隨機整數。 inline int rand(int x, int y) {return x + rand(y - x);} // Fisher–Yates Shuffle void random_shuffle(int array[], int n) { srand(time(0)); for (int i=0; i<n-1; i++) swap(array[i], array[rand(i, n)]); }

隨機混洗可以串流嗎？我也不知道。哎喲隨便啦。