1、課前思考題課前思考題你認為以下三個公式有區別嗎？你認為以下三個公式有區別嗎？整理課件2第九章遞歸思想與相應算法32003200整理課件相傳，在古代印度名為Bramah的廟中，僧人們整天把三根柱子上的金盤倒來倒去，原來他們想把64個一個比一個小的金盤從一根柱子上移到另一根柱子上去。在盤子的移動過程中，要求恪守下述規則：每次只允許移動一只盤，且大盤不得摞在小盤上面。請你幫助他們制定移盤的步驟！3印度神廟僧侶的金盤任務整理課件有人可能會覺得這個問題很簡單，而實際上，如果真的動手進行數學推算就會發現：即便一秒鐘移動一只盤子，按照上述規則，要將64只盤子從一個柱子移至另一個柱子上，需要大約5800億年！

2、這個僧侶移盤問題，通常被稱為漢諾(Hanoi)塔問題。解決這個問題最經典的算法就是遞歸。4任務 整理課件遞歸算法在可計算性理論中占有重要地位，它是算法設計的有力工具，對于拓展編程思路非常有用。遞歸算法不涉及高深數學知識，不過初學者要建立起遞歸概念并不十分容易。 遞歸及其實現遞歸及其實現5整理課件為了幫助我們思考和表述遞歸算法的思路，使算法更為了幫助我們思考和表述遞歸算法的思路，使算法更直觀和清晰，我們定義兩個結點：直觀和清晰，我們定義兩個結點：或結點或結點和和與結點。與結點。1、或結點、或結點,BZ trueCZfalseA（真）（假） A 條條件件 Z 條條件件!Z B C A為為“或結點或

3、結點”，A依不同條件會有兩種不同的取值依不同條件會有兩種不同的取值, B 或或C。結點用。結點用 表示。表示。 6輔助遞歸算法設計的工具整理課件如果有多于如果有多于 2 種取值，可用下圖：種取值，可用下圖： Z1 Z2 Zn B C G A 條件為條件為 Z1 , Z2 , ,Zn ,Z1 , Z2 , ,Zn , A A 取值為取值為 B B 或或 C, C, 或或 G G7整理課件2、與結點、與結點與結點與結點要涂黑，相關要涂黑，相關聯的聯的 B 與與 C 之間要用之間要用弧線連起來。弧線連起來。A 為為與結點與結點，A 的最終取值為的最終取值為 C 結點的值，結點的值，但為了求得但為了求

4、得 C 的值，得先求出的值，得先求出 B 結點的值結點的值, C 是是B 的函數。的函數。ABC8整理課件與結點與結點可能有多個相關聯的點，這時可描述為下圖可能有多個相關聯的點，這時可描述為下圖A 結點的值最終為結點的值最終為 D 的值，但為了求的值，但為了求 D 需先求需先求 B 和和 C。先求左邊的點才能求最右邊的點的值先求左邊的點才能求最右邊的點的值，約，約定最右邊定最右邊 D 點的值就是點的值就是 A 結點的值。結點的值。ABDC9整理課件例：試編寫一個函數fact(n)，求解階乘 n !10下面分別使用“枚舉”、“遞推”、“遞歸”等三種不同的算法思想來實現該函數，請注意對比不同方法的

5、代碼內容。什么樣的程序是遞歸程序？整理課件設fact(n)是一個求 n !的函數11/ 使用枚舉思想，求解正整數的階乘#include using namespace std;int fact(int n) int m = 1; for (int i=1; i=n; i+) m = m * i; return m;int main() cout fact(3) = fact(3) endl; return 0; 整理課件設fact(n)是一個求 n !的函數12/ 使用遞推思想，求解正整數的階乘#include using namespace std;int fact(int n) int m

6、10; / / / / 假設假設求求10以內整數的階乘以內整數的階乘 m1 = 1; / / 遞推的起始值遞推的起始值 for (int i=2; i=n; i+) mi = mi-1 * i; return mn;/ / 返回遞推的終值返回遞推的終值int main() cout fact(3) = fact(3) endl; return 0; 整理課件設fact(n)是一個求 n !的函數13/ 使用遞歸算法，求解正整數的階乘#include using namespace std;int fact(int n) if (n = 1)/ / 遞歸的終止條件遞歸的終止條件 return 1

7、;/ / 直接返回結果直接返回結果 return n * fact(n-1); / n * (n-1)! / / 自己調用自己：遞歸自己調用自己：遞歸int main() cout fact(3) = fact(3) 1Bfact(2)3*fact(2)fact(3)Cfact(1)D2*fact(1)AE2116整理課件對于對于fact(n)的遞歸實現，它的的遞歸實現，它的與或圖與或圖如下：如下：A 為為或結點或結點；B 為直接可解結點，值為為直接可解結點，值為1；C 為為與結點與結點，當當 n1 時，時，A 的取值即的取值即 C 的值，而的值，而 C 的值即的值即 E 的值，的值，為了求得

8、為了求得 E 的值，需要先求出的值，需要先求出 D 的值。的值。D 值值 fact( n-1 ) 乘以乘以 n 即為即為 E 的值。的值。A fact(n)Bfact(1)=1Cn1n=1Dfact(n-1)En*fact(n-1)17整理課件遞歸算法的出發點不是在初始條件上，而是在求解目標上，即從所求的未知項出發，逐次調用本身直到遞歸邊界（即初始條件）的求解過程。就本例而言，大家或許會認為使用遞歸算法沒有必要，費力不討好。但有許多實際問題往往不可能或很難找到顯而易見的遞推關系，這時，遞歸算法就表現出明顯的優越性。我們將通過不同類型的示例問題來說明：遞歸算法比較符合人的思維方式，邏輯性強，可將

9、問題描述得簡單扼要，可讀性強，易于理解。許多看來相當復雜或難以下手的問題，如果能夠使用遞歸算法，就會變得易于處理。18整理課件19整理課件9.2 9.2 遞遞 歸歸 算算 法法 舉舉 例例 方陣填充方陣填充20整理課件21整理課件22整理課件Fill( number,begin,size)23整理課件24整理課件25整理課件26整理課件27整理課件28整理課件29整理課件30整理課件31整理課件32整理課件33整理課件34整理課件35整理課件SIZE SIZE 是奇數時是奇數時36整理課件源代碼略37整理課件9.2 9.2 遞遞 歸歸 算算 法法 舉舉 例例 組合數計算組合數計算38整理課件我

10、們畫出我們畫出與或圖與或圖來闡述求解思路：來闡述求解思路：39整理課件源代碼40#include using namespace std;int C(int m, int n) if (m0 | n0 | mn) return 0; if (m = n) return 1; if (n = 1) return m; return C(m-1, n)+C(m-1, n-1);int main() cout C(6,2) = C(6, 2) endl; return 0;整理課件整理課件9.2 9.2 遞遞 歸歸 算算 法法 舉舉 例例 快速排序快速排序42整理課件“與或圖與或圖”對應的快速排序思

11、路對應的快速排序思路：1、將待排序的數據放入數組、將待排序的數據放入數組 a 中，下標從中，下標從 z 到到 y ；2、令、令sort( z ,y )為將數組元素從下標為為將數組元素從下標為 z 到下標為到下標為 y 的的 y z + 1 個元素從小到大排序。個元素從小到大排序。3、取、取 a z 放變量放變量 k 中，通過分區處理，為中，通過分區處理，為 k 選擇應選擇應該排定的該排定的位置位置 將比將比 k 大的數放右邊，比大的數放右邊，比 k 小小的數放左邊的數放左邊。當。當 k 到達最終位置后，由到達最終位置后，由 k 劃分左劃分左右兩個集合。然后再右兩個集合。然后再用同樣的思路處理用

12、同樣的思路處理左集合與左集合與右集合右集合。43整理課件44整理課件我們畫出與或圖來闡述快速排序的思路：我們畫出與或圖來闡述快速排序的思路：函數函數sortsort有兩個參數（有兩個參數（z z和和y y），分別表示數組中一個片段的），分別表示數組中一個片段的起始與終止下標值。起始與終止下標值。STEP 1. STEP 1. 比比arrayzarrayz小的元素交換到數組左邊，大的元素交換到數組右邊小的元素交換到數組左邊，大的元素交換到數組右邊STEP 2. STEP 2. 將將arrayzarrayz元素放到新位置上，下標是元素放到新位置上，下標是 m m45整理課件分區處理：分區處理： k

13、1、讓、讓 k=a z a 2、將、將 k 放在放在 a m z m y3、使、使 az, az+1 , , a m-1 = a m 4、使、使 a m = y，則什么也不做。這是直接可，則什么也不做。這是直接可解結點。解結點。C 結點是在結點是在 z y 情況下情況下 A 結點的解。結點的解。C 是一個是一個與結與結點點。要對。要對 C 求解需分解為三步。依次為：求解需分解為三步。依次為：46整理課件1、先解、先解 D 結點，結點，D 結點是一個直接可解結點，功能是結點是一個直接可解結點，功能是進行所謂的分區處理，規定這一步要做的事情是進行所謂的分區處理，規定這一步要做的事情是（1）將）將

14、a z 中的元素放到它應該在的位置上，比如中的元素放到它應該在的位置上，比如 m 位置。這時位置。這時 a m a z ；（2）讓下標從）讓下標從 z 到到 m-1 的數組元素小于等的數組元素小于等于于a m ；（3）讓下標從）讓下標從 m+1 到到 y 的數組元素大于的數組元素大于a m ； 比如比如: a 數組中數組中 a z = 5，經分組處理后，經分組處理后，5 送至送至 a 4 。5 到位后，其左邊到位后，其左邊 a 0 a 3 的值都小于的值都小于 5；其右邊其右邊 a 5 , a 6 都都大于大于 5。47整理課件2、再解、再解 E 結點，這時要處理的是結點，這時要處理的是 a

15、0 a 3 ；3、再解、再解 F 結點，處理結點，處理a 5 , a 6 。下面按照這種思路構思一個快速排序的程序框圖下面按照這種思路構思一個快速排序的程序框圖。48整理課件 ll r r l= ll; r = r r ; k = a r r a y l; T F d o w h ile (l = k ) (1 ) r = r-1 ; l r (2 ) T F a r r a y l= a r r a y r ; l= l+ 1 w h ile (l r )& & (a r r a y l = k ) (3 ) l= l+ 1 ; l r ; (4 ) T F a r r a

16、y r = a r r a y l; w h ile (l!= r ); a r r a y l= k ; fo r (i= ll; i45253515750動畫演示動畫演示整理課件下面舉例說明排序過程下面舉例說明排序過程圖圖1 a數組中有數組中有7個元素待排序個元素待排序1 讓讓 k = a z = a 0 = 5zy圖圖 1k51整理課件2 進入直到型循環進入直到型循環 執行（執行（1）ay=a6=4 不滿足當循環條件，不滿足當循環條件，y不動。不動。 執行（執行（2）zy，做兩件事：，做兩件事： a z = a y ，即，即a 0 = a 6 = 4， z = z +1 = 0+1 =

17、1，見，見圖圖2zy 圖圖 2k52整理課件 執行（執行（3）圖）圖2中的中的a1 5zy圖圖 3k53整理課件 執行（執行（4）ay=az，即，即a6=a2=6，見，見圖圖4。這時。這時 z != y 還得執行直到型循環的循環體。還得執行直到型循環的循環體。zy圖圖 4k54整理課件 執行（執行（1）ay=a6=6，6k滿足當循環的條件，滿足當循環的條件，y = y-1 = 6-1 = 5見見圖圖5，之后退出當循環，因為，之后退出當循環，因為 a y = 3k (k=5)zy圖圖 5k55整理課件 執行（執行（2）a z =a y ，并讓，并讓 z = z+1=3，見，見圖圖6 zy圖圖 6

18、k56整理課件 執行（執行（3）由于）由于a3=1k，退出循環。見，退出循環。見圖圖7 zy圖圖 7k57整理課件 執行（執行（4）az=ay，a5=7。見。見圖圖8 這時仍然這時仍然 zk，讓，讓 y = y-1 = 4。見。見圖圖9zy圖圖 9k59整理課件 之后，之后，z = y，退出直到型循環，做，退出直到型循環，做 a z = k，z = 4， a 4 = 5，這是，這是 5 的最終位置，的最終位置，5 將整個數據分成左右將整個數據分成左右兩個集合，見兩個集合，見圖圖10。zy圖圖 10左左右右k60整理課件用上述思路去排左邊的部分用上述思路去排左邊的部分從從 z = 0 到到 y

19、= 3，見，見圖圖11。讓。讓 k = a z = a 0 = 4，然后，然后進到直到型循環，進到直到型循環， 執行（執行（1）a y = 1k，不滿足當循環的條件，不滿足當循環的條件，y不動。不動。 執行（執行（2）a z = a y ，z = z+1 = 1, 見見圖圖12zy圖圖 12zy圖圖 11k61整理課件 執行（執行（3）a z k，z=z+1=2，a2k，z=z+1=3，這時，這時z=y，不會執行（，不會執行（4），同時退出直到型循環，見），同時退出直到型循環，見圖圖13。然后做然后做 a z =k，即，即a 3 =4，見圖，見圖14，左邊也排好了。，左邊也排好了。圖圖 14z

20、y圖圖 13zykk62整理課件4、用上述思路去排右邊的部分，見、用上述思路去排右邊的部分，見圖圖15，讓，讓k = a z = a 5 = 7，進入直到型循環；，進入直到型循環； 執行（執行（1）a y = 6k，y不動不動 執行（執行（2）a z = a y =6，z = z+1=5+1=6，見，見圖圖16圖圖 16zy圖圖 15zyk63整理課件這時這時 z = y，不再執行（，不再執行（3）（）（4），退出直到型循環后，），退出直到型循環后，做做 a z = k，見圖，見圖17。圖圖 17zyk64整理課件在有了遞歸調用函數之后，主程序很容易寫，主程在有了遞歸調用函數之后，主程序很容易

21、寫，主程序中應包含序中應包含1、 定義整型變量：數組定義整型變量：數組 a10 ，i ；2、 用循環結構輸入待排序的數，將其放入用循環結構輸入待排序的數，將其放入 a 數組；數組；3、 調用調用 sort 函數，使用三個實際參數函數，使用三個實際參數a將數組將數組 a 當實參；當實參；0數組下標下界；數組下標下界；9數組下標上界；數組下標上界；4、 輸出排序結果輸出排序結果下面給出參考程序（分兩頁）下面給出參考程序（分兩頁）65整理課件/ */ * 程程 序：序：6_6.cpp */ * 作作 者：者：wuwh */ * 編制時間：編制時間：2002年年10月月28日日 */ * 主要功能：快

22、速排序主要功能：快速排序 */ *#include / coutusing namespace std;void sort(int array , int zz, int yy) /被調用函數，數組被調用函數，數組array,zz,yy為形參為形參int z,y,i,k; /定義變量定義變量 if ( zzyy ) /如果如果 zz yy ,則做下列則做下列 7 件事件事: / 7 件事開始件事開始z = zz; y = yy; k = array z ; /第第1件事件事do /第第2件事件事(開始開始) while( z=k) y-; /2.1,右邊的元素右邊的元素=k,讓讓 y 往中間移

23、往中間移 if( z y ) /2.2,右邊的元素右邊的元素k,讓讓 array z = array y ; /array y 送給送給 array z ， z = z+1; /同時讓同時讓 z 往中間移往中間移 while( z y) & (arrayz = k) z+; /2.3,左邊的元素左邊的元素=k,讓讓 z 往中間移往中間移 if ( z k, 讓讓 array z array y = array z ; /送給送給array y while( z != y ) ; /第第2件事件事(結束結束)66整理課件array z = k; /第第3件事件事,k已排到位已排到位for

24、(i = zz ;i = yy ;i+) /第第4件事，輸出件事，輸出 coutai=arrayi; ;cout endl; /第第5件事，換行件事，換行sort( array, zz ,z-1 ); /第第6件事，排左邊部分件事，排左邊部分sort( array ,z+1, yy); /第第7件事，排右邊部分件事，排右邊部分 /7件事結束件事結束 /函數體結束函數體結束int main() /主函數開始主函數開始int a10,i; /整型變量整型變量cout 請輸入請輸入10個整數個整數n; /提示信息提示信息for (i = 0; i a i ;sort(a,0,9);/調用調用sort

25、函數函數,實參為數組實參為數組a和和0，9cout 排序結果為排序結果為:; /提示信息提示信息for (i =0; i10 ;i+ ) cout a i ;/輸出排序結果輸出排序結果cout endl; return 0;/主函數結束主函數結束 67整理課件/ */ * 程程 序：序：6_6.cpp * / * 作作 者：者：wuwh * / * 編制時間：編制時間：2002年年10月月28日日 * / * 主要功能：快速排序主要功能：快速排序 * / *68整理課件#include /cout using namespace;void sort(int array , int zz, in

26、t yy)/被調用函數，數組被調用函數，數組array,zz,yy為形參為形參 /函數體開始函數體開始 int z,y,i,k; /定義變量定義變量 if ( zzyy ) /如果如果 zz yy ,則做下列則做下列 7 件事件事:69整理課件 / 7 件事開始件事開始 z = zz; y = yy; k = array z ; /第第1件事件事70整理課件do /第第2件事件事(開始開始) while( z=k) y-; /2.1,右邊的元素右邊的元素=k,讓讓 y 往中間移往中間移 if( z y ) /2.2,右邊的元素右邊的元素k,讓讓 /array y 送給送給 array z ， /同時讓同時讓 z 往中間移往中間移 array z = ar