Microsoft PowerPoint - 10b Design Recursive Solutions.ppt [相容模式]

Transcription

1 如何設計遞迴函式 Pei-yih Ting 遞迴函式 遞迴 (recursive) 函式是自己呼叫自己的函式 在呼叫自己之前一定有 if- 一類的選擇判斷敘述, 以避免無窮盡的遞迴呼叫 函式中至少有一條控制路徑不包含遞迴呼叫, 稱為 base case 函式一定有輸入參數, 用來指定所解決問題的規模 例如 : int sum(int n) { if (n==) urn ; urn sum(n-1) + n; 1+++n 運用遞迴方式撰寫程式的好處 : 對於適合用遞迴方式解決的問題來說 程式碼的表達性比較高, 容易看懂, 容易偵錯 程式比較精簡, 不需要額外實作堆疊來輔助運算 遞迴函式 (cont d) 適合用遞迴方式解答的問題特徵 Recursive structure 一個大問題的解可以藉由一或多個子問題的解來合成出來 ; 問題本身能夠用分治法 (divide-and-conquer, 各個擊破 ) 解而且解答的形式一致的 ; 另外問題的拆解必須是有效率的 配合樹狀資料結構的處理函式 ( 包含樹狀結構的搜尋 ), 尤其是需要運用堆疊來輔助解決的問題 遞迴函式的缺點 : 需要藉由 memoization 來加速 執行時需要比較多的記憶體 ( 系統堆疊 ), 只有在所解決的問題大小不會用完系統堆疊時程式才能正確運作 ; 一個簡單的迴圈需要使用 O(1) 的常數記憶體, 寫成等效的遞迴函式在執行時會用掉 O(n) 的系統堆疊空間 執行時有可能需要很多的時間 : 例如一個計算第 n 個 Fibonacci 數列元素的遞迴程式需要 O( n ) 的運算時間, 相對地一個迴圈版本的程式 ( 動態規劃 ) 只需要 O(n) 的運算時間 遞迴函式 (cont d) 遞迴是一種重複 (repetition) 的程式架構 迴圈程式架構可以轉成遞迴函式 可以用遞迴解的問題, 一定也可以用迴圈解, 至少可以自己用輔助的堆疊資料結構配合迴圈來完成, 不過有很多運用遞迴解很直覺的問題, 運用迴圈解需要特別的觀察以及演算法 交互遞迴 (mutually recursive) 函式 f() 呼叫函式 g(), g() 再呼叫 f() 也是一種遞迴, f() 間接地呼叫 f() 自己 尾端遞迴 (tail-recursive) 每一個遞迴呼叫完成後沒有任何其它動作, 只回傳該數值例如 : urn tail_rec_fun(p1, p); 下列三個例子都不是 urn rec_fun(p1, p) + 1; r = rec_fun(p1, p); printf("%d\n", p1); urn r; 4

2 遞迴函式 (cont d) rec_func(p1,p); urn rec_fun(p,p1); 尾端遞迴的函式在設計時不需要特別注意遞迴函式呼叫的深度, 很多編譯器都可以最佳化程式碼 (VC: /O1 /O), 概念上在呼叫下一層遞迴函式時除了更換呼叫引數的內容外, urn address 以及區域變數所用到的空間是完全一樣的, urn address 的內容也是完全不變的, 呼叫的時候沿用原先的堆疊框就可以, 不需要像呼叫一般的函式一樣建立新的堆疊框, 維持 urn address 不變相當於最後處理到 base case 時 urn 一次就回到最上層的呼叫端, 請注意最佳化程式並不會把尾端遞迴直接換成迴圈 尾端遞迴函式有特別的設計方法 ( 對相同問題來說, 參數比一般遞迴函式多 ) 與問題拆解方法, 和一般遞迴函式直覺的表示方法有一些差別, 不過有時候為了解除遞迴深度對程式設計的限制, 反而犧牲掉了遞迴函式精簡易讀的特性 5 遞迴函式的設計方法 基本步驟 a. 定義出遞迴函式以及其參數 ( 遞迴函式一定需要 ) b. 想清楚這個遞迴函式在某一參數時能夠解的問題是什麼 c. 把需要解決的問題拆解為較小的問題 d. 呼叫遞迴函式解決這個小問題, 並且用這個答案組合出原來問題的答案 e. 問題縮到最小時 (base case) 可以直接寫出答案 例如 : 計算陣列 data[] 裡 n 個元素 data[]data[n-1] 的總和 a. int sum(int data[], int n) b. 這個函式能夠計算並回傳 data[]+data[1]++data[n-1] c. 拆解為小一點的問題 : n-1 個元素的總和 d. sum(data, n-1) 可以算出 data[]++data[n-], 所以 sum(data, n) 的結果應該是 sum(data, n-1) + data[n-1] e. sum(data, ) 的結果是 6 int arraysum1(int data[], int n) { if (n==) urn ; urn arraysum1(data, n-1) + data[n-1]; 前面這個範例裡, 呼叫 sum(data, n) 以後會依序呼叫 sum(data, n-1), sum(data, n-),, sum(data, ) 共 n+1 次遞迴函式呼叫, 遞迴深度 n+1, 才能夠計算出答案 在撰寫遞迴函式時, 前面這樣的問題拆解方式是比較沒有效率的, 需要 O(n) 次的函式呼叫, 在許可的情況下應該盡量尋找遞迴深度淺一些的問題拆解方法, 例如在計算陣列 data[] 裡 n 個元素 data[]data[n-1] data[n 的總和時, 可以考慮拆成下面兩個子問題 : 計算 data[]data[(n-1)/] 的總和以及計算 data[(n+1)/]data[n-1] data[n 1] 的總和最後把兩者加總起來 ; 這個例子裡遞迴函式呼叫的次數沒有減少, 更理想的狀況是函數呼叫的次數也盡量降低 7 a. int sum(int data[], int istart, int iend) b. 這個函式能夠計算並回傳 data[istart]++data[iend] +data[iend] c. 拆解為兩個小一點的問題 : 計算 (iend-istart+)/ istart+)/ 及 (iend-istart+1)/ istart+1)/ 個元素的總和 sum(data, istart, istart+(iend-istart)/) 算出 data[istart]+data[istart+1]++data[istart+(iend-istart)/] [ ] [ ] sum(data, istart+(iend-istart)/+1, iend) 算出 data[istart+(iend-istart)/+1]++data[iend] d. 因此 sum(data, istart, iend) 的結果應該是上述兩者之和 e. sum(data, i, i) 的結果是 data[i] int arraysum(int data[], int istart, int iend) { if (istart==iend) urn data[istart]; urn arraysum(data, istart, istart+(iend-istart)/) + arraysum(data, istart+(iend-istart)/+1, iend); 8

3 函式 int sum(int data[], int istart, int iend) 有三個參數, 目的是希望函式裡處理 data[istart]data[iend] 這 iend-istart+1 筆整數資料,data[]data[istart-1] 是沒有用到的, 所以前兩個參數其實可以合併在一起, 只傳遞 data[istart] 的位址當作是陣列的起始記憶體位址, 可以更進一步簡化為兩個參數的版本 : int sum(int *startdata, int ndata), 其中 startdata 存放 data[istart] t t] 陣列元素的記憶體位址, 代表由 &data[istart] t t] 開始的後半段資料陣列,ndata 則為資料的筆數, 遞迴呼叫時這些參數會保存在堆疊框上, 少一個參數也降低一點點需要的堆疊記憶體, 同時程式的描述會比較簡潔和直覺一些 int arraysum(int data[], int n) { if (n==) urn ; int *data if (n==1) urn data[]; urn arraysum(data, (n+1)/) + arraysum(&data[(n+1)/], n/); 9 Fibonacci a. int fibonacci(int n) b. 這個函式計算並回傳 f(n)=f(n-1)+f(n-), f(1)=f()=1 f() 1 c. 拆解為兩個小一點的問題 : 計算 f(n-1) 與 f(n-) d. 由 fibonacci(n-1) 及 fibonacci(n-) 合成出 fibonacci(n) 的結果, 也就是 fibonacci(n)=fibonacci(n-)+fibonacci(n-1) e. fibonacci() 以及 fibonacci(1) 都是 1 int fibonacci(int n) { if ((n==) (n==1)) urn 1; urn fibonacci(n-) + fibonacci(n-1); 這樣子設計出來的程式很簡潔, 但是執行起來需要呼叫 fibonacci 函式 O( n ) 次, 其中很多次的參數是一樣的, 所以執行效率很不好, 如果配合使用額外的陣列的話, 就很有效率了, memoization, 如果用陣列配合迴圈來寫的話 dynamic programming 1 Fibonacci Applications Rabbit breeding Stair climbing f(n) = f(n-1) + f(n-) 第 1 個月買了一對幼兔第 n-1 個月有第 n- 個月有 第 個月長大為成兔 f(n-1) 對兔子 f(n-) 對兔子 第 個月生下一對幼兔 ( 成兔和幼兔 ) 養了一個月都是成兔了 第 n-1 個月時都已經是成兔, 這個月都生了一對小兔子 Rays through glasses f(5) = f(4) + f() Mario 每一步可以爬一級或兩級, 爬到最上面總共有多少種方法最後一步 f()= 最後一步 , 1 1 1, 1 1 1, 爬一級 f()+f(1) 爬二級 ( ), , 1, 1 reflect f() once f(1) f() = f(1) + f() 11 Subset Sum a. int subsetsum(int data[], int n, int target) b. 判斷是否 data[]data[n-1] [ ] 中某些數字的和是 target c. 拆解為兩個小一點的問題 : data[n-1] 不在內, data[]data[n-] 中某些數字的和是 target; data[n-1] 在內, data[]data[n-] 中某些數字的和是 target-data[n-1] d. data[n-1] 在或不在集合內這兩種狀況中只要有一種可以找到答案, target 就可以表示成這 n 個數字的子集合的和, 所以是 兩個結果 e. target 如果是 當然空集合就是答案 ; n 如果是 且 target!= 則一定沒有答案 int subsetsum(int data[], int n, int target) { if (target==) urn 1; if (n==) urn ; urn subsetsum(data, n-1, target) subsetsum(data, n-1, target-data[n-1]); 程式執行起來需要呼叫 subsetsum 函式 O( n ) 次, 雖然概念表達的很清楚, 但是執行效率很不好 ( 本來就是 NP-complete 的問題 ) 1

4 GCD and LCM a. int gcd(int m, int n) // precondition: m>=n> b. 這個函式計算並回傳 m 與 n 的最大公因數 c. 拆解為小一點的問題 : gcd(n, m%n) d. gcd(m, n) = gcd(n, m%n) e. 如 m 為 n 的整數倍, gcd(m, n) = n // assume m >= n > int gcd(int m, int n) { int ans; if (m % n == ) ans = n; ans = gcd(n, m % n); urn ans; int lcm(int m, int n) { urn m * n /g gcd(m, n); 1 二分搜尋法 (Binary Search) 假設資料陣列 data[] 中的資料已經由小到大依序排列 a. int binarysearch(int data[], int start, int end, int target) b. 這個函式在整數陣列元素 data[start] t t] 到元素 data[end] d] 之間尋找 target, 找到了回傳 target 在陣列中的位置, 找不到回傳 -1 c. 拆解為小一點的問題 : 原來是在 start 到 end 之間, 拆成更小的區間 d. center=(start+end)/, 如果 target 比 data[center] 大, 就在 [center+1,end] 區間中尋找, 反之在 [start,center-1] 間尋找 e. 如果 target == data[center] 就找到了如果 end < start 就沒有任何元素在區間裡, 一定找不到 int binarysearch(int data[], int start, int end, int target) { int center = (start+end)/; if (start>end) urn -1; if (target == data[center]) urn center; if (target > data[center]) urn binarysearch(data, center+1, end, target); urn binarysearch(data, start, center-1, target); Tail-recursive 14 最大乘積的整數拆解方法 最大乘積的整數拆解方法 (cont d) 一個正整數 n 可以分解成較小正整數的和, n = a 1 +a ++a k, 請寫一個程式找到一種分解方法能夠使得乘積 a 1 a a k 最大 遞迴設計 a. int findmaxprod(int n) b. 這個函式計算並回傳最大乘積 a 1 a a k 滿足 n = a 1 +a ++a k c. 拆解為兩個小一點的問題 : n 1 =a 1 ++a k, 最大乘積 a 1 a k n =b 1 ++b +b, 最大乘積 b 1 b int findmaxprod(int n) { int i, max=n, prod; if (n<=4) urn n; for (i=1; i<=n/; i++) { prod = findmaxprod(i)* findmaxprod(n-i)); i)); if (prod > max) max = prod; urn max; 該怎麼辦? 又需要 memoization 了, 每個正整數至少有一種最大乘積的拆解方法, 走過就要留下痕跡, 算過就要記錄下來, 不要浪費時間和能量重複計算相同的東西 就像是費氏序列或是組合數的計算一樣, 運用遞迴 / 陣列, 或用迴圈 / 陣列來設計, 是標準的動態規劃最佳化方法 將每個正整數拆解開的最大乘積記錄在陣列 P(i) 裡 : 滿足 n=n 1 +n, 在這種分解法下最大乘積為 a 1 a a k b 1 b b d. n 不拆開的話, 乘積就是 n, 將 n 拆為 n 1 +n 的方法總共有 n/ 種, 在這些分解方法下找到乘積的最大值就是我們的答案 e. n <= 4 時不拆解就可以得到最大值, 也就是 n 這個程式很短很容易了解, 但是最大的問題就在效率, 你可以想像呼叫 findmaxprod() 時, findmaxprod(5) 被呼叫了 1684 次嗎? 15 i P(i) x*... P(11) = 54 = * * * P(i) = max { x P(i-x) 1 x i x* = argmax { x P(i-x) 1 x i

5 i P(i) P(i) = max { x P(i-x) 1 x i x*... x* = argmax { x P(i-x) 1 x i 陣列 迴圈... 順向 DP 遞迴... 逆向 DP int P[1]={1,,,4, xstar[1]={; int i, j, n=11; for (i=5; i<=n; i++) for (P[i]=1*P[i-1],xstar[i]=1,j=; j<i; j++) if (j*p[i-j]>p[i]) P[i] = j*p[i-j], j] xstar[i] = j; int maxprod(int P[], int xstar[], int i) { if (P[n]>) urn P[n]; int j, tmp; for (P[i]=1*maxProd(P, xstar, i-1), 這個遞迴和前面的遞迴不同 xstar[i]=1,j=; j<i; j++) if (j*(tmp=maxprod(p, xstar, i-j))>p[i]) P[i] = j*tmp, xstar[i] = j; Rod cutting, String Partition, Unbounded Knapsack, 迴文判別 Palindrome "A man, a plan, a canal, Panama!" "Amor, Roma" "race car" "taco cat" "WasitacaroracatIsaw?" a a cat saw? "No 'x' in Nixon" 一個字串去掉標點符號和空白以後由前面看和後面看一模一樣 a. int ispalindrome(int len, char buf[]) // 已去除標點符號和空白 b. 這個函式檢查字元陣列 buf[] 中的字串是否為迴文 c. 拆解為長度短一點的問題 : 檢查去除第一個字元和最後一個字元以後的長度 len- 字串是否為迴文 d. 第一個字和最後一個字相同且 ispalindrome(len-,buf+1) 為真則原字串是一個迴文 int ispalindrome(int len, char buf[]) { e. 長度為 1 或是 的字串都是 if (len <= 1) urn 1; 迴文 The Sator Square S A T O R A R E P O T E N E T O P E R A R O T A S if (buf[]!= buf[len-1]) urn ; urn ispalindrome(len-, buf+1); &buf[1] 18 河內塔 Towers of Hanoi 將一疊由小到大的的盤子由一個柱子上移到另外一個柱子上, 並且維持原來的順序 : 每一個步驟只能移動一個盤子 任何時候, 大的盤子不可以放在比它小的盤子之上 有一個輔助的柱子可以使用 A B C 1 4 程式輸出 1, A -> B, A -> >C 1, B -> C, A -> B 1, C -> A, C -> B 1, A -> B 4, A -> C 1, B -> C, B -> >A 1, C -> A, B -> C 1, A -> B, A -> C 1, B -> C 19 a. void move(char from_peg, char to_peg, char aux_peg, int ndisks) b. 印出由 from_peg 柱子搬 ndisks 個盤子到 to_peg 柱子的步驟, 過程中以 aux_peg 柱子為輔助, 避免大盤子在小盤子之上 c. 拆解為三個小一點的問題 : 個 ndisks-1 以及 1 個直接移動 d. 由子問題的解合成整個問題的解 : 運作條件 : aux_peg 柱子上如果有盤子的話, 需要大於 from_peg 柱子上最上面的 ndisks-1 個盤子,to to_peg 柱子上如果有盤子的話, 需要大於 from_peg 柱子上最上面的 ndisks 個盤子 由 from_peg 柱子搬 ndisks-1 個盤子到 aux_peg 柱子 由 from_peg 柱子搬 1 個盤子到 to_peg 柱子 由 aux _p peg 柱子搬 ndisks-1 個盤子到 to _p peg 柱子假設原來 to_peg 柱子以及 aux_peg 柱子上沒有比 from_peg 柱子最上面算起第 ndisks 個盤子小的盤子, 所以可以用上面的三個步驟來完成 ; 接下來考慮過程中兩次移動 ndisks-1 個盤子, 在三個柱子上也沒有比這 ndisks-1 個盤子小的, 所以可以再用上面的三個步驟來完成 e. ndisks=1 時 : to_peg 柱子上的盤子比 from_peg 柱子上第一個盤子大的話, 直接搬移

6 move('b','a','c',); move('b','c','a',1); move('a','c','b',); 程式輸出 move('b', 'C', 'A', ); 1, B -> C, B -> A 1, C -> A, B -> C 1, A -> B, A -> C 1, B -> C A B C 1 4 Move top disks from peg B to peg C using peg A as auxiliary peg move('b','c','a',1); move('b','a','c',1); move('c','a','b',1); move('a','b','c',1); move('a','c','b',1); move('b','c','a',1); 1 Tower of Hanoi (cont d) 1 void move(char from_peg, /* input - characters naming */ char to_peg, /* the problem's */ char aux_peg, /* three pegs */ 4 int ndisks) { /* input - number of disks to move */ 5 if (ndisks == 1) { 6 printf("move disk 1 from peg %c to peg %c\n", from_peg, to_peg); 7 { 8 move(from_peg, aux_peg, to_peg, ndisks - 1); 9 printf("move disk %d from peg %c to peg %c\n", ndisks, from_peg, to_peg); 1 move(aux_peg, to_peg, from_peg, ndisks - 1); 11 1 請注意這樣子移動的次數一定是最少的, 如果是只有一個碟子時, 只要移動 a 1 = 1 次, 如果只有兩個碟子時, 只要移動 a = 次,, 如果有 n 個碟子時, 你知道最大的碟子至少要移動 1 次, 但是在移動它之前, 要把上面 n-1 個碟子都先移到輔助的柱子上 ( 由 from_peg 到 aux_peg), 那麼最少要移動 a n-1 次, 然後移動最大的碟子 ( 由 from_peg 到 to_peg), 然後再把輔助的柱子上面的 n-1 個碟子移到目標柱子上, 又需要 a n-1 次, 總共需要移動 a n = a n 次 Recursively Iteratively Counting Upward int main() { data[pivot]data[ndata-1] int main() { int data[4], ndata=4; int data[1]; for (i=; i<ndata; i++) countup(4, data, ); data[i] = 1; urn ; n n n for data[]<=ndata; next(ndata, data)) (; a b (, print(ndata, data); void countup(int ndata, int data[], int pivot) { urn ; 1 1 if (pivot==ndata) 11 1 e print(ndata, data); void next(int ndata, int data[]) { 1 1 for (data[pivot]=1; int i; data[pivot]<=ndata; data[pivot]++) c d countup(ndata, for (i=ndata-1; data, i>; i--) pivot+1); if (data[i]<n) void print(int ndata, { data[i]++; int data[]) urn; { printf("%d", data[]); // ndata> for (int i=1; i<ndata; data[i] = i++) 1; printf(" data[]++; %d", data[i]); printf("\n"); countup() ) pivot 1 countup(1) countup() countup() countup(4) ndata void countup (int ndata, int data[], int pivot ) { if ( pivot==ndata ) on and on print(ndata, t data); for ( data[pivot]=1 ; data[pivot]<=ndata; data[pivot]++ ) countup(ndata, data, pivot+1) ; 4

7 Some saving on the last level of recursive function call void countup(int ndata, int data[], int pivot) { for (data[pivot]=1; data[pivot]<=ndata; data[pivot]++) if (pivot<ndata-1) countup(ndata, data, pivot+1); print(ndata, data); 5 列印出 n 個數字的所有排列方法 問題拆解 1 permutations of {,, 4 permutations of {1,, 4 permutations of {, 1, 4 4 permutations of {,, 1 for (i=; i<n; i++) a[i] = i+1; permutation(a,, n-1); void permutation(int perm[], int start, int end) { if (start == end) printperm(perm, end+1); for (int i=start; t; i<=end; i++) { swap(&perm[start], &perm[i]); permutation(perm, start+1, end); swap(&perm[start], &perm[i]); Recursive (n,k)-combinations level C(5,) start n-(k-level) start 1 n-(k-level) select level-k elements from seq[start]seq[n-(k-level)] and put the result to result[level]result[k-1] [ ] comb(n,k,seq,,,result); void comb(int n, int k, const int seq[], int start, int level, int result[]) { if (level==k) print(result, k); // result[]result[k-1] for (int i=start; i<=n-(k-level); i++) result[level] = seq[i], comb(n, k, seq, i+1, level+1, result); startn-(k-level) levelk-1l seq result 1 7 快速排序法 (Quick Sort) 範例 : 9, 5, 1, 19,, 6, 4, 15, 8,, 7 目標 :,, 4, 5, 6, 7, 8, 9, 1, 15, 19 遞迴函式設計 : 分治法 (Divide and Conquer): 切割問題, 各個擊破 每一步驟挑選一個元素放在正確的位置上, 將其它數字分為兩群, 比這個元素大或是等於的放右邊, 小於的放左邊例如 : 將第一個元素 9 放在正確位置上 9 {5,, 6, 4, 8,, 7 {1, 19, 15 如此就可以得到兩個元素個數比較少的排序問題 問題 : 怎麼把 9 放在正確的位置上? 把 9 和其它數字一個一個比較就可以 ; 怎樣才能夠有效率地分成兩群? 8

8 快速排序法 (cont d) istart front 9, 5, 1, 19,, 6, 4, 15, 8,, 7 步驟 1. while rear>istart && data[rear]>=data[istart] data[istart] rear-- 步驟. while front<iend && data[front]<data[istart] front++ 步驟. if rear>front 交換 data[front++] 及 data[rear--] 重複步驟 1 至步驟 iend rear 9, 5, 1, 19,, 6, 4, 15, 8,, 7 front 9, 5, 1, 19,, 6, 4, 15, 8,, 7 front 9, 5, 7, 19,, 6, 4, 15, 8,, 1 front 9, 5, 7,,, 6, 4, 15, 8, 19, 1 直到 front > rear 9, 5, 7,,, 6, 4, 8, 15, 19, 1 (i.e. while (front < rear) { ) 交換 data[istart] 及 data[rear], 以 data[rear] 為分割點得到兩個長度比較短的排序問題 rear 9, 5, 7,,, 6, 4, 8, 15, 19, 1 8, 5, 7,,, 6, 4, 9, 15, 19, 1 rear rear 9 void quick_sort(int array[], int n) { if (n > ) { int pivot = place_midst(array, n); 版本 1 quick_sort(array, pivot); quick_sort(&array[pivot+1], n - pivot - 1); if (n == ) if (array[]>array[1]) swap(array,, 1); int place_midst(int array[], int n) { // 將 array[] 放到正確位置 array[pivot] // 而且比較小的放在前半, >= 的放在後半 void swap(int array[], int i, int j) { // 交換陣列元素 array[i] 及 array[j] void quick_sort(int array[], int istart, int iend) { if (iend-istart istart > 1) { 版本 int pivot = place_midst(array, istart, iend); quick_sort(array, istart, pivot-1); quick_sort(array, pivot+1, iend); if (iend-istart == 1) if (array[istart]>array[iend]) swap(array, istart, iend); int place_midst(int t array[], int istart, t int iend) d){// 將 array[istart] t] 放到正確位置 // array[pivot], 而且比較小的放在 // 前半, >= 的放在後半 快速選擇法 (Quick Select) 範例 : 9, 5, 1, 19,, 6, 4, 15, 8,, 7 目標 : 找到數列中第 k 小的數字 遞迴函式設計 : Partition-based Selection algorithm 每一步驟挑選一個元素放在正確的位置上, 將其它數字分為兩群, 比這個元素大的放左邊, 小的放右邊 ( 前面的 place_midst) 例如 : 將第一個元素 9 放在正確位置第 8 格內 9 {5,, 6, 4, 8,, 7 {1, 19, 15 如果 8 就是 k, 我們已經找到第 k 小的數字了 如果 8 比 k 大, 顯然第 k 小的數字在前半段 如果 8 比 k 小, 顯然第 k 小的數字在後半段 1 快速選擇法 (cont d) void quick_select(int kth, int array[], int istart, int iend) { if (iend-istart > 1) { int pivot = place_midst(array, istart, iend); if (pivot==kth-1) urn pivot; if (pivot>kth-1) urn quick_select(kth, array, istart, pivot-1); urn quick_select(kth, array, pivot+1, iend); if (iend-istart == 1) if (array[istart]>array[iend]) swap(array, istart, iend); urn kth-1; int place_midst(int array[], int istart, int iend) { // 將 array[istart] 放到正確位置 // array[pivot], 而且比較小的 // 放在前半, >= 的放在後半 void swap(int array[], int i, int j) { // 交換陣列元素 array[i] 及 array[j]

9 迷宮路徑搜尋 右圖二維陣列代表一個迷宮路徑, 空格代表可以走的通道, 代表不 end 能走 ; 由左下角座標 (8, ) 的位置開始 走, 目標是左上角座標 (, 8) 的位置 在每一個位置上, 允許左上右下四個方 1 向前進, 除非無法前進了, 否則不會後退, 也不能走出邊界 如右下圖, 這是一個路徑搜尋的問題, 一 4 旦走到某一個位置, 接下來最多有四種走 5 法, 程式需要一種一種嘗試, 都無法前進的 6 話 ( 有可能走出邊界, 有可能是障礙物, 有 7 可能是由那個地方走過來的, 也有可能先 8 前已經經過了 ) 要倒退回去嘗試下一個選擇 start (8,) 我們會用深度優先的搜尋方法 (Depth First Search, DFS), 遇見第一個可行的走法就一直 走下去直到沒路為止, 退回最接近而還沒有嘗 試過的選擇, 因此需要一個堆疊, 記錄所有還沒 有試過的選擇, 由堆疊上拿出來的是最後放進去的 迷宮路徑搜尋 直覺的迴圈作法 int i = ; // : 左, 1: 上, : 右, : 下 static const int dirs[][] = {{-1,, {,1, {1,, {,-1; while ((cur!=target) (cury!=targety)) { // 還沒走到目的地 if (board[cur+dirs[i][]][cury+dirs[i][1]]==-1) // 死路或是撞牆 i = (i+1) % 4; // 下一個方向 cur += dirs[i][], ], cury += dirs[i][1], ], i=; 簡單的講這個程式的邏輯就是 有路就往前走 問題 有路就一直往前走, 萬一繞圈圈怎麼偵測出來? 四個方向順序嘗試, 需要避開先前走過來的路, 否則有機會變成不斷地來回走 走到死路或是撞牆時, 該怎樣退回前面哪一個方向或是哪一格? 然後哪一個方向已經嘗試過, 該繼續試哪一個方向? 4 a. int maze(int width, int height, char board[][], 方法一 int cur, int cury, int target, int targety, char path[][], int npath) b. 這個函式延伸 path[] 陣列內長度是 npath 的部份路徑, 搜尋由 (cur,cury) cury) 開始到 (target,targety) targety) 的路徑, 如果找到一條路徑, 就回傳 1, 同時陣列 path[]path[npath-1] 就是完整路徑 ; 如果沒有找到任何路徑就回傳 ; board 陣列中除了記錄牆壁 / 障礙, 也標示所經過的路徑, 以免不斷地繞圈圈 c. 拆解為小一點的問題 : 每一次在某一條路徑上往前走一步時, 就靠近目的地一點, 又可以運用這個 maze 函式來搜尋接下去的路徑 d. 每一次到達一個位置 (cur,cury), 有四個方向可以測試, 其中有一個是上一步的位置, board[][]==; 不能走的, board[][]==-1; 可以走的, board[][]==; 針對每一個可以走的, 嘗試往前走一步, 把這一步記錄在 path[] 陣列並且呼叫 -1 maze(width, height, board, cur+dirs[i][], cury+dirs[i][1], target, targety, path, npath) e. (cur==target)&&(cury==targety) 就表示 -1-1 走到目的地了 二維陣列 int board[][]; // 打算處理 x 的迷宮, 周圍保留一列一行內容為 -1, 代表牆壁, 這樣子在程式內部測試時不需要特別去檢查有沒有超過邊界 -- 用 if 敘述去檢查陣列的註標是不是在範圍內 1 row height, 1 col width 不過這樣子宣告的話, 迷宮的實際座標就在 (1,1)-(width,height) 中間, 和平常陣列註標在 (,)-(width-1,height-1) 有一點點位移, 我們也可以在宣告的地方稍微動一點手腳, 讓我們保持一般的陣列使用方法, 但是又可以有希望有的邊界 能不能定義一個 (-1,-1)-(width,height) 1) ( h i ht) 的陣列? int board[][]; int (*board)[] = (int (*)[]) &board[1][1]; for (i=-1; i<=height; i++) board[i][-1] = board[i][width] = -1; for (i=; i<height; i++) for (j=; j<width; j++) board[i][j] = ; for (j=; j<width; j++) board[-1][j] = board[height][j] = -1; 6

10 int maze(int width, int height, char board[][], int cur, int cury, int target, int targety, char path[][], int npath) { // : 左,1: 上,: 右,: 下 static ti const int dirs[][] = {{-1,, 1 {,1, {1 {1,, {1 {,-1; if ((cur==target)&&(cury==targety)) urn 1; board[cur][cury] = ; // 標示已經走過此格 for (int i=; i<4; i++) if (board[cur+dirs[i][]][cury+dirs[i][1]]==) { path[npath][] = cur+dirs[i][]; path[npath][1] = cury+dirs[i][1]; if (maze(width, height, board, cur+dirs[i][], cury+dirs[i][1], target, targety, path, npath+1)) urn 1; board[cur][cury] = ; // 四個方向最後都是死路或已經走過, 退回前一層 urn ; 7 迷宮路徑搜尋 執行範例 end (,8) start (8,) 8 迷宮路徑搜尋 退回前一步 很多同學第一次看到前面的遞迴程式時, 可以接受每呼叫一次 maze() 就是往前走一步, 但是有點難想像到底怎麼退回前一步的, 例如下面這個主要程式段落裡, 如果某一次 maze(,next, nexty, ) 的呼叫回傳, 代表如果下一步走 (next, nexty) 是沒有辦法走到目標點的, 所以要繼續嘗試 (cur, cury) 的下一個方向 ( 下一個 i), 這個時候其實就是退回前一步 for (i=; i<4; i++) if (board[next=cur+dirs[i][]][nexty=cury+dirs[i][1]]==) [ ]][ [ ]] if (maze(, next, nexty, )) urn 1; 從另外一種角度描述程式的表現, 前面我們數數字的程式, 當第一位填, 接下來由 (1,1,1) 數到 (n,n,n), 下一個數字就要退到最前面填 ; 現在這個迷宮程式如果你把遞迴函式呼叫時每一層迴圈裡的 i 值 ( 就是每一步是左上右下哪一個方向 ) 列出, 所謂退回前一步, 就是當某一步試完四個 istartiend 方向以後, 回前一格繼續試下一個方向 i n n n 9 前面那個程式中 board[][] 陣列中只記錄了有沒有走過以及牆壁 / 障礙, 其實可以記錄更多的東西, 甚至走過的路徑都可以記下來, 不需要使用額外的 path[][] 陣列 方法二 a. int maze(int width, int height, char board[][], int cur, int cury, int target, int targety) b. 這個函式搜尋由 (cur,cury) 開始到 (target,targety) 的路徑, 如果找到路徑, 就列印路徑並且回傳 1, 如果沒有找到任何路徑就回傳 ; board 陣列中除了記錄牆壁 / 障礙, 也標示由哪裡走過來的, 以免不斷繞圈圈, 同時找到路徑後還可以藉由所記錄的資料印出路徑 ) c. 拆解為小一點的問題 : 每一次在某一條路徑上往前走一步時, 就靠近目的地一點, 又可以運用這個 maze 函式來搜尋接下去的路徑 d. 每一次到達一個位置 (cur,cury), 有上下左右四個相鄰位置 (next, nexty) 可以測試, 其中有一個標示上兩步的位置, board[][]>; 有的不能走, board[][]==-1; 有的可以走, board[][]==; 針對每一個可以走的方向, 嘗試往前走一步, 把這一步的方向 (1: 左,: 上,: 右,4: 下 ) 記錄在 board[next][nexty] 中並且呼叫 maze(width, height, next =cur+dirs[i][], nexty=cury+dirs[i][1], target, targety) e. (cur==target)&&(cury==targety) 就表示到達目的地了 4

11 board[start][starty] = 5; // visited maze(width, height, board, start, starty, target, targety); int maze(int width, int height, char board[][], int cur, int cury, int target, int targety) { static const int dirs[][] = {{-1,, 1 {,1, {1 {1,, {1 {,-1; int next, nexty; if ((cur==target)&&(cury==targety)) { printpath(width, id h height, h board); urn 1; for (int i=; i<4; i++) { next = cur+dirs[i][], nexty = cury+dirs[i][1]; if (board[next][nexty]==) ] { board[next][nexty] = 1+i; // 1: 左, : 上, : 右, 4: 下 if (maze(width, height, board, next, nexty, target, targety)) urn 1; board[next][nexty] = ; urn ; // 四個方向最後都是死路, 退回前一層 41 路徑列印 如何由 board[][] 所記錄的資訊中列印路徑? 遞迴 這是這種尋找路徑問題的標準方法 ( 很多動態規劃的問題裡用到 ) 為什麼需要用遞迴? 怎麼這麼麻煩?? 因為 board[][] 記錄的是如何走到這一個座標點的方法, 所以需要由 (target=, targety=8) 往前追蹤到 (8, ), 這樣子找到的路徑順序就反過來了, 要反序列印如果不用額外的陣列的話, 最簡單的方法就是遞迴, 利用系統的堆疊來完成 void printpath(int width, int height, int board[][], int cur, int cury) { static const int dirs[][] = {{-1,, {,1, {1,, {,-1; if ((cur==8)&&(cury==)) printf("(8,)"); ( ); -1-1 { int prev = board[cur][cury]-1; printpath(width, height, board, cur-dirs[prev][], cury-dirs[prev][1]); printf(" (%d,%d)", cur, cury); void printpath(int width, int height, int board[][]) { printpath(width, height, board,, 8); printf("\n"); 尋找所有路徑 : 某一個方向走下一步達到終點時, 繼續搜尋下一個方向 board[start][starty] = 5; // visited maze(width, height, board, start, starty, target, targety); void maze(int width, int height, char board[][], int cur, int cury, int target, int targety) { static const int dirs[][] = {{-1,, {,1, {1,, {,-1; int next, nexty; if ((cur==target)&&(cury==targety)) { printpath(width, height, board); urn; for (int i=; i<4; i++) { next = cur+dirs[i][], nexty = cury+dirs[i][1]; if (board[next][nexty]==) { board[next][nexty] ] = 1+i; // 1: 左, : 上, : 右, 4: 下 maze(width, height, board, next, nexty, target, targety); board[next][nexty] = ; // 以 (next,nexty) 為起點 // 的已經試完, 退回試下一種走法 4 尋找最短路徑 DFS 可以尋找所有路徑並且記錄最短路徑長度, 不過最短路徑需要重新再執行一次搜尋 在尋找的過程中也可以用目前最短的路徑作為上限, 如果某一條路徑的長度已經超過, 就退回測試下一個可能的選項 Dijkstra s s shortestpath 最短路徑演算法 廣度優先搜尋法 (Breadth First Search, BFS) Dynamic Programming 44

12 字串拼圖 A B D E C 給定一個如右圖的字串二維陣列, 請寫一個程式判斷目標字串是否出現在陣列中, 字串可以上下左右串聯, 也可以彎折, 不可以斜向串聯, 不可交叉, 例如 ABD, DBA, IAT, TAI, ERNM, MNRE 都在陣列中, BDAT, DIAD, DID 都不在陣列中 假設二維字元陣列 board[7][7] 其中第 列, 第 行, 第 6 列, 第 6 行都填入空格來標示邊界 ; 一維字元陣列 target[] 裡有長度 len 的目標字串 如下圖先簡化這個問題成為 target 目標字串與以 board[ix][iy] 為起點的所有字串比對, 比對成功回傳 1, 否則回傳, 亦即與 I, ID, IE, IF, IA, IDD, IDE, ID, IED, IEC, IFC, IFD, IA, IAT, IAD, 由短而長逐步比對, 這個比對過程可以畫成樹狀圖以 DFS 搜尋, 可以用遞迴函式實作 S E D I F B V A D E R Q T W Y N M P Q A B D E C S E D I F B V A D E R Q T W Y N M P Q D E F A D E D C I 45 a. int ismatched(char board[][7], int len, char target[], int x, int y) b. 這個函式檢查字元陣列 target[] 中的字串是否與以 board[x][y] 為中心的字串吻合 c. 長度短一點的問題 : 如果第一個字吻合, 即 target[]==board[x][y], 則進一步比對由 target[1] 開始的字串是否可以和由 board[x+1][y], board[x-1][y], board[x][y+1], 或是 board[x][y-1] 為中心的字串吻合, 注意需要避開折回或是交叉重疊的字串 d. 如果任一子字串比對成功, 則表示完整的字串是吻合的, 回傳 1 e. 長度為 1 且 board[x][y] == target[] 時表示吻合, 回傳 1 int ismatched(char board[][7], int len, char target[], int x, int y) { if (board[x][y] == target[]) { board[x][y] = -board[x][y]; if (len == 1) urn 1; { if (ismatched(board, len-1, &target[1], x+1, y)) urn 1; if (ismatched(board, ( len-1, &target[1], x, y-1)) urn 1; if (ismatched(board, len-1, &target[1], x-1, y)) urn 1; if (ismatched(board, len-1, &target[1], x, y+1)) urn 1; urn ; 46 Hamiltonian Path 把右邊這樣的棋盤中每一格看成是一個圖形的節點, 每一個節點和上下左右相鄰的四個節點連接在一起, 請由 (,) 這一個節點開始, 判斷是否存在一個路徑可以經過所有的節點恰好一次 ( 一筆畫過所有的節點 ), 這種路徑稱為 Hamiltonian Path 尋找 Hamiltonian Path 的問題是 NP-Hard 我們可以寫類似搜尋迷宮路徑的暴力演算法, 程式效率會不好, 但是對於參數比較小的問題來說, 是可以找到答案的 start (,) (1,1) (,) (,1) (,) int explore(int nsize, int ivisitstates[][15], int current, int currenty, int serialno, long *lsolcount, long *ltrialcount) { int offset[4][] = {-1,,,-1, 1,,,1; int i, next, nexty, loldcount = *lsolcount; *ltrialcount += 1; // node counts (including all internal and leave nodes) if (serialno == nsize*nsize-) { *lsolcount += 1; urn 1; ivisitstates[current][currenty] = serialno; for (i=; i<4; i++) { next = current + offset[i][]; nexty = currenty + offset[i][1]; if (ivisitstates[next][nexty] < ) explore(nsize,ivisitstates, next,nexty, serialno+1, lsolcount, ltrialcount); (,1) (1,) (1,) (1,1) (,) (1,) (,) 47 ivisitstates[current][currenty] ] = -1; urn (*lsolcount>loldcount? 1 : );

13 8 Queen Problem 把 8 個皇后放在 8 8 的西洋棋棋盤上使得用基本的西洋棋規則, 任意兩個皇后無法吃掉對方, 也就是兩個皇后不能在同一列 同一行 或是在對角線方向的直線上 暴力解 : DFS ( 深度優先搜尋 ), 需要使用堆疊來記錄路徑搜尋過程中的下一個選擇 一個完全不考慮限制的暴力搜尋法需要考慮 8*8 種可能的解 ; 如果考慮行與列的限制, 則有 8! 種可能的解 ; 如果再考慮對角線方向的限制, 可能解的數目又降低了 如果考慮旋轉與鏡射的重複性,8 后問題的 9 個解其實只剩下 1 個不同的解 由於是一個像是迷宮或是 Hamilton Path 這樣的深度優先搜尋, 我們可以撰寫遞迴函式來搜尋可能的解答 n-queen 快速的經驗法則解法請參考 wiki 49 a. int placequeensforremainingrows(int size, int cols[], int irow) b. 這個函式將第 irow 個到第 size-1 個皇后在不違反 cols[] cols[irow-1] l[ir 的限制之下排好, 結果放在 cols[irow] l[ir cols[size-1] 中, 如果能夠完成就回傳 1, 否則回傳值為 c. 拆解為兩個小一點的問題 : 排第 irow 個皇后, 在第 irow 列上, 測試第, 1,, size-1 行是否和先前放在 (, cols[]) (irow-1,cols[irow-1]) 上的皇后有衝突, 如果沒有的話, 再運用這個遞迴函式排好第 irow+1 到 size-1 個皇后 ; 如果前者在所有可能性中找不到答案, 回傳 ; 如果後者找不到答案, 繼續 中第, 1,, size-1 行未進行的測試 (backtracking) d. 子問題的答案和原本的部份答案合併在一起就是答案了 e. irow 等於 size 時,cols[]cols[size-1] cols[size 已經完全排好, 列印 int placequeensforremainingrows(int size, int cols[], int irow) { if (irow == size) { printboard(size, cols); urn 1; for (int icol=; icol<size; icol++) if (issafewithprevious(size, cols, irow, icol)) { cols[irow] = icol; if (placeremainingrows(size, cols, irow+1)) urn 1; urn ; 5 合併排序法 (Merge Sort) 以一個範例來說明基本的演算法 將資料分割成兩半 各自排序 合併兩數列 運算複雜度 : O(n log n), 比 quicksort 的平均 O(n log n) 好 需要額外的 O(n) 記憶體, 比 quicksort 多 51 void mergesort(int data[], int len) { int len1=len/, len=len-len1; if (len <= 1) urn; mergesort(data, len1); mergesort(&data[len1], len); merge(data, len1, &data[len1], len); void merge(int data1[], int len1, int data[], int len) { int data1_idx idx=, data_idx idx=, result_idx idx=; int *buf = (int *) malloc((len1+len) * sizeof(int)); while (data1_idx < len1 data_idx < len) { if (data1_idx < len1 && data_idx < len) buf[result_idx++] = (data1[data1_idx]<=data[data_idx])? data1[data1_idx++] : data[data_idx++]; if (data1_idx < len1) buf[result_idx++] = data1[data1_idx++]; buf[result_idx++] = data[data_idx++]; for (result_idx = ; result_idx < len1+len; result_idx++) data1[result_idx] = buf[result_idx]; free(buf); f) 5

14 Determinant of an n-by-n Matrix Laplace s formula a 1,1 a 1, a 1, A = Recursion a,1 a, a, a 1,1 a, a, det(a) = (-1) 1+1 a + (-1) ,1M 11 1,1 a 1 1,M 1 1, + (-1) 1+ a 1 1,M 1 1, minor a 1,1 a 1, a 1, M 1, = det ( a,1 a, a, Termination a 1,1 a, a, ) i.e. det(a) = a 1,1 a, a,1 a 1, for a -by- matrix A a,1 a, a,1 a, 迴圈 迴圈 遞迴函式 struct t Local localvar; lv // contains persistent t variables for <loop-body> for (loopvar=1; loopvar<1; loopvar++) <loop-body> 遞迴函式 void recfun() { int loopvar = 1; struct Local localvar; rechelperfunc(loopvar, localvar); // 完成 <loop-body>, loopvar, loopvar+1,, 1 void rechelperfunc(int loopvar, struct Local &localvar) { if (loopvar<1) ){ <loop-body> loopvar++; rechelperfunc(loopvar, localvar); tail-recursive 54 範例 迴圈 for (i=; i<n; i++) printf("%d\n", i); 遞迴函式 void recprint() { int i=; recprinthelper(n, i); // prints i,i+1,,n-1 void recprinthelper(int n, int i) { if (i<n) { printf("%d\n", i); i++; recprinthelper(n,i); C++ default parameter void recprint(int n, int i=) { if (i<n) { printf("%d\n", i); i++; recprint(n,i); for (i=sum=; i<n; i++) sum+=i; printf("%d\n", i); int recsum(int n, int i=) { if (i==n) urn ; urn i+recsum(n,i+1); void recprint(int n) { // prints 1,,n-1 if (n==) printf(""); recprint(n-1); printf("%d\n", n-1); --- or more commonly int recsum(int n) { if (i==) urn ; urn n+recsum(n-1); 55 範例 (cont d) 迴圈矩陣乘法 for (i=; i<m; i++) for (j=; j<p; j++) for (k=,c[i][j]=; k<n; k++) // n==o c[i][j] += a[i][k]*b[k][j]; 這個範例其實並不是告訴你矩陣的乘法需要用遞迴才能寫, 事實上迴圈的寫法就是非常簡潔的了, 效率其實也沒有比最佳的演算法差多少, 這個範例是希望讓你體會迴圈和遞迴寫法的關聯性 遞迴函式 - 每次呼叫完成一次乘法及加法每次呼叫完成一個元素 c 矩陣的一整列 c[i][j] c[irow] void multiplymatrix(int m, int n, int a[][ma], int o, int p, int b[][ma], int c[][ma], ], // 需要初始為 int idx) irow) { { // // 也可以傳 idx: irow: m*p-1 i, m-1 j, k, 但需要適當遞增機制 int if (irow<m) i=idx/p, i=idx/(n*p), j=idx%p, { j=idx/n%p, k; k=idx%n; // idx: m*n*p-1 if (idx<m*p) (idx<m*n*p) for (int j=; { j<p; { j++) for c[i][j] for (k=, (int += c[i][j]=; a[i][k]*b[k][j]; k=, c[irow][j]=; k<n; k++) k<n; k++) multiplymatrix(m, c[i][j] c[irow][j] += a[i][k]*b[k][j]; += n, a[irow][k]*b[k][j]; a, o, p, b, c, idx+1); multiplymatrix(m, n, a, o, p, b, c, idx+1); irow+1); 56

15 尾端遞迴函式 1. 尾端遞迴函式 (Tail Recursive Function, Tail Recursion) 也是一種遞迴函式, 額外的特性是每次呼叫自己之後, 必須立刻回傳結果, 不能做任何其它事例如 : 計算 f(n) = n 的遞迴函式 一 int sum(int n) { // 計算 f(n)=+1+++n if (n==) sum(5) sum(4) 般 sum() sum() sum(1) sum() 遞 urn ; sum(n) 5 4 迴 1 函 urn sum(n-1)+n; 式 urn value 15 + C++ 預設參數 尾 int sum(int n, int psum=) { // 計算 f(n)=+1+++n+psum if (n==) sum(5,) sum(4,5) 端 sum(,9) urn psum; sum(,1) 遞 sum(n,psum)5, 迴 4,5 +,9 sum(n-1, +,1 函 urn n+psum); ,14 式 +,15 urn + value 計算 f(n)=1+++(n-1)+(n+psum) sum(1,14) sum(,15) 57 尾端遞迴函式 (/4). 尾端遞迴函式比一般的遞迴函式難寫難讀, 為什麼要寫這種尾端遞迴函式呢? 因為 C++ 編譯器可以對這種函式最佳化, 使得它就算呼叫自己非常多次, 不會使用額外的堆疊空間 ( 因為尾端遞迴函式在下一層函式回傳後並不需要使用上一層函式裡面的任何參數 暫存器 或是變數的數值, 所以概念上堆疊上的堆疊框可以直接在呼叫下一層函式時使用, 上一層函式的 urn address, 直接作為下一層函式的 address, 只需更換呼叫的引數值即可 ) Local Variables Register save Ret address Arguments Current Stack Frame 58. 計算 f(n)=1++n 的尾端遞迴函式的第二種設計方法 : a. 分解問題 : f(n)=sumtr(n,psum=,i=1)=()+1+++n= sumtr(n-1,psum+i,i+1)=(+1)+++n= 加總 psum 及 1n 後 n 個數字 sumtr(,psum+n,n+1)=(+1++n) n+1)=(+1+ +n) 注意 一定有一個參數 psum 是部份答案, 這個部份答案一層一層越來越接近想要計算的 f(n), 開始的呼叫是 sumtr(n,psum=f(),1) 下層函式 sumtr(n',f(n-n'),n-n'+1) 需要計算出原來的 f(n), 而不是子問題的答案, 如此才能夠在每一層回傳最後結果, 在呼叫 sumtr(, f(n),n+1) 時基本上沒有計算的動作, 第二個參數就是最後的答案 f(n) b. 根據分解的問題定義出遞迴函式以及其參數 int sumtr(int n, int psum=, int i) sumtr() sumtr() sumtr() sumtr()sumtr() int sumtr(int n, int psum, int i) { 5,,1 psumi) if (n==) sumtr(n,psum,i) 4,1, +,, sumtr(),6,4 + urn psum; + 1,1,5,15,6 + urn urn sumtr(n-1, psum+i, i+1); value 計算 Fibonacci f(n)=f(n-1)+f(n-) 的尾端遞迴函式的設計方法 : a. 分解問題 : f(n)=fibo(n,f1=f(),f=f(-1)) f(n-1)=fibo(n-1,f1=f(1)=f()+f(-1),f=f()) fib ( 1 f1 f(1) f() f f()) f(1)=fibo(1,f1=f(n-1),f=f(n-)) ( ( ), ( )) f()=fibo(,f1=f(n)=f(n-1)+f(n-),f=f(n-1)) 注意 一定有一個參數 f1 是部份答案, 這個部份答案一層一層越來越接近想要計算的 f(n), 開始的呼叫是 fibo(n,f1=f()=1,f=f(-1)=1) 下層函式 fibo(n',f(n-n'),f(n-n'-1)) ( ( )) 需要計算出原來的 f(n), 而不是子問題的答案, 如此才能夠在每一層回傳最後結果, 在呼叫 fibo(, f(n),f(n-1)) 時基本上沒有計算的動作, 第二個參數就是答案 f(n) b. 根據分解的問題定義出遞迴函式以及其參數 int fibo(int n, int f1=1, int f=1) int fibo(int n, int f1, int f) { if (n==) urn f1; urn fibo(n-1, f1+f, f1); fibo() fibo() fibo() 5,1,1 fibo() fibo(n,f1,f) 4,,1 fibo() +,, fibo() +,5, + 1,8,5,1, urn value 1 6

16 全域 / 靜態變數 int sum(int data[], int n) { static int result = ; if (n>) { result += data[n-1]; sum(data, n-1); urn result; Side effect int recsum(int n, int i=) { if (i==n) urn ; urn i+recsum(n,i++); 遞迴專屬的錯誤 61 系統堆疊大小控制 platform default size ===================== SunOS/Solaris 817K bytes (Shared Version) Linux 817K bytes Windows 14K bytes (Release Version) cygwin 48K bytes Linux ulimit -a # shows the current stack size ulimit -s 768 # sets the stack size to M bytes OS LD_FLAGS= -Wl,-stack_size,x1 size Windows Visual Studio Run "dumpbin /headers executable_file", and you can see the "size of stack reserve" information in "optional header values" Run "editbin /STACK:size" to change the default stack size. Visual Studio: Properties -> Configuration Properties -> Linker -> System -> Stack Reserve Size #pragma comment(linker, "/STACK:677716") g++ -Wl,--stack=56 test.cpp o test.exe 6