《算法語言與數據結構學習教案》由會員分享，可在線閱讀，更多相關《算法語言與數據結構學習教案（174頁珍藏版）》請在裝配圖網上搜索。

1、會計學1算法語言算法語言(sun f y yn)與數據結構與數據結構第一頁，共174頁。 第2頁/共174頁第二頁，共174頁。/ */ * 程 序：6_3.cpp（驗證素數程序） */ * 作 者：wuwh */ * 編制時間：2002年10月20日 */ * 主要功能：可驗證某數是否為素數 */ *#include / 預編譯命令#include / 預編譯命令int checkprime( int );/ 子函數聲明int main()/ 主函數int a=0;/ 定義整型變量，初始化為0cout a;/ 鍵盤輸入一個整數/ 用實參a調用子函數，該子函數的/ 返回值作為if語句(yj)的

2、分支條件if ( checkprime(a) ) / checkprime(a)為1cout a 是素數 endl;else/ checkprime(a)為0cout a 不是素數 endl;/ 主函數結束第3頁/共174頁第三頁，共174頁。n/ 用實參 a 調用子函數，該子函數的n/ 返回值作為 if 語句的分支(fnzh)條件nif ( checkprime( a ) ) n/ checkprime( a ) 為 1ncout a 是素數 endl;nnelsen / checkprime( a ) 為 0n cout a 不是素數 endl;nn/ 主函數結束第第5章章 函數函數(hn

3、sh)第4頁/共174頁第四頁，共174頁。第第5章章 函數函數(hnsh)第5頁/共174頁第五頁，共174頁。bool checkprime(int b)/ 子函數，子函數，b為形式參數為形式參數int k=0; / 定義整型變量，并初始化定義整型變量，并初始化for (k=2; k=sqrt(double)b); k+)/ 循環(huán)循環(huán)if (b%k = 0)/ 如果如果b能夠能夠(nnggu)被被k整除，整除，則返回則返回0/ 可理解為可理解為“搶先搶先”返回返回0，有了，有了 return 0，/ 后面的后面的 return 1 不起作用了不起作用了return 0;return 1;/

4、 b不能被不能被k整除，則返回整除，則返回1第第5章章 函數函數(hnsh)第6頁/共174頁第六頁，共174頁。bool checkprime(int b) int k=0;for (k=2; k=sqrt(double)b); k+)if (b%k = 0) return 0;return 1;第第5章章 函數函數(hnsh)第7頁/共174頁第七頁，共174頁。bool checkprime( int b ) / 子函數子函數 int k=0; 形式參數形式參數for ( k=2; k=sqrt( (double) b ); k=K+1 ) if ( b % k = 0 ) return

5、 0; return 1; / b不能被不能被k整除，則返回整除，則返回1 / 說明說明(shumng) b 是質數是質數第第5章章 函數函數(hnsh)第8頁/共174頁第八頁，共174頁。 講這一程序的目的：講這一程序的目的：如何定義一個如何定義一個(y )函數函數主函數怎樣調用子函數主函數怎樣調用子函數實在參數和形式參數實在參數和形式參數返回值是什么意思返回值是什么意思第9頁/共174頁第九頁，共174頁。第第5章章 函數函數(hnsh)第10頁/共174頁第十頁，共174頁。第第5章章 函數函數(hnsh)第11頁/共174頁第十一頁，共174頁。第12頁/共174頁第十二頁，共174

6、頁。第13頁/共174頁第十三頁，共174頁。 4.于局部變量。第14頁/共174頁第十四頁，共174頁。第15頁/共174頁第十五頁，共174頁。第16頁/共174頁第十六頁，共174頁。輸出輸出 return 0 return 1 a是質數 a不是質數返回第17頁/共174頁第十七頁，共174頁。int main()int a=0;cout a;if ( checkprime(a) ) bool checkprime(int b) int k=0; for (k=2; k=sqrt(double)b); k+) if (b%k = 0) return 0; return 1; cout a

7、 是素數(s sh) endl; elsecout a 不是素數(s sh) endl; 第18頁/共174頁第十八頁，共174頁。第19頁/共174頁第十九頁，共174頁。第20頁/共174頁第二十頁，共174頁。第21頁/共174頁第二十一頁，共174頁。 第22頁/共174頁第二十二頁，共174頁。第23頁/共174頁第二十三頁，共174頁。1nkxx4444441 2 3 4 5 6 p o w e r ( , )li li i=1,2,n l = k第24頁/共174頁第二十四頁，共174頁。4441 , 2, 61SOP( , )power( , )mim li l第25頁/共17

8、4頁第二十五頁，共174頁。第26頁/共174頁第二十六頁，共174頁。int power(int p, int q);/ 聲明函數power第27頁/共174頁第二十七頁，共174頁。第28頁/共174頁第二十八頁，共174頁。for(i=1; i=m; i+ )sum=sum+power( i, l );/ 累加return sum; / 返回值第29頁/共174頁第二十九頁，共174頁。第30頁/共174頁第三十頁，共174頁。第31頁/共174頁第三十一頁，共174頁。例例:int power(int p, int n)power 為函數名，要以英文字母開頭。為函數名，要以英文字母開頭

9、。int 是函數值的數據類型，這里是是函數值的數據類型，這里是int（整型）。（整型）。(int p, int n) 括號括號(kuho)中的中的 p, n為函數的形式參數，形為函數的形式參數，形式參數也要定義其數據類型。式參數也要定義其數據類型。第32頁/共174頁第三十二頁，共174頁。函數定義(dngy)的一般格式： ()第33頁/共174頁第三十三頁，共174頁。形式參數與實在(shzi)參數1、形式參數是在定義函數時放在函數名后括號中的參數。在未、形式參數是在定義函數時放在函數名后括號中的參數。在未進行函數調用時，并不對形式參數分配內存單元。在發(fā)生函進行函數調用時，并不對形式參數分配

10、內存單元。在發(fā)生函數調用時，立刻數調用時，立刻(lk)給形式參數分配內存單元。調用結束后，給形式參數分配內存單元。調用結束后，釋放掉行參所占的內存單元。釋放掉行參所占的內存單元。2、因此，形參變量屬于局部變量，其作用域在它所在的函數體、因此，形參變量屬于局部變量，其作用域在它所在的函數體內。內。3、在定義函數的時候，必須指定形參變量的類型，如下所示、在定義函數的時候，必須指定形參變量的類型，如下所示int power(int p, int n) / 函數函數(hnsh)體體 c第34頁/共174頁第三十四頁，共174頁。4、實在參數是一個具有確定值的表達式。函數在調用時，將實在參數賦給形式參數

11、。比如(br)，主函數調用SOP(n,k)，這時，n,k為實在參數，n的值為6，k的值為4。在被調用函數定義中，int SOP(m,l) 中的 m, l 為形式參數，在SOP被調用時，系統(tǒng)給 m, l 這兩個形式參數分配了內存單元。之后，n 的值 6 賦給 m; k 的值 4 賦給 l。第35頁/共174頁第三十五頁，共174頁。power( i, l ) 處在 SOP( m, l ) 函數中，表示SOP函數去調用 power 函數。其中(qzhng) i, l 為實在參數，而 int power( p, q )中的 p, q 為形式參數。比如，執(zhí)行 SOP( 6, 4 )時，l=4, m=6

12、,當 i=1 時，sum = sum + power( 1, 4 )這里 1，4 為實在參數，調用power( p, q )，兩個形式參數 p, q 分別被賦以 1，4 。第36頁/共174頁第三十六頁，共174頁。 執(zhí)行執(zhí)行 SOP(6,4) l=4 sum=0 i=1: sum = sum + power(i,l) = 0 + 1 = 1 i=2: sum = sum + power(i,l) = 1 + 16 = 17 i=3: sum = sum + power(i,l) = 17 + 81 = 98 i=4: sum = sum + power(i,l) = 98 + 256 = 3

13、54 i=5: sum = sum + power(i,l) = 354 + 625 = 979 i=6: sum = sum + power(i,l) = 979 + 1296 = 2275 return (sum) 2275 返回返回 執(zhí)行執(zhí)行 power(1, 4): product = 1*1*1*1 return(1) = 1 調用 返回 執(zhí)行執(zhí)行 power(2, 4): product = 2*2*2*2 return(16) = 16 調用 返回 執(zhí)行執(zhí)行 power(3, 4): product = 3*3*3*3 return(81) = 81 調用 返回 執(zhí)行執(zhí)行 pow

14、er(4, 4): product = 4*4*4*4 return(256) = 256 調用 返回 執(zhí)行執(zhí)行 power(5, 4): product = 5*5*5*5 return(625) = 625 調用 返回 執(zhí)行執(zhí)行 power(6, 4): product = 6*6*6*6 return(1296) = 1296 調用 返回 SOP(n,k) 調用調用 第37頁/共174頁第三十七頁，共174頁。遞遞 推推第38頁/共174頁第三十八頁，共174頁。第39頁/共174頁第三十九頁，共174頁。第40頁/共174頁第四十頁，共174頁。寫成一般(ybn)式fish i = (

15、 fish i - 1 1 ) * 4 / 5i = 2, 3, ,5這個公式可用于知 A 看到的魚數去推算 B 看到的，再推算 C 看到的，.?，F在要求的是 A 看到的，能否倒過來，先知 E 看到的再反推 D 看到的，直到A看到的。為此將上式改寫為：fish i-1 = fish i * 5 / 4 +1i = 5, 4,2第41頁/共174頁第四十一頁，共174頁。分析上式. 當 i = 5 時，fish 5 表示 E 醒來所看到的魚數，該數應滿足(mnz)被整除后余，即fish 5 % 5 = 1 2. 當 i = 5 時，fish i-1 表示 D 醒來所看到的魚數，這個數既要滿足(m

16、nz)fish 4 = fish 5 * 5 / 4 + 1 又要滿足(mnz)fish 4 % 5 = 1顯然，fish 4 不能不是整數，這個結論同樣可以用至 fish 3 , fish 2 和 fish 1 第42頁/共174頁第四十二頁，共174頁。3 . 按題意要求 5 人合伙捕到的最少魚數，可以從小往大枚舉，可以先讓 E 所看到的魚數最少為 6 條，即 fish 5 初始化為 6 來試，之后每次增加 5 再試，直至遞推到 fish 1 得整數且除以 5 之后的余數(ysh)為 1。根據上述思路，我們可以構思如下的程序框圖：第43頁/共174頁第四十三頁，共174頁。 定義數組 fi

17、sh6，并初始化為 1； 定義循環(huán)控制變量 i，并初始化為 0。 輸出計算結果 fish1至 fish5 do while(i=1); fish5=fish5+5; / .1 for ( i=4; i=1; i- ) / .2 fishi+1%4 != 0 true false break; /退出 for 循環(huán) fishi = fishi+1*5/4+1; 第44頁/共174頁第四十四頁，共174頁。該圖可分為三部分該圖可分為三部分(1) 是說明部分：包含定義數組是說明部分：包含定義數組 fish6，并初始化為，并初始化為 1 和定義循環(huán)和定義循環(huán)控制變量控制變量 i，并初始化為，并初始化為

18、 0。(2) 是是 do.while 直到型循環(huán)，其循環(huán)體又含兩塊：直到型循環(huán)，其循環(huán)體又含兩塊：(2).1 是枚舉是枚舉(mi j)過程中的過程中的 fish5 的初值設置，一開始的初值設置，一開始 fish5=1+5; 以后每次增以后每次增 5。(2).2 是一個是一個 for 循環(huán)，循環(huán)，i 的初值為的初值為 4，終值為，終值為 1，步長為，步長為 -1，該循環(huán)的循環(huán)體是一個分支語句，該循環(huán)的循環(huán)體是一個分支語句， 如果如果 fishi+1不能被不能被 4 整除，則跳出整除，則跳出 for 循環(huán)（使用循環(huán)（使用 break 語語句）句）; 否則，從否則，從 fishi+1 算出算出 fi

19、shi。第45頁/共174頁第四十五頁，共174頁。當由 break 語句讓程序退出循環(huán)時，意味著某人看到的魚數不是整數，當然不是所求，必須令fish 5 加 5 后再試，即重新進入直到型循環(huán) do while 的循環(huán)體。當著正常退出 for 循環(huán)時，一定是控制變量 i 從初值 4，一步一步執(zhí)行到終值 1，每一步的魚數均為整數，最后 i = 0，表示計算完畢，且也達到了退出直到型循環(huán)的條件(tiojin)。(3) 輸出計算結果第46頁/共174頁第四十六頁，共174頁。/*/* 程 序 名：5_3.c（五人合伙捕魚） */* 作 者：wuwh */* 編制時間：2002年10月2日 */* 主

20、要功能：遞推算法的實現 */*#include / 預編譯命令void main() /主函數 int fish6=1,1,1,1,1,1; / 整型數組，記錄每人醒來后看到的魚數 int i=0; do fish5=fish5+5; / 讓E看到的魚數增5。 for (i=4; i=1; i-) if ( fishi+1%4 !=0 )break; / 跳出for循環(huán)elsefishi=fishi+1*5/4+1;/ 計算第i人看到的魚數 while( i=1 ); / 當 i=1 繼續(xù)(jx)做do循環(huán) / 輸出計算結果 for (i=1; i1 時，時，A 的取值即的取值即 C 的值，而

21、的值，而 C 的的值即值即 E 的值，為了求得的值，為了求得 E 的值，需要先求出的值，需要先求出 D 的值。的值。D 值值 fact( n-1 ) 乘以乘以 n 即為即為 E 的值。的值。A fact(n)Bfact(1)=1Cn1n=1Dfact(n-1)En*fact(n-1)第55頁/共174頁第五十五頁，共174頁。與結點可能有多個與結點可能有多個(du )相關聯的點，這時可描述為相關聯的點，這時可描述為下圖下圖A 結點結點(ji din)的值最終為的值最終為 D 的值，但為了求的值，但為了求 D 需需先求先求 B 和和 C。從圖上看。從圖上看, 先求左邊的點才能求最右邊的點先求左邊

22、的點才能求最右邊的點的值，我們約定最右邊的值，我們約定最右邊 D 點的值就是點的值就是 A 結點結點(ji din)的的值。值。ABDC第56頁/共174頁第五十六頁，共174頁。下面我們以下面我們以3！為例來畫與或結點圖，目的是！為例來畫與或結點圖，目的是體會體會(thu)遞歸的含義。遞歸的含義。C = 1D = 2*C = 2B = D = 2E = 3*B = 3*2 = 6A = E = 61=1131Bfact(2)3*fact(2)fact(3)Cfact(1)D2*fact(1)AE21第57頁/共174頁第五十七頁，共174頁。下面下面(xi mian)畫出了調用和返回的遞歸示

23、意圖畫出了調用和返回的遞歸示意圖 Bfact(2)fact(2)=2*fact(1)=2*fact(1)=2*1=2*1=2=2返回返回 DAfact(3)fact(3)=3*fact(2)=3*fact(2)=3*2=3*2=6=6E E返回返回 Cfact(1)=1調用調用調用調用第58頁/共174頁第五十八頁，共174頁。從圖可以想象：從圖可以想象：欲求欲求 fact( 3 )，先要求，先要求 fact( 2 )；要求；要求 fact( 2 ) 先求先求 fact( 1 )。就象剝一顆圓白菜，從外向里，一層層剝下來，。就象剝一顆圓白菜，從外向里，一層層剝下來，到了菜心，遇到到了菜心，遇到

24、(y do) 1 的階乘，其值為的階乘，其值為1，到達了遞歸的，到達了遞歸的邊界。然后再用邊界。然后再用 fact( n )=n*fact( n-1 ) 這個普遍公式，從里這個普遍公式，從里向外倒推回去得到向外倒推回去得到 fact( n ) 的值。的值。為了把這個問題說得再透徹一點。我們畫了如下的流為了把這個問題說得再透徹一點。我們畫了如下的流程圖：程圖：第59頁/共174頁第五十九頁，共174頁。 31 fact(3) 真真 假假 調調用用 fact(2) 計計算算 3*fact(2) fact(2) fact(1) 21 真真 假假 調調用用 fact(1) 計計算算 2*fact(1)

25、 11 真真 假假 fact(1) 1 返返回回 返返回回 第60頁/共174頁第六十頁，共174頁。為了形象為了形象(xngxing)地描述遞歸過程，將上圖改畫成下圖地描述遞歸過程，將上圖改畫成下圖 fact(3) 真真 假假 3=1 調調用用 fact(2) 真真 假假 假假 真真 2=1 1=1 fact(2)=2*fact(1) 返返回回 fact(3)=3*fact(2) 返返回回 調調用用 fact(1) fact(1) =1 返返回回 第61頁/共174頁第六十一頁，共174頁。在這個圖中在這個圖中“內層內層”與與“外層外層”有著相同有著相同(xin tn)的結構。的結構。它們之

26、間它們之間“你中有我，我中有你你中有我，我中有你”，呈現相互依存的關系。，呈現相互依存的關系。為了進一步講清遞歸的概念，將遞歸與遞推做一比較。仍以為了進一步講清遞歸的概念，將遞歸與遞推做一比較。仍以求階乘為例。求階乘為例。遞推是從已知的初始條件出發(fā)，逐次去求所需要的階乘值。遞推是從已知的初始條件出發(fā)，逐次去求所需要的階乘值。如求如求 3！初始條件初始條件 fact( 1 ) = 1fact( 2 ) = 2 * fact( 1 ) = 2fact( 3 ) = 3 * fact( 2 ) = 6第62頁/共174頁第六十二頁，共174頁。這相當于從菜心這相當于從菜心“推到推到”外層。而遞歸算法

27、的出發(fā)點外層。而遞歸算法的出發(fā)點不放在初始條件上，而放在求解的目標上，從所求的未不放在初始條件上，而放在求解的目標上，從所求的未知項出發(fā)逐次調用本身的求解過程，直到遞歸的邊界知項出發(fā)逐次調用本身的求解過程，直到遞歸的邊界（即初始條件）。就本例而言，讀者會認為遞歸算法可（即初始條件）。就本例而言，讀者會認為遞歸算法可能是多余的，費力而不討好。但許多實際問題不可能或能是多余的，費力而不討好。但許多實際問題不可能或不容易找到顯而易見的遞推關系，這時遞歸算法就表現不容易找到顯而易見的遞推關系，這時遞歸算法就表現出了明顯的優(yōu)越性。下面我們將會看到，遞歸算法比較出了明顯的優(yōu)越性。下面我們將會看到，遞歸算法

28、比較符合人的思維方式，邏輯性強，可將問題描述得簡單扼符合人的思維方式，邏輯性強，可將問題描述得簡單扼要，具有良好的可讀性，易于理解，許多看來相當復雜，要，具有良好的可讀性，易于理解，許多看來相當復雜，或難以下手的問題，如果能夠使用遞歸算法就會使問題或難以下手的問題，如果能夠使用遞歸算法就會使問題變得易于處理。下面舉一個盡人皆知變得易于處理。下面舉一個盡人皆知(jn rn ji zh)的的例子哈諾（例子哈諾（Hanoi）塔問題。）塔問題。第63頁/共174頁第六十三頁，共174頁。故事：故事：相傳在古代印度的相傳在古代印度的 Bramah 廟中，有位僧人整天把廟中，有位僧人整天把三根柱子上的金盤

29、倒來倒去，原來他是想把三根柱子上的金盤倒來倒去，原來他是想把64個一個一個比一個小的金盤從一根柱子上移到另一根柱子上個比一個小的金盤從一根柱子上移到另一根柱子上去去(shng q)。移動過程中恪守下述規(guī)則：每次只。移動過程中恪守下述規(guī)則：每次只允許移動一只盤，且大盤不得落在小盤上面。有人允許移動一只盤，且大盤不得落在小盤上面。有人會覺得這很簡單，真的動手移盤就會發(fā)現，如以每會覺得這很簡單，真的動手移盤就會發(fā)現，如以每秒移動一只盤子的話，按照上述規(guī)則將秒移動一只盤子的話，按照上述規(guī)則將64只盤子從只盤子從一個柱子移至另一個柱子上，所需時間約為一個柱子移至另一個柱子上，所需時間約為5800億億年。

30、年。 第64頁/共174頁第六十四頁，共174頁。怎樣編寫這種程序？思路上還是怎樣編寫這種程序？思路上還是(hi shi)先從最簡單的情況先從最簡單的情況分析起，搬一搬看，慢慢理出思路。分析起，搬一搬看，慢慢理出思路。1、在、在A柱上只有一只盤子，假定柱上只有一只盤子，假定(jidng)盤號為盤號為1，這，這時只需將該盤從時只需將該盤從A搬至搬至C，一次完成，記為，一次完成，記為move 1 from A to C (演示演示)ABC1第65頁/共174頁第六十五頁，共174頁。2、在、在A柱上有二只盤子，柱上有二只盤子，1為小盤，為小盤，2為大盤為大盤(d pn)。第（第（1）步將）步將1號

31、盤從號盤從A移至移至B，這是為了讓，這是為了讓2號盤能移動；號盤能移動；第（第（2）步將）步將2號盤從號盤從A移至移至C；第（第（3）步再將）步再將1號盤從號盤從B移至移至C；這三步記為（演示）：這三步記為（演示）：ABC21move 1 from A to B;move 2 from A to C;move 3 form B to C;第66頁/共174頁第六十六頁，共174頁。3、在、在A柱上有柱上有3只盤子，從小到大分別為只盤子，從小到大分別為1號，號，2號，號，3號號第（第（1）步）步 將將1號盤和號盤和2號盤視為一個整體；先將二者作為號盤視為一個整體；先將二者作為整體從整體從A移至移

32、至B，給，給3號盤創(chuàng)造能夠一次移至號盤創(chuàng)造能夠一次移至C的機會。的機會。這一步記為這一步記為 move( 2, A, C, B) 意思是將上面的意思是將上面的2只盤子作為整體從只盤子作為整體從A借助借助(jizh)C移至移至B。第（第（2）步）步 將將3號盤從號盤從A移至移至C，一次到位。記為，一次到位。記為 move 3 from A to C第（第（3）步）步 處于處于B上的作為一個整體的上的作為一個整體的2只盤子，再移至只盤子，再移至C。這一步記為這一步記為 move( 2, B, A, C)意思是將意思是將2只盤子作為整體從只盤子作為整體從B借助借助(jizh)A移至移至C。所謂借助所

33、謂借助(jizh)是什么意思，等這件事做完了不言自明。是什么意思，等這件事做完了不言自明。第67頁/共174頁第六十七頁，共174頁。move (3, A, B, C)move (2, A, C, B)move (1, A, B, C)move (2, B, A, C)ABC213演示演示(ynsh)(ynsh)：移動：移動3 3個個盤子的分解盤子的分解第68頁/共174頁第六十八頁，共174頁。move (3, A, B, C)move (2, A, C, B)move (1, A, B, C)move (1, A, C, B)move (1, C, A, B)move (1, A, B,

34、C)move (2, B, A, C)move (1, B, C, A)move (1, B, A, C)move (1, A, B, C)ABC213第69頁/共174頁第六十九頁，共174頁。4、從題目的約束條件看，大盤上可以隨便摞小盤，、從題目的約束條件看，大盤上可以隨便摞小盤，相反則不允許。在將相反則不允許。在將1號和號和2號盤當整體號盤當整體(zhngt)從從A移至移至B的過程中的過程中 move(2, A, C, B) 實際上是分實際上是分解為以下三步解為以下三步第（第（1）.1步：步：move 1 form A to C;第（第（1）.2步：步：move 2 form A to

35、B;第（第（1）.3步：步：move 1 form C to B;第70頁/共174頁第七十頁，共174頁。經過以上步驟，將經過以上步驟，將 1 號和號和 2 號盤作為整號盤作為整體體(zhngt)從從 A 移至移至 B，為，為 3 號盤從號盤從 A 移至移至 C 創(chuàng)造了條件。同樣，創(chuàng)造了條件。同樣，3號盤一旦到了號盤一旦到了 C，就，就要考慮如何實現將要考慮如何實現將 1 號和號和 2 號盤當整體號盤當整體(zhngt)從從 B 移至移至 C 的過程了。實際上的過程了。實際上 move(2, B, A, C) 也要分解為三步：也要分解為三步：第（第（3）.1步：步：move 1 form B

36、 to A;第（第（3）.2步：步：move 2 form B to C;第（第（3）.3步：步：move 1 form A to C;第71頁/共174頁第七十一頁，共174頁。5、看、看 move(2, A, C, B) 是說要將是說要將 2 只盤子從只盤子從 A 搬至搬至 B，但沒有但沒有 C 是不行的，因為第（是不行的，因為第（1）.1步就要將步就要將 1 盤盤從從 A 移到移到 C，給，給 2 盤創(chuàng)造條件從盤創(chuàng)造條件從 A 移至移至 B，然后再，然后再把把 1 盤從盤從 C 移至移至 B?？吹竭@里就能明白借助。看到這里就能明白借助 C 的的含義了。因此，在構思搬移含義了。因此，在構思

37、搬移(bn y)過程的參量時，過程的參量時，要把要把 3 個柱子都用上。個柱子都用上。第72頁/共174頁第七十二頁，共174頁。6、定義搬移、定義搬移(bn y)函數函數 move(n, A, B, C)，物理，物理意義是將意義是將 n 只盤子從只盤子從 A 經經 B 搬到搬到 C輸出n:A to Cmove(n-1,A,C,B)move(n-1,B,A,C)move(n,A,B,C)考慮到前面已考慮到前面已經研究經研究(ynji)過的過的(1)(2)(3)步，步，可以將搬移過可以將搬移過程用如下的與程用如下的與或結點圖表示。或結點圖表示。第73頁/共174頁第七十三頁，共174頁。這里用與

38、或結點的含義是分解為這里用與或結點的含義是分解為(1)(2)(3)步。這步。這3步是相關的，相互依存的，而且是有序的，從左至右步是相關的，相互依存的，而且是有序的，從左至右執(zhí)行。執(zhí)行。move(n, A, B, C) 分解為分解為3步步(1)move(n-1, A, C, B)理解理解(lji)為將上面的為將上面的n-1只盤子作為只盤子作為一個整體從一個整體從A經經C移至移至B；(2)輸出輸出n：A to C，理解，理解(lji)將將n號盤從號盤從A移至移至C，是直接，是直接可解結點；可解結點；(3)Move(n-1, B, A, C)理解理解(lji)為將上面的為將上面的n-1只盤子作為只盤

39、子作為一個整體從一個整體從B經經A移至移至C。第74頁/共174頁第七十四頁，共174頁。這里這里(zhl)顯然是一種遞歸定義，當著解顯然是一種遞歸定義，當著解 move(n-1, A, C, B)時又可想到，將其分解為時又可想到，將其分解為 3 步：步：第第1步：將上面的步：將上面的n-2只盤子作為一個整體從只盤子作為一個整體從A經經B到到C，move(n-2, A, B, C)；第第2步：第步：第n-1號盤子從號盤子從A直接移至直接移至B，即，即n-1:A to B；第第3步：再將上面的步：再將上面的n-2只盤子作為一個整體從只盤子作為一個整體從C經經A移至移至B，move(n-2, C,

40、 A, B)；下面，我們還是以下面，我們還是以3只盤子為例畫出遞歸的與或圖。只盤子為例畫出遞歸的與或圖。第75頁/共174頁第七十五頁，共174頁。這個圖很象一顆倒置著的樹，結點這個圖很象一顆倒置著的樹，結點move(3, A, B, C)是樹根，是樹根，與結點是樹的分枝與結點是樹的分枝(fn zh)，葉子都是直接可解結點。，葉子都是直接可解結點。輸出1:A to C1:A to C輸出3:A to Cmove(2,A,C,B)move(2,B,A,C)move(3,A,B,C)輸出2:A to B2:A to B輸出1:C to B1:C to B輸出1:B to A1:B to A輸出2:

41、B to C2:B to C輸出1:A to C1:A to Cmove(1,A,B,C) move(1,C,A,B) move(1,B,C,A) move(1,A,B,C)第76頁/共174頁第七十六頁，共174頁。 move(3,A,B,C) move(2,A,C,B) 輸輸出出 3: A to C move(2,B,A,C) move(2,A,C,B) 調調用用 move(1,A,B,C) move(2,B,A,C) 調調用用 move(1,B,C,A) 返返回回 返返回回 調調用用 調調用用 返返回回 move(1,A,B,C) 輸輸出出 2: A to B move(1,C,A,B)

42、 move(1,B,C,A) 輸輸出出 2: B to C move(1,A,B,C) 輸輸出出 1: A to C 輸輸出出 1: B to A 輸輸出出 1: C to B 輸輸出出 1: A to C 4 1 3 2 5 7 6 調調用用 調調用用 返返回回 返返回回 調調用用 move (1,C,A,B) move (1,A,B,C) 第77頁/共174頁第七十七頁，共174頁。 輸出輸出 3: A to C 調用調用 move(1,C,A,B) 輸出：輸出：1: C to B 輸出：輸出：2: A to B move(1,C,A,B) 調用調用 move(1,A,B,C) 輸出輸出

43、1: A to C move(1,A,B,C) move(2,A,C,B) 調用調用 move(2,A,C,B) 調用調用 move(2,B,A,C) 調用調用 move(1,A,B,C) 輸出輸出 1: A to C 輸出：輸出：2: B to C 調用調用 move(1,B,C,A) 輸出輸出 1: B to A move(1,B,C,A) move(2,B,A,C) move(1,A,B,C) move(3,A,B,C) 1 2 3 4 5 6 7 第78頁/共174頁第七十八頁，共174頁。/ */ * 程程 序：序：6_hanoi2002.cpp */ * 作作 者：者：wuwh *

44、/ * 編制時間：編制時間：2002年年10月月13日日 */ * 主要功能：用遞歸求解主要功能：用遞歸求解Hanoi問題問題 */ *#include / 預編譯命令預編譯命令int step=1;/ 整型全局變量整型全局變量,預置預置1,步數步數void move(int m, char p, char q, char r); / 聲明要用到的被調用函數聲明要用到的被調用函數void main()/ 主函數主函數/ 主程序開始主程序開始int n;/ 整型變量整型變量,n為盤數為盤數,printf( 請輸入盤數請輸入盤數 n=“);/ 提示信息提示信息scanf(“/%d”),&n);/

45、輸入正整數輸入正整數nprintf( 在在3根柱子上移根柱子上移%d只盤的步驟為只盤的步驟為:“,n); / 輸出輸出(shch)提示信息提示信息 move(n,a,b,c);/ 調用函數調用函數 move(n,a,b,c)/ 主函數結束主函數結束第79頁/共174頁第七十九頁，共174頁。/ 以下函數是被主程序調用的函數以下函數是被主程序調用的函數/ 函數名：函數名：move/ 輸輸 入：入：m，整型變量，表示盤子數目，整型變量，表示盤子數目/ p，q，r為字符為字符(z f)型變量，表示柱子標號型變量，表示柱子標號/ 返回值：無返回值：無void move(int m, char p, c

46、har q, char r)/ 自定義函數體開始自定義函數體開始if (m=1)/ 如果如果m為為1,則為直接可解結點則為直接可解結點,/ 直接可解結點直接可解結點,輸出移盤信息輸出移盤信息printf(%d move 1# from p to r”, step); step+;/ 步數加步數加1else/ 如果不為如果不為1,則要調用則要調用move(m-1)move(m-1,p,r,q);/ 遞歸調用遞歸調用move(m-1)/直接可解結點直接可解結點,輸出移盤信息輸出移盤信息 printf(%d move %d from p to r”, step,m); step+;/ 步數加步數加1

47、move(m-1,q,p,r);/ 遞歸調用遞歸調用move(m-1)/自定義函數體結束自定義函數體結束第80頁/共174頁第八十頁，共174頁。1111,125;123nmnnnmmmnm nmmnCmnCCCCC習題：已知表示從 個元素中取 個的組合數，又知、試畫出符合上述關系的與或結合圖；、指出哪個是直接可解結點；、畫出求解結點圖；4、寫出遞歸程序求解組合問題。第81頁/共174頁第八十一頁，共174頁。第82頁/共174頁第八十二頁，共174頁。/ */ * 程程 序：序：6_7.cpp * / * 編制時間：編制時間：2002年年10月月28日日 * / * 主要功能：計算組和數主要

48、功能：計算組和數C(m,n) */ *#include / 預編譯預編譯(biny)命令命令Using namespace std;第83頁/共174頁第八十三頁，共174頁。/ 計算(j sun)C(m,n)，即從m個數中取n個數的組合數int C ( int m, int n)if (m0 | n0 | mn)return 0;if (m=n)/ C(m,m)=1return 1;if (n=1)/ C(m,1)=mreturn m;/ C(m,n)=C(m-1,n)+C(m-1,n-1)return C (m-1, n)+C (m-1,n-1);第84頁/共174頁第八十四頁，共174頁

49、。int main()/ 主函數開始主函數開始/ 測試一些結果測試一些結果(ji gu)cout C(6,0)= Cmn(6,0) endl;cout C(6,1)= Cmn(6,1) endl;cout C(6,2)= Cmn(6,2) endl;cout C(6,6)= Cmn(6,6) Y Y；2# 2# 青蛙從青蛙從 L L S S；1# 1# 青蛙從青蛙從 Y Y S S；3# 3# 青蛙從青蛙從 L L Y Y；4# 4# 青蛙從青蛙從 L L R R；3# 3# 青蛙從青蛙從 Y Y R R；1# 1# 青蛙從青蛙從 S S Y Y；2# 2# 青蛙從青蛙從 S S R R；1#

50、 1# 青蛙從青蛙從 Y Y R R；S SY Y5 54 46 6L LR R1 12 23 37 78 89 91#2#4#3#3#1#2#1#1#第91頁/共174頁第九十一頁，共174頁。表一表一第92頁/共174頁第九十二頁，共174頁。 為了將過河過程描述得更清楚，我們給出了表為了將過河過程描述得更清楚，我們給出了表1 1。表中。表中L1 L2 L3 L4L1 L2 L3 L4表示左岸石柱上落在一起的青蛙的高度位置。表示左岸石柱上落在一起的青蛙的高度位置。L1 L1 在最上面，在最上面，L4 L4 在最下面的位置。引入這個信息就可比較在最下面的位置。引入這個信息就可比較容易地看出對

51、青蛙占位的約束條件。同理容易地看出對青蛙占位的約束條件。同理R1 R2 R3 R4R1 R2 R3 R4也是也是如此。對水中石柱如此。對水中石柱S S，也分成兩個高度位置，也分成兩個高度位置S1 S2S1 S2。對荷葉。對荷葉Y Y無須分層，因為它只允許一只青蛙落在其上。無須分層，因為它只允許一只青蛙落在其上。t=0t=0為初始時為初始時刻，青蛙從小到大落在石柱刻，青蛙從小到大落在石柱L L上。上。t=1t=1為第一步：為第一步：1#1#從從L L跳至跳至荷葉荷葉Y Y上；上；L L上只剩上只剩2# 3# 4#2# 3# 4#。T=2 T=2 為第二步；為第二步；2#2#從從L L跳至石跳至石

52、柱柱S S上，處在上，處在S2S2位置上，位置上，L L上只剩上只剩3#3#和和4#4#。T=3T=3為第三步，為第三步，1#1#從從Y Y跳至跳至S S，將，將Y Y清空。這時你看，清空。這時你看，S S上有上有1#1#、2#2#，L L上有上有3#3#、4#4#，好象是原來，好象是原來(yunli)(yunli)在在L L上的上的4 4只青蛙，分成了上下兩只青蛙，分成了上下兩部分，上面的部分，上面的2 2只通過荷葉只通過荷葉y y轉移到了轉移到了S S上。這一過程是一分上。這一過程是一分為二的過程。即將為二的過程。即將L L上的一隊青蛙，分解為兩個隊，每隊各上的一隊青蛙，分解為兩個隊，每隊

53、各二只，且將上面的二只轉移到了二只，且將上面的二只轉移到了S S上。這時我們可以考慮形上。這時我們可以考慮形成兩個系統(tǒng)，一個是成兩個系統(tǒng)，一個是L L，Y Y，R R系統(tǒng)，一個是系統(tǒng)，一個是S S，Y Y，R R系統(tǒng)。前系統(tǒng)。前者二只青蛙號大；后者二只青蛙號小。先跳號大的，再跳號者二只青蛙號大；后者二只青蛙號小。先跳號大的，再跳號小的。從第五步到第九步可以看出的確是這么做的。小的。從第五步到第九步可以看出的確是這么做的。第93頁/共174頁第九十三頁，共174頁。2YRSL31第94頁/共174頁第九十四頁，共174頁。此有：Jump(1,1)=2*Jump(0,1)=2*2=4 第95頁/共

54、174頁第九十五頁，共174頁。現在再看現在再看S=2，y=1 Jump(2,1) 我們將河中的兩個石柱稱作我們將河中的兩個石柱稱作S1和和S2，荷葉叫荷葉叫y，考慮先將，考慮先將L上的青蛙的一上的青蛙的一半半(ybn)借助于借助于S2和和y轉移到轉移到S1上，上，當然是一半當然是一半(ybn)小號的青蛙在小號的青蛙在S1上，大的留在上，大的留在L上。上。y yLR RS1S1S2S2第96頁/共174頁第九十六頁，共174頁。 1第97頁/共174頁第九十七頁，共174頁。S19. 8 2 4第98頁/共174頁第九十八頁，共174頁。LRYS2876543S1214321第99頁/共174

55、頁第九十九頁，共174頁。LS2YR S1S2YR第100頁/共174頁第一百頁，共174頁。這樣這樣 L S1 S2 y R 系統(tǒng)系統(tǒng)(xtng)分解為分解為 ： （L S2 y R 系統(tǒng)系統(tǒng)(xtng)） + （S1 S2 y R 系統(tǒng)系統(tǒng)(xtng)）= 2 * （L S2 y R 系統(tǒng)系統(tǒng)(xtng)）= 2 * Jump(1,1)用歸納法用歸納法Jump(S, y)=2*Jump(S-1, y)第101頁/共174頁第一百零一頁，共174頁。5. 將上述分析出來的規(guī)律將上述分析出來的規(guī)律(gul)寫成遞歸形式的與或結點圖為：寫成遞歸形式的與或結點圖為：Jump(S,y)y+1S!=0

56、S=0Jump(S-1,y)2*Jump(S-1,y)第102頁/共174頁第一百零二頁，共174頁。舉例(j l)：S=3，y=4，算 Jump(3,4)A=Jump(2,4)2*B2*10=20Jump(3,4)2*A2*20=402*C2*5=10C=Jump(0,4)S=04+1 5B=Jump(1,4)3(3,4)2 (1)2 (4 1)40SJumpy第103頁/共174頁第一百零三頁，共174頁。/ */ * 程程 序：序：6_5.cpp */ * 作作 者：者：wuwh */ * 編制編制(binzh)時間：時間：2002年年10月月20日日 */ * 主要功能：青蛙過河主要功

57、能：青蛙過河 */ *#include /預編譯命令預編譯命令int Jump(int, int);/聲明有被調用函數聲明有被調用函數void main()/主函數主函數/主程序開始主程序開始int s=0,y=0,sum=0;/整型變量整型變量,s為河中石柱數為河中石柱數,y為荷葉數為荷葉數cout s;/輸入正整數輸入正整數scout y;/輸入正整數輸入正整數ysum = Jump ( s , y ) ;/Jump(s,y)為被調用函數為被調用函數cout Jump( s , /輸出結果輸出結果 y )= sum endl;/主程序結束主程序結束第104頁/共174頁第一百零四頁，共17

58、4頁。/ */ * 程程 序：序：6_5.cpp */ * 作作 者：者：wuwh */ * 編制編制(binzh)時間：時間：2002年年10月月20日日 */ * 主要功能：青蛙過河主要功能：青蛙過河(遞歸遞歸) */ *第105頁/共174頁第一百零五頁，共174頁。#include /預編譯命令預編譯命令int Jump(int, int);/聲明聲明(shngmng)有被調用函有被調用函數數int main()/主函數主函數 int s=0,y=0,sum=0; cout s;/輸入正整數輸入正整數s cout y;/輸入正整數輸入正整數y sum = Jump ( s , y )

59、;/Jump(s,y)為被調用函數為被調用函數 cout Jump( s , /輸出結果輸出結果 y )= sum =rl=rA sort(l,r)數據在al,.,ar中數據在al,.,ar中B什么也不做什么也不做ClrD分區(qū)處理分區(qū)處理Fsort(m+1,r)Esort(l,m-1)第111頁/共174頁第一百一十一頁，共174頁。第112頁/共174頁第一百一十二頁，共174頁。分區(qū)處理：分區(qū)處理：1、讓、讓 k=a z 2、將、將 k 放在放在 a m 3、使、使 az, az+1 , , a m-1 = a m 4、使、使 a m = y，則什么也不做。這是直接可解結，則什么也不做。這

60、是直接可解結點。點。C 結點是在結點是在 z y 情況下情況下 A 結點的解。結點的解。C 是一個與結點。要是一個與結點。要對對 C 求解需分解為三步。依次為：求解需分解為三步。依次為：第113頁/共174頁第一百一十三頁，共174頁。1、先解、先解 D 結點，結點，D 結點是一個直接可解結點，功能是結點是一個直接可解結點，功能是進行所謂的分區(qū)進行所謂的分區(qū)(fn q)處理，規(guī)定這一步要做的處理，規(guī)定這一步要做的事情是事情是（1）將）將 a z 中的元素放到它應該在的位置上，比如中的元素放到它應該在的位置上，比如 m 位置。這時位置。這時 a m a z ；（2）讓下標從）讓下標從 z 到到

61、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。（見下圖）（見下圖）第114頁/共174頁第一百一十四頁，共174頁。azyam下標下標(xi bio)：下標下標(xi bio)：zm-1ym+1第115頁/共174頁第一百一十五頁，共174頁。2、再解、再解 E 結點，這時要處理的是結點，

62、這時要處理的是 a 0 a 3 ；3、再解、再解 F 結點，處理結點，處理a 5 ,a 6 。下面下面(xi mian)按照這種思路構思一個快速排序的程序按照這種思路構思一個快速排序的程序框圖?？驁D。void sort( int array , int zz, int yy )int z, y, i , k ;第116頁/共174頁第一百一十六頁，共174頁。 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

63、 ; 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 y r = a r r a y l; w h ile (l!= r ); a r r a y l= k ; fo r (i= ll; i = r r ; i= i+ 1 ) 輸輸 出出 a r r a y i; 換換 行行 ; s o r t(a r r a y, ll, l-1 ); s o r t(a r r a y, l+ 1 , r r ); 第117頁/共174頁第一百一十七頁，共174頁。下面舉例說明排序下面舉例

64、說明排序(pi (pi x)x)過程過程圖圖1 a數組中有數組中有7個元素個元素(yun s)待排序待排序1 讓讓 k = a z = a 0 = 5zy圖圖 1k第118頁/共174頁第一百一十八頁，共174頁。2 進入直到型循環(huán)進入直到型循環(huán)(xnhun)執(zhí)行（執(zhí)行（1）ay=a6=4 不滿足當循環(huán)不滿足當循環(huán)(xnhun)條件，條件，y不動。不動。執(zhí)行（執(zhí)行（2）zy，做兩件事：，做兩件事：a z = a y ，即，即a 0 = a 6 = 4，z = z +1 = 0+1 = 1，見圖，見圖2zy 圖圖 2k第119頁/共174頁第一百一十九頁，共174頁。執(zhí)行（執(zhí)行（3）圖）圖2中的

65、中的a1k滿足當循環(huán)的條件滿足當循環(huán)的條件(tiojin)，y = y-1 = 6-1 = 5見圖見圖5，之后退出當循環(huán)，因為，之后退出當循環(huán)，因為 a y = 3kzy圖圖 5k第122頁/共174頁第一百二十二頁，共174頁。執(zhí)行執(zhí)行(zhxng)（2）a z =a y ，并讓，并讓 z = z+1=3，見，見圖圖6 zy圖圖 6k第123頁/共174頁第一百二十三頁，共174頁。執(zhí)行（執(zhí)行（3）由于）由于a3=1k，退出循環(huán)，退出循環(huán)(xnhun)。見圖。見圖7 zy圖圖 7k第124頁/共174頁第一百二十四頁，共174頁。執(zhí)行（執(zhí)行（4）az=ay，a5=7。見圖。見圖8 這時仍然這

66、時仍然(rngrn) zk，讓，讓 y = y-1 = 4。見圖。見圖9zy圖圖 9k第126頁/共174頁第一百二十六頁，共174頁。之后，之后，z = y，退出直到，退出直到(zhdo)型循環(huán)，做型循環(huán)，做 a z = k，z = 4， a 4 = 5，這是，這是 5 的最終位置，的最終位置，5 將整個數據分成左右兩將整個數據分成左右兩個集合，見圖個集合，見圖10。zy圖圖 10左左右右k第127頁/共174頁第一百二十七頁，共174頁。用上述用上述(shngsh)思路去排左邊的部分思路去排左邊的部分從從 z = 0 到到 y = 3，見圖，見圖11。讓。讓 k = a z = a 0 = 4，然后進到直到，然后進到直到型循環(huán)，型循環(huán)，執(zhí)行（執(zhí)行（1）a y = 1k，不滿足當循環(huán)的條件，不滿足當循環(huán)的條件，y不動。不動。執(zhí)行（執(zhí)行（2）a z = a y ，z = z+1 = 1, 見圖見圖12zy圖圖 12zy圖圖 11k第128頁/共174頁第一百二十八頁，共174頁。執(zhí)行（執(zhí)行（3）a z k，z=z+1=2，a2k，z=z+1=3，這時，這時z=y，不會執(zhí)行（，不會執(zhí)行（