《算法語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)第5章學(xué)習(xí)教案》由會(huì)員分享，可在線閱讀，更多相關(guān)《算法語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)第5章學(xué)習(xí)教案（174頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

2、的分支條件if ( checkprime(a) ) / checkprime(a)為1cout a 是素?cái)?shù) endl;else/ checkprime(a)為0cout a 不是(b shi)素?cái)?shù) endl;/ 主函數(shù)結(jié)束第3頁(yè)/共174頁(yè)第三頁(yè)，共174頁(yè)。n/ 用實(shí)參 a 調(diào)用子函數(shù)(hnsh)，該子函數(shù)(hnsh)的n/ 返回值作為 if 語(yǔ)句的分支條件nif ( checkprime( a ) ) n/ checkprime( a ) 為 1ncout a 是素?cái)?shù) endl;nnelsen / checkprime( a ) 為 0n cout a 不是素?cái)?shù) endl;nn/ 主函數(shù)(

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

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

5、( b % k = 0 ) return 0; return 1; / b不能被不能被k整除整除(zhngch)，則返回，則返回1 / 說(shuō)明說(shuō)明 b 是質(zhì)數(shù)是質(zhì)數(shù)第第5章章 函數(shù)函數(shù)(hnsh)第8頁(yè)/共174頁(yè)第八頁(yè)，共174頁(yè)。 講這一程序的目的：講這一程序的目的：如何定義一個(gè)函數(shù)如何定義一個(gè)函數(shù)主函數(shù)怎樣調(diào)用子函數(shù)主函數(shù)怎樣調(diào)用子函數(shù)實(shí)在參數(shù)和形式參數(shù)實(shí)在參數(shù)和形式參數(shù)返回值是什么返回值是什么(shn me)意思意思第9頁(yè)/共174頁(yè)第九頁(yè)，共174頁(yè)。第第5章章 函數(shù)函數(shù)(hnsh)第10頁(yè)/共174頁(yè)第十頁(yè)，共174頁(yè)。第第5章章 函數(shù)函數(shù)(hnsh)第11頁(yè)/共174頁(yè)第十一頁(yè)，共

6、174頁(yè)。第12頁(yè)/共174頁(yè)第十二頁(yè)，共174頁(yè)。第13頁(yè)/共174頁(yè)第十三頁(yè)，共174頁(yè)。第14頁(yè)/共174頁(yè)第十四頁(yè)，共174頁(yè)。第15頁(yè)/共174頁(yè)第十五頁(yè)，共174頁(yè)。第16頁(yè)/共174頁(yè)第十六頁(yè)，共174頁(yè)。輸出(shch) 輸出(shch) return 0 return 1 a是質(zhì)數(shù) a不是質(zhì)數(shù)返回第17頁(yè)/共174頁(yè)第十七頁(yè)，共174頁(yè)。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

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

8、 )power( , )mim li l第25頁(yè)/共174頁(yè)第二十五頁(yè)，共174頁(yè)。第26頁(yè)/共174頁(yè)第二十六頁(yè)，共174頁(yè)。int power(int p, int q);/ 聲明函數(shù)power第27頁(yè)/共174頁(yè)第二十七頁(yè)，共174頁(yè)。第28頁(yè)/共174頁(yè)第二十八頁(yè)，共174頁(yè)。for(i=1; i=m; i+ )sum=sum+power( i, l );/ 累加return sum; / 返回值第29頁(yè)/共174頁(yè)第二十九頁(yè)，共174頁(yè)。第30頁(yè)/共174頁(yè)第三十頁(yè)，共174頁(yè)。第31頁(yè)/共174頁(yè)第三十一頁(yè)，共174頁(yè)。例例:int power(int p, int n)power

9、 為函數(shù)為函數(shù)(hnsh)名，要以英文字母開(kāi)頭。名，要以英文字母開(kāi)頭。int 是函數(shù)是函數(shù)(hnsh)值的數(shù)據(jù)類(lèi)型，這里是值的數(shù)據(jù)類(lèi)型，這里是int（整（整型）。型）。(int p, int n) 括號(hào)中的括號(hào)中的 p, n為函數(shù)為函數(shù)(hnsh)的形式參數(shù)，的形式參數(shù)，形式參數(shù)也要定義其數(shù)據(jù)類(lèi)型。形式參數(shù)也要定義其數(shù)據(jù)類(lèi)型。第32頁(yè)/共174頁(yè)第三十二頁(yè)，共174頁(yè)。函數(shù)定義的一般(ybn)格式： ()第33頁(yè)/共174頁(yè)第三十三頁(yè)，共174頁(yè)。形式參數(shù)與實(shí)在(shzi)參數(shù)1、形式參數(shù)是在定義函數(shù)時(shí)放在函數(shù)名后括號(hào)中的參數(shù)。在未、形式參數(shù)是在定義函數(shù)時(shí)放在函數(shù)名后括號(hào)中的參數(shù)。在未進(jìn)行進(jìn)行

10、(jnxng)函數(shù)調(diào)用時(shí)，并不對(duì)形式參數(shù)分配內(nèi)存單元。在函數(shù)調(diào)用時(shí)，并不對(duì)形式參數(shù)分配內(nèi)存單元。在發(fā)生函數(shù)調(diào)用時(shí)，立刻給形式參數(shù)分配內(nèi)存單元。調(diào)用結(jié)束發(fā)生函數(shù)調(diào)用時(shí)，立刻給形式參數(shù)分配內(nèi)存單元。調(diào)用結(jié)束后，釋放掉行參所占的內(nèi)存單元。后，釋放掉行參所占的內(nèi)存單元。2、因此，形參變量屬于局部變量，其作用域在它所在的函數(shù)體、因此，形參變量屬于局部變量，其作用域在它所在的函數(shù)體內(nèi)。內(nèi)。3、在定義函數(shù)的時(shí)候，必須指定形參變量的類(lèi)型，如下所示、在定義函數(shù)的時(shí)候，必須指定形參變量的類(lèi)型，如下所示int power(int p, int n) / 函數(shù)函數(shù)(hnsh)體體 c第34頁(yè)/共174頁(yè)第三十四頁(yè)，共

11、174頁(yè)。4、實(shí)在參數(shù)是一個(gè)具有確定值的表達(dá)式。函數(shù)在調(diào)用時(shí)，將實(shí)在參數(shù)賦給形式參數(shù)。比如，主函數(shù)調(diào)用SOP(n,k)，這時(shí)，n,k為實(shí)在參數(shù)，n的值為6，k的值為4。在被調(diào)用函數(shù)定義中，int SOP(m,l) 中的 m, l 為形式參數(shù)，在SOP被調(diào)用時(shí)，系統(tǒng)給 m, l 這兩個(gè)形式參數(shù)分配(fnpi)了內(nèi)存單元。之后，n 的值 6 賦給 m; k 的值 4 賦給 l。第35頁(yè)/共174頁(yè)第三十五頁(yè)，共174頁(yè)。power( i, l ) 處在 SOP( m, l ) 函數(shù)中，表示SOP函數(shù)去調(diào)用 power 函數(shù)。其中 i, l 為實(shí)在(shzi)參數(shù)，而 int power( p, q

12、 )中的 p, q 為形式參數(shù)。比如，執(zhí)行 SOP( 6, 4 )時(shí)，l=4, m=6,當(dāng) i=1 時(shí)，sum = sum + power( 1, 4 )這里 1，4 為實(shí)在(shzi)參數(shù)，調(diào)用power( p, q )，兩個(gè)形式參數(shù) p, q 分別被賦以 1，4 。第36頁(yè)/共174頁(yè)第三十六頁(yè)，共174頁(yè)。 執(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 + 8

13、1 = 98 i=4: sum = sum + power(i,l) = 98 + 256 = 354 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 調(diào)用 返回 執(zhí)行執(zhí)行 power(2, 4): product = 2*2*2*2 return(16) = 16 調(diào)用 返回 執(zhí)行執(zhí)行 power(3, 4):

14、 product = 3*3*3*3 return(81) = 81 調(diào)用 返回 執(zhí)行執(zhí)行 power(4, 4): product = 4*4*4*4 return(256) = 256 調(diào)用 返回 執(zhí)行執(zhí)行 power(5, 4): product = 5*5*5*5 return(625) = 625 調(diào)用 返回 執(zhí)行執(zhí)行 power(6, 4): product = 6*6*6*6 return(1296) = 1296 調(diào)用 返回 SOP(n,k) 調(diào)用調(diào)用 第37頁(yè)/共174頁(yè)第三十七頁(yè)，共174頁(yè)。遞遞 推推第38頁(yè)/共174頁(yè)第三十八頁(yè)，共174頁(yè)。第39頁(yè)/共174頁(yè)第三十九

15、頁(yè)，共174頁(yè)。第40頁(yè)/共174頁(yè)第四十頁(yè)，共174頁(yè)。寫(xiě)成一般式fish i = ( fish i - 1 1 ) * 4 / 5i = 2, 3, ,5這個(gè)公式可用于知 A 看到的魚(yú)數(shù)去推算(tu sun) B 看到的，再推算(tu sun) C 看到的，.。現(xiàn)在要求的是 A 看到的，能否倒過(guò)來(lái)，先知 E 看到的再反推 D 看到的，直到A看到的。為此將上式改寫(xiě)為：fish i-1 = fish i * 5 / 4 +1i = 5, 4,2第41頁(yè)/共174頁(yè)第四十一頁(yè)，共174頁(yè)。分析上式. 當(dāng) i = 5 時(shí)，fish 5 表示 E 醒來(lái)所看到的魚(yú)數(shù)，該數(shù)應(yīng)滿足(mnz)被整除后余，即

16、fish 5 % 5 = 1 2. 當(dāng) i = 5 時(shí)，fish i-1 表示 D 醒來(lái)所看到的魚(yú)數(shù)，這個(gè)數(shù)既要滿足(mnz)fish 4 = fish 5 * 5 / 4 + 1 又要滿足(mnz)fish 4 % 5 = 1顯然，fish 4 不能不是整數(shù)，這個(gè)結(jié)論同樣可以用至 fish 3 , fish 2 和 fish 1 第42頁(yè)/共174頁(yè)第四十二頁(yè)，共174頁(yè)。3 . 按題意要求 5 人合伙捕到的最少魚(yú)數(shù)，可以從小往大枚舉(mi j)，可以先讓 E 所看到的魚(yú)數(shù)最少為 6 條，即 fish 5 初始化為 6 來(lái)試，之后每次增加 5 再試，直至遞推到 fish 1 得整數(shù)且除以 5

17、 之后的余數(shù)為 1。根據(jù)上述思路，我們可以構(gòu)思如下的程序框圖：第43頁(yè)/共174頁(yè)第四十三頁(yè)，共174頁(yè)。 定義數(shù)組 fish6，并初始化為 1； 定義循環(huán)控制變量 i，并初始化為 0。 輸出計(jì)算結(jié)果 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頁(yè)/共174頁(yè)第四十四頁(yè)，共174頁(yè)。該圖可分為三部分該圖可分為三部分(1) 是說(shuō)明部分：包含定義數(shù)組是說(shuō)明部

18、分：包含定義數(shù)組 fish6，并初始化為，并初始化為 1 和定和定義循環(huán)控制變量義循環(huán)控制變量 i，并初始化為，并初始化為 0。(2) 是是 do.while 直到型循環(huán)，其循環(huán)體又含兩塊：直到型循環(huán)，其循環(huán)體又含兩塊：(2).1 是枚舉過(guò)程是枚舉過(guò)程(guchng)中的中的 fish5 的初值設(shè)置，的初值設(shè)置，一開(kāi)始一開(kāi)始 fish5=1+5; 以后每次增以后每次增 5。(2).2 是一個(gè)是一個(gè) for 循環(huán)，循環(huán)，i 的初值為的初值為 4，終值為，終值為 1，步長(zhǎng)，步長(zhǎng)為為 -1，該循環(huán)的循環(huán)體是一個(gè)分支語(yǔ)句，該循環(huán)的循環(huán)體是一個(gè)分支語(yǔ)句， 如果如果 fishi+1不能被不能被 4 整除，

19、則跳出整除，則跳出 for 循環(huán)（使用循環(huán)（使用 break 語(yǔ)句）語(yǔ)句）; 否則，從否則，從 fishi+1 算出算出 fishi。第45頁(yè)/共174頁(yè)第四十五頁(yè)，共174頁(yè)。當(dāng)由 break 語(yǔ)句讓程序退出循環(huán)時(shí)，意味著某人看到的魚(yú)數(shù)不是整數(shù)，當(dāng)然不是所求，必須令fish 5 加 5 后再試，即重新進(jìn)入直到型循環(huán) do while 的循環(huán)體。當(dāng)著正常退出 for 循環(huán)時(shí)，一定是控制變量 i 從初值 4，一步一步執(zhí)行到終值 1，每一步的魚(yú)數(shù)均為整數(shù)，最后 i = 0，表示計(jì)算(j sun)完畢，且也達(dá)到了退出直到型循環(huán)的條件。(3) 輸出計(jì)算(j sun)結(jié)果第46頁(yè)/共174頁(yè)第四十六頁(yè)，

20、共174頁(yè)。/*/* 程 序 名：5_3.c（五人合伙捕魚(yú)） */* 作 者：wuwh */* 編制時(shí)間：2002年10月2日 */* 主要功能：遞推算法(sun f)的實(shí)現(xiàn) */*#include / 預(yù)編譯命令void main() /主函數(shù) int fish6=1,1,1,1,1,1; / 整型數(shù)組，記錄每人醒來(lái)后看到的魚(yú)數(shù) int i=0; do fish5=fish5+5; / 讓E看到的魚(yú)數(shù)增5。 for (i=4; i=1; i-) if ( fishi+1%4 !=0 )break; / 跳出for循環(huán)elsefishi=fishi+1*5/4+1;/ 計(jì)算第i人看到的魚(yú)數(shù) w

21、hile( i=1 ); / 當(dāng) i=1 繼續(xù)做do循環(huán) / 輸出計(jì)算結(jié)果 for (i=1; i1 時(shí)，時(shí)，A 的取值即的取值即 C 的值，的值，而而 C 的值即的值即 E 的值，為了的值，為了(wi le)求得求得 E 的值，需的值，需要先求出要先求出 D 的值。的值。D 值值 fact( n-1 ) 乘以乘以 n 即為即為 E 的的值。值。A fact(n)Bfact(1)=1Cn1n=1Dfact(n-1)En*fact(n-1)第55頁(yè)/共174頁(yè)第五十五頁(yè)，共174頁(yè)。與結(jié)點(diǎn)可能有多個(gè)與結(jié)點(diǎn)可能有多個(gè)(du )相關(guān)聯(lián)的點(diǎn)，這時(shí)可描述為下相關(guān)聯(lián)的點(diǎn)，這時(shí)可描述為下圖圖A 結(jié)點(diǎn)的值最終

22、為結(jié)點(diǎn)的值最終為 D 的值，但為了求的值，但為了求 D 需先求需先求 B 和和 C。從圖上看。從圖上看, 先求左邊的點(diǎn)才能求最右邊的點(diǎn)的值，先求左邊的點(diǎn)才能求最右邊的點(diǎn)的值，我們我們(w men)約定最右邊約定最右邊 D 點(diǎn)的值就是點(diǎn)的值就是 A 結(jié)點(diǎn)的值。結(jié)點(diǎn)的值。ABDC第56頁(yè)/共174頁(yè)第五十六頁(yè)，共174頁(yè)。下面我們以下面我們以3！為例來(lái)畫(huà)與或結(jié)點(diǎn)圖，目的是體！為例來(lái)畫(huà)與或結(jié)點(diǎn)圖，目的是體會(huì)會(huì)(thu)遞歸的含義。遞歸的含義。C = 1D = 2*C = 2B = D = 2E = 3*B = 3*2 = 6A = E = 61=1131Bfact(2)3*fact(2)fact(3

23、)Cfact(1)D2*fact(1)AE21第57頁(yè)/共174頁(yè)第五十七頁(yè)，共174頁(yè)。下面下面(xi mian)畫(huà)出了調(diào)用和返回的遞歸示意圖畫(huà)出了調(diào)用和返回的遞歸示意圖 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調(diào)用調(diào)用調(diào)用調(diào)用第58頁(yè)/共174頁(yè)第五十八頁(yè)，共174頁(yè)。從圖可以想象：從圖可以想象：欲求欲求 fact( 3 )，先要求，先要求 fact( 2 )；要求；要求 fact( 2 ) 先求

24、先求 fact( 1 )。就象剝一顆圓白菜，從外向里，一。就象剝一顆圓白菜，從外向里，一層層剝下來(lái)層層剝下來(lái)(xi li)，到了菜心，遇到，到了菜心，遇到 1 的階乘，其的階乘，其值為值為1，到達(dá)了遞歸的邊界。然后再用，到達(dá)了遞歸的邊界。然后再用 fact( n )=n*fact( n-1 ) 這個(gè)普遍公式，從里向外倒推這個(gè)普遍公式，從里向外倒推回去得到回去得到 fact( n ) 的值。的值。為了把這個(gè)問(wèn)題說(shuō)得再透徹一點(diǎn)。我們畫(huà)了如為了把這個(gè)問(wèn)題說(shuō)得再透徹一點(diǎn)。我們畫(huà)了如下的流程圖：下的流程圖：第59頁(yè)/共174頁(yè)第五十九頁(yè)，共174頁(yè)。 31 fact(3) 真真 假假 調(diào)調(diào)用用 fact

25、(2) 計(jì)計(jì)算算 3*fact(2) fact(2) fact(1) 21 真真 假假 調(diào)調(diào)用用 fact(1) 計(jì)計(jì)算算 2*fact(1) 11 真真 假假 fact(1) 1 返返回回 返返回回 第60頁(yè)/共174頁(yè)第六十頁(yè)，共174頁(yè)。為了形象為了形象(xngxing)地描述遞歸過(guò)程，將上圖改畫(huà)成下圖地描述遞歸過(guò)程，將上圖改畫(huà)成下圖 fact(3) 真真 假假 3=1 調(diào)調(diào)用用 fact(2) 真真 假假 假假 真真 2=1 1=1 fact(2)=2*fact(1) 返返回回 fact(3)=3*fact(2) 返返回回 調(diào)調(diào)用用 fact(1) fact(1) =1 返返回回 第6

26、1頁(yè)/共174頁(yè)第六十一頁(yè)，共174頁(yè)。在這個(gè)圖中在這個(gè)圖中“內(nèi)層內(nèi)層”與與“外層外層”有著相同的結(jié)構(gòu)。它們之間有著相同的結(jié)構(gòu)。它們之間“你你中有我，我中有你中有我，我中有你”，呈現(xiàn)相互依存的關(guān)系。，呈現(xiàn)相互依存的關(guān)系。為了進(jìn)一步講清遞歸的概念，將遞歸與遞推做一比較。仍為了進(jìn)一步講清遞歸的概念，將遞歸與遞推做一比較。仍以求階乘以求階乘(ji chn)為例。為例。遞推是從已知的初始條件出發(fā)，逐次去求所需要的階乘遞推是從已知的初始條件出發(fā)，逐次去求所需要的階乘(ji chn)值。值。如求如求 3！初始條件初始條件 fact( 1 ) = 1fact( 2 ) = 2 * fact( 1 ) = 2

27、fact( 3 ) = 3 * fact( 2 ) = 6第62頁(yè)/共174頁(yè)第六十二頁(yè)，共174頁(yè)。這相當(dāng)于從菜心這相當(dāng)于從菜心“推到推到”外層。而遞歸算法的出發(fā)外層。而遞歸算法的出發(fā)點(diǎn)不放在初始條件上，而放在求解的目標(biāo)上，從所求點(diǎn)不放在初始條件上，而放在求解的目標(biāo)上，從所求的未知項(xiàng)出發(fā)逐次調(diào)用本身的求解過(guò)程，直到遞歸的的未知項(xiàng)出發(fā)逐次調(diào)用本身的求解過(guò)程，直到遞歸的邊界（即初始條件）。就本例而言，讀者會(huì)認(rèn)為遞歸邊界（即初始條件）。就本例而言，讀者會(huì)認(rèn)為遞歸算法可能是多余的，費(fèi)力而不討好。但許多實(shí)際問(wèn)題算法可能是多余的，費(fèi)力而不討好。但許多實(shí)際問(wèn)題不可能或不容易找到顯而易見(jiàn)的遞推關(guān)系，這時(shí)遞歸

28、不可能或不容易找到顯而易見(jiàn)的遞推關(guān)系，這時(shí)遞歸算法就表現(xiàn)出了明顯的優(yōu)越性。下面算法就表現(xiàn)出了明顯的優(yōu)越性。下面(xi mian)我們將我們將會(huì)看到，遞歸算法比較符合人的思維方式，邏輯性強(qiáng)，會(huì)看到，遞歸算法比較符合人的思維方式，邏輯性強(qiáng)，可將問(wèn)題描述得簡(jiǎn)單扼要，具有良好的可讀性，易于可將問(wèn)題描述得簡(jiǎn)單扼要，具有良好的可讀性，易于理解，許多看來(lái)相當(dāng)復(fù)雜，或難以下手的問(wèn)題，如果理解，許多看來(lái)相當(dāng)復(fù)雜，或難以下手的問(wèn)題，如果能夠使用遞歸算法就會(huì)使問(wèn)題變得易于處理。下面能夠使用遞歸算法就會(huì)使問(wèn)題變得易于處理。下面(xi mian)舉一個(gè)盡人皆知的例子哈諾（舉一個(gè)盡人皆知的例子哈諾（Hanoi）塔問(wèn)）塔問(wèn)

29、題。題。第63頁(yè)/共174頁(yè)第六十三頁(yè)，共174頁(yè)。故事：故事：相傳在古代印度的相傳在古代印度的 Bramah 廟中，有位僧人整天把廟中，有位僧人整天把三根柱子上的金盤(pán)倒來(lái)倒去，原來(lái)他是想把三根柱子上的金盤(pán)倒來(lái)倒去，原來(lái)他是想把64個(gè)一個(gè)一個(gè)比一個(gè)小的金盤(pán)從一根柱子上移到另一根柱子上個(gè)比一個(gè)小的金盤(pán)從一根柱子上移到另一根柱子上去。移動(dòng)過(guò)程中恪守下述規(guī)則：每次只允許移動(dòng)一去。移動(dòng)過(guò)程中恪守下述規(guī)則：每次只允許移動(dòng)一只盤(pán)，且大盤(pán)不得落在小盤(pán)上面。有人會(huì)覺(jué)得這很只盤(pán)，且大盤(pán)不得落在小盤(pán)上面。有人會(huì)覺(jué)得這很簡(jiǎn)單，真的動(dòng)手移盤(pán)就會(huì)發(fā)現(xiàn)，如以每秒移動(dòng)一只簡(jiǎn)單，真的動(dòng)手移盤(pán)就會(huì)發(fā)現(xiàn)，如以每秒移動(dòng)一只盤(pán)子盤(pán)子

30、(pn zi)的話，按照上述規(guī)則將的話，按照上述規(guī)則將64只盤(pán)子只盤(pán)子(pn zi)從一個(gè)柱子移至另一個(gè)柱子上，所需時(shí)間約為從一個(gè)柱子移至另一個(gè)柱子上，所需時(shí)間約為5800億年。億年。 第64頁(yè)/共174頁(yè)第六十四頁(yè)，共174頁(yè)。怎樣編寫(xiě)這種程序？思路上還是先從最簡(jiǎn)單的情況怎樣編寫(xiě)這種程序？思路上還是先從最簡(jiǎn)單的情況(qngkung)分析起，搬一搬看，慢慢理出思路。分析起，搬一搬看，慢慢理出思路。1、在、在A柱上只有一只盤(pán)子柱上只有一只盤(pán)子(pn zi)，假定盤(pán)號(hào)為，假定盤(pán)號(hào)為1，這時(shí)只需將該盤(pán)從這時(shí)只需將該盤(pán)從A搬至搬至C，一次完成，記為，一次完成，記為move 1 from A to C

31、(演示演示)ABC1第65頁(yè)/共174頁(yè)第六十五頁(yè)，共174頁(yè)。2、在、在A柱上有二只盤(pán)子柱上有二只盤(pán)子(pn zi)，1為小盤(pán)，為小盤(pán)，2為大盤(pán)。為大盤(pán)。第（第（1）步將）步將1號(hào)盤(pán)從號(hào)盤(pán)從A移至移至B，這是為了讓，這是為了讓2號(hào)盤(pán)能移動(dòng)；號(hào)盤(pán)能移動(dòng)；第（第（2）步將）步將2號(hào)盤(pán)從號(hào)盤(pán)從A移至移至C；第（第（3）步再將）步再將1號(hào)盤(pán)從號(hào)盤(pán)從B移至移至C；這三步記為（演示）：這三步記為（演示）：ABC21move 1 from A to B;move 2 from A to C;move 3 form B to C;第66頁(yè)/共174頁(yè)第六十六頁(yè)，共174頁(yè)。3、在、在A柱上有柱上有3只盤(pán)子，

32、從小到大分別為只盤(pán)子，從小到大分別為1號(hào)，號(hào)，2號(hào)，號(hào)，3號(hào)號(hào)第（第（1）步）步 將將1號(hào)盤(pán)和號(hào)盤(pán)和2號(hào)盤(pán)視為一個(gè)整體；先將二者作為號(hào)盤(pán)視為一個(gè)整體；先將二者作為整體從整體從A移至移至B，給，給3號(hào)盤(pán)創(chuàng)造能夠號(hào)盤(pán)創(chuàng)造能夠(nnggu)一次移至一次移至C的機(jī)會(huì)。這一步記為的機(jī)會(huì)。這一步記為 move( 2, A, C, B) 意思是將上面的意思是將上面的2只盤(pán)子作為整體從只盤(pán)子作為整體從A借助借助C移至移至B。第（第（2）步）步 將將3號(hào)盤(pán)從號(hào)盤(pán)從A移至移至C，一次到位。記為，一次到位。記為 move 3 from A to C第（第（3）步）步 處于處于B上的作為一個(gè)整體的上的作為一個(gè)整體的2

33、只盤(pán)子，再移至只盤(pán)子，再移至C。這一步記為這一步記為 move( 2, B, A, C)意思是將意思是將2只盤(pán)子作為整體從只盤(pán)子作為整體從B借助借助A移至移至C。所謂借助是什么意思，等這件事做完了不言自明。所謂借助是什么意思，等這件事做完了不言自明。第67頁(yè)/共174頁(yè)第六十七頁(yè)，共174頁(yè)。move (3, A, B, C)move (2, A, C, B)move (1, A, B, C)move (2, B, A, C)ABC213演示演示(ynsh)(ynsh)：移動(dòng)：移動(dòng)3 3個(gè)盤(pán)子個(gè)盤(pán)子的分解的分解第68頁(yè)/共174頁(yè)第六十八頁(yè)，共174頁(yè)。move (3, A, B, C)mov

34、e (2, A, C, B)move (1, A, B, C)move (1, A, C, B)move (1, C, A, B)move (1, A, B, C)move (2, B, A, C)move (1, B, C, A)move (1, B, A, C)move (1, A, B, C)ABC213第69頁(yè)/共174頁(yè)第六十九頁(yè)，共174頁(yè)。4、從題目的約束條件看，大盤(pán)上可以隨便摞小盤(pán)，、從題目的約束條件看，大盤(pán)上可以隨便摞小盤(pán)，相反則不允許相反則不允許(ynx)。在將。在將1號(hào)和號(hào)和2號(hào)盤(pán)當(dāng)整體號(hào)盤(pán)當(dāng)整體從從A移至移至B的過(guò)程中的過(guò)程中 move(2, A, C, B) 實(shí)際上是

35、分實(shí)際上是分解為以下三步解為以下三步第（第（1）.1步：步：move 1 form A to C;第（第（1）.2步：步：move 2 form A to B;第（第（1）.3步：步：move 1 form C to B;第70頁(yè)/共174頁(yè)第七十頁(yè)，共174頁(yè)。經(jīng)過(guò)以上步驟經(jīng)過(guò)以上步驟(bzhu)，將，將 1 號(hào)和號(hào)和 2 號(hào)號(hào)盤(pán)作為整體從盤(pán)作為整體從 A 移至移至 B，為，為 3 號(hào)盤(pán)從號(hào)盤(pán)從 A 移至移至 C 創(chuàng)造了條件。同樣，創(chuàng)造了條件。同樣，3號(hào)盤(pán)一旦到了號(hào)盤(pán)一旦到了 C，就，就要考慮如何實(shí)現(xiàn)將要考慮如何實(shí)現(xiàn)將 1 號(hào)和號(hào)和 2 號(hào)盤(pán)當(dāng)整體從號(hào)盤(pán)當(dāng)整體從 B 移至移至 C 的過(guò)程了。

36、實(shí)際上的過(guò)程了。實(shí)際上 move(2, B, A, C) 也要分解為三步：也要分解為三步：第（第（3）.1步：步：move 1 form B to A;第（第（3）.2步：步：move 2 form B to C;第（第（3）.3步：步：move 1 form A to C;第71頁(yè)/共174頁(yè)第七十一頁(yè)，共174頁(yè)。5、看、看 move(2, A, C, B) 是說(shuō)要將是說(shuō)要將 2 只盤(pán)子從只盤(pán)子從 A 搬至搬至 B，但沒(méi)有，但沒(méi)有 C 是不行的，因?yàn)榈冢ㄊ遣恍械?，因?yàn)榈冢?）.1步就要將步就要將 1 盤(pán)從盤(pán)從 A 移到移到 C，給，給 2 盤(pán)創(chuàng)造條件從盤(pán)創(chuàng)造條件從 A 移至移至 B，然后再

37、把然后再把 1 盤(pán)從盤(pán)從 C 移至移至 B?？吹竭@里就能明白借?？吹竭@里就能明白借助助 C 的含義的含義(hny)了。因此，在構(gòu)思搬移過(guò)程的了。因此，在構(gòu)思搬移過(guò)程的參量時(shí)，要把參量時(shí)，要把 3 個(gè)柱子都用上。個(gè)柱子都用上。第72頁(yè)/共174頁(yè)第七十二頁(yè)，共174頁(yè)。6、定義、定義(dngy)搬移函數(shù)搬移函數(shù) move(n, A, B, C)，物理意義，物理意義是將是將 n 只盤(pán)子從只盤(pán)子從 A 經(jīng)經(jīng) B 搬到搬到 C輸出n:A to Cmove(n-1,A,C,B)move(n-1,B,A,C)move(n,A,B,C)考慮到前面已經(jīng)考慮到前面已經(jīng)研究過(guò)的研究過(guò)的(1)(2)(3)步，可以將

38、搬移步，可以將搬移過(guò)程用如下的與過(guò)程用如下的與或結(jié)點(diǎn)或結(jié)點(diǎn)(ji din)圖表示。圖表示。第73頁(yè)/共174頁(yè)第七十三頁(yè)，共174頁(yè)。這里用與或結(jié)點(diǎn)的含義是分解為這里用與或結(jié)點(diǎn)的含義是分解為(1)(2)(3)步。這步。這3步是步是相關(guān)的，相互依存的，而且是有序的，從左至右執(zhí)行。相關(guān)的，相互依存的，而且是有序的，從左至右執(zhí)行。move(n, A, B, C) 分解為分解為3步步(1)move(n-1, A, C, B)理解為將上面理解為將上面(shng min)的的n-1只盤(pán)子作只盤(pán)子作為一個(gè)整體從為一個(gè)整體從A經(jīng)經(jīng)C移至移至B；(2)輸出輸出n：A to C，理解將，理解將n號(hào)盤(pán)從號(hào)盤(pán)從A移至

39、移至C，是直接可解結(jié)點(diǎn)；，是直接可解結(jié)點(diǎn)；(3)Move(n-1, B, A, C)理解為將上面理解為將上面(shng min)的的n-1只盤(pán)子作只盤(pán)子作為一個(gè)整體從為一個(gè)整體從B經(jīng)經(jīng)A移至移至C。第74頁(yè)/共174頁(yè)第七十四頁(yè)，共174頁(yè)。這里顯然是一種遞歸定義，當(dāng)著解這里顯然是一種遞歸定義，當(dāng)著解 move(n-1, A, C, B)時(shí)又可想到，將其分解為時(shí)又可想到，將其分解為 3 步：步：第第1步：將上面的步：將上面的n-2只盤(pán)子作為一個(gè)只盤(pán)子作為一個(gè)(y )整體從整體從A經(jīng)經(jīng)B到到C，move(n-2, A, B, C)；第第2步：第步：第n-1號(hào)盤(pán)子從號(hào)盤(pán)子從A直接移至直接移至B，即

40、，即n-1:A to B；第第3步：再將上面的步：再將上面的n-2只盤(pán)子作為一個(gè)只盤(pán)子作為一個(gè)(y )整體從整體從C經(jīng)經(jīng)A移至移至B，move(n-2, C, A, B)；下面，我們還是以下面，我們還是以3只盤(pán)子為例畫(huà)出遞歸的與或圖。只盤(pán)子為例畫(huà)出遞歸的與或圖。第75頁(yè)/共174頁(yè)第七十五頁(yè)，共174頁(yè)。這個(gè)圖很象一顆倒置著的樹(shù)，結(jié)點(diǎn)這個(gè)圖很象一顆倒置著的樹(shù)，結(jié)點(diǎn)move(3, A, B, C)是樹(shù)是樹(shù)根，與結(jié)點(diǎn)是樹(shù)的分枝根，與結(jié)點(diǎn)是樹(shù)的分枝(fn zh)，葉子都是直接可解，葉子都是直接可解結(jié)點(diǎn)。結(jié)點(diǎn)。輸出1:A to C1:A to C輸出3:A to Cmove(2,A,C,B)move(

41、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: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頁(yè)/共174頁(yè)第七十六頁(yè)，共174頁(yè)。 move(3,A,B,C) move(2,A,C,B) 輸輸出出 3: A to C move(2,B,A,C) move(2,A,C,B) 調(diào)調(diào)用用 move(1,A,B,C) move(2,B,A,C) 調(diào)調(diào)用用 mo

42、ve(1,B,C,A) 返返回回 返返回回 調(diào)調(diào)用用 調(diào)調(diào)用用 返返回回 move(1,A,B,C) 輸輸出出 2: A to B move(1,C,A,B) 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 調(diào)調(diào)用用 調(diào)調(diào)用用 返返回回 返返回回 調(diào)調(diào)用用 move (1,C,A,B) move (1,A,B,C) 第77頁(yè)/共174頁(yè)第七十七頁(yè)，共174頁(yè)。 輸出輸出 3: A to C 調(diào)用調(diào)用 move(

43、1,C,A,B) 輸出：輸出：1: C to B 輸出：輸出：2: A to B move(1,C,A,B) 調(diào)用調(diào)用 move(1,A,B,C) 輸出輸出 1: A to C move(1,A,B,C) move(2,A,C,B) 調(diào)用調(diào)用 move(2,A,C,B) 調(diào)用調(diào)用 move(2,B,A,C) 調(diào)用調(diào)用 move(1,A,B,C) 輸出輸出 1: A to C 輸出：輸出：2: B to C 調(diào)用調(diào)用 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

44、 4 5 6 7 第78頁(yè)/共174頁(yè)第七十八頁(yè)，共174頁(yè)。/ */ * 程程 序：序：6_hanoi2002.cpp */ * 作作 者：者：wuwh */ * 編制編制(binzh)時(shí)間：時(shí)間：2002年年10月月13日日 */ * 主要功能：用遞歸求解主要功能：用遞歸求解Hanoi問(wèn)題問(wèn)題 */ *#include / 預(yù)編譯命令預(yù)編譯命令int step=1;/ 整型全局變量整型全局變量,預(yù)置預(yù)置1,步數(shù)步數(shù)void move(int m, char p, char q, char r);/ 聲明要用到的被調(diào)用函數(shù)聲明要用到的被調(diào)用函數(shù)void main()/ 主函數(shù)主函數(shù)/ 主程序

45、開(kāi)始主程序開(kāi)始int n;/ 整型變量整型變量,n為盤(pán)數(shù)為盤(pán)數(shù),printf( 請(qǐng)輸入盤(pán)數(shù)請(qǐng)輸入盤(pán)數(shù) n=“);/ 提示信息提示信息scanf(“/%d”),&n);/ 輸入正整數(shù)輸入正整數(shù)nprintf( 在在3根柱子上移根柱子上移%d只盤(pán)的步驟為只盤(pán)的步驟為:“,n); / 輸出提示信息輸出提示信息 move(n,a,b,c);/ 調(diào)用函數(shù)調(diào)用函數(shù) move(n,a,b,c)/ 主函數(shù)結(jié)束主函數(shù)結(jié)束第79頁(yè)/共174頁(yè)第七十九頁(yè)，共174頁(yè)。/ 以下函數(shù)是被主程序調(diào)用的函數(shù)以下函數(shù)是被主程序調(diào)用的函數(shù)/ 函數(shù)名：函數(shù)名：move/ 輸輸 入：入：m，整型變量，表示盤(pán)子數(shù)目，整型變量，表示盤(pán)

46、子數(shù)目/ p，q，r為字符型變量，表示柱子標(biāo)號(hào)為字符型變量，表示柱子標(biāo)號(hào)/ 返回值：無(wú)返回值：無(wú)void move(int m, char p, char q, char r)/ 自定義函數(shù)體開(kāi)始自定義函數(shù)體開(kāi)始if (m=1)/ 如果如果m為為1,則為直接可解結(jié)點(diǎn)則為直接可解結(jié)點(diǎn),/ 直接可解結(jié)點(diǎn)直接可解結(jié)點(diǎn),輸出移盤(pán)信息輸出移盤(pán)信息printf(%d move 1# from p to r”, step); step+;/ 步數(shù)加步數(shù)加1else/ 如果不為如果不為(b wi)1,則要調(diào)用則要調(diào)用move(m-1)move(m-1,p,r,q);/ 遞歸調(diào)用遞歸調(diào)用move(m-1)/直接

47、可解結(jié)點(diǎn)直接可解結(jié)點(diǎn),輸出移盤(pán)信息輸出移盤(pán)信息 printf(%d move %d from p to r”, step,m); step+;/ 步數(shù)加步數(shù)加1move(m-1,q,p,r);/ 遞歸調(diào)用遞歸調(diào)用move(m-1)/自定義函數(shù)體結(jié)束自定義函數(shù)體結(jié)束第80頁(yè)/共174頁(yè)第八十頁(yè)，共174頁(yè)。1111,125;123nmnnnmmmnm nmmnCmnCCCCC習(xí)題：已知表示從 個(gè)元素中取 個(gè)的組合數(shù)，又知、試畫(huà)出符合上述關(guān)系的與或結(jié)合圖；、指出哪個(gè)是直接可解結(jié)點(diǎn)；、畫(huà)出求解結(jié)點(diǎn)圖；4、寫(xiě)出遞歸程序求解組合問(wèn)題。第81頁(yè)/共174頁(yè)第八十一頁(yè)，共174頁(yè)。第82頁(yè)/共174頁(yè)第八十

48、二頁(yè)，共174頁(yè)。/ */ * 程程 序：序：6_7.cpp * / * 編制時(shí)間：編制時(shí)間：2002年年10月月28日日 * / * 主要功能：計(jì)算主要功能：計(jì)算(j sun)組和數(shù)組和數(shù)C(m,n) */ *#include / 預(yù)編譯命令預(yù)編譯命令Using namespace std;第83頁(yè)/共174頁(yè)第八十三頁(yè)，共174頁(yè)。/ 計(jì)算(j sun)C(m,n)，即從m個(gè)數(shù)中取n個(gè)數(shù)的組合數(shù)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

49、m;/ C(m,n)=C(m-1,n)+C(m-1,n-1)return C (m-1, n)+C (m-1,n-1);第84頁(yè)/共174頁(yè)第八十四頁(yè)，共174頁(yè)。int main()/ 主函數(shù)開(kāi)始主函數(shù)開(kāi)始(kish)/ 測(cè)試一些結(jié)果測(cè)試一些結(jié)果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#

50、青蛙從青蛙從 L L R R；3# 3# 青蛙從青蛙從 Y Y R R；1# 1# 青蛙從青蛙從 S S Y Y；2# 2# 青蛙從青蛙從 S S R R；1# 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頁(yè)/共174頁(yè)第九十一頁(yè)，共174頁(yè)。表一表一第92頁(yè)/共174頁(yè)第九十二頁(yè)，共174頁(yè)。 為了將過(guò)河過(guò)程描述為了將過(guò)河過(guò)程描述(mio sh)(mio sh)得更清楚，我們給出了表得更清楚，我們給出了表1 1。表中表中L1 L2 L3 L4L1 L2 L3 L4表示左岸石柱上落在

51、一起的青蛙的高度位置。表示左岸石柱上落在一起的青蛙的高度位置。L1 L1 在最上面，在最上面，L4 L4 在最下面的位置。引入這個(gè)信息就可比較容在最下面的位置。引入這個(gè)信息就可比較容易地看出對(duì)青蛙占位的約束條件。同理易地看出對(duì)青蛙占位的約束條件。同理R1 R2 R3 R4R1 R2 R3 R4也是如此。也是如此。對(duì)水中石柱對(duì)水中石柱S S，也分成兩個(gè)高度位置，也分成兩個(gè)高度位置S1 S2S1 S2。對(duì)荷葉。對(duì)荷葉Y Y無(wú)須分層，無(wú)須分層，因?yàn)樗辉试S一只青蛙落在其上。因?yàn)樗辉试S一只青蛙落在其上。t=0t=0為初始時(shí)刻，青蛙從小到為初始時(shí)刻，青蛙從小到大落在石柱大落在石柱L L上。上。t=1t

52、=1為第一步：為第一步：1#1#從從L L跳至荷葉跳至荷葉Y Y上；上；L L上只剩上只剩2# 2# 3# 4#3# 4#。T=2 T=2 為第二步；為第二步；2#2#從從L L跳至石柱跳至石柱S S上，處在上，處在S2S2位置上，位置上，L L上只剩上只剩3#3#和和4#4#。T=3T=3為第三步，為第三步，1#1#從從Y Y跳至跳至S S，將，將Y Y清空。這時(shí)你清空。這時(shí)你看，看，S S上有上有1#1#、2#2#，L L上有上有3#3#、4#4#，好象是原來(lái)在，好象是原來(lái)在L L上的上的4 4只青蛙，只青蛙，分成了上下兩部分，上面的分成了上下兩部分，上面的2 2只通過(guò)荷葉只通過(guò)荷葉y y

53、轉(zhuǎn)移到了轉(zhuǎn)移到了S S上。這一過(guò)上。這一過(guò)程是一分為二的過(guò)程。即將程是一分為二的過(guò)程。即將L L上的一隊(duì)青蛙，分解為兩個(gè)隊(duì)，每上的一隊(duì)青蛙，分解為兩個(gè)隊(duì)，每隊(duì)各二只，且將上面的二只轉(zhuǎn)移到了隊(duì)各二只，且將上面的二只轉(zhuǎn)移到了S S上。這時(shí)我們可以考慮形上。這時(shí)我們可以考慮形成兩個(gè)系統(tǒng)，一個(gè)是成兩個(gè)系統(tǒng)，一個(gè)是L L，Y Y，R R系統(tǒng)，一個(gè)是系統(tǒng)，一個(gè)是S S，Y Y，R R系統(tǒng)。前者系統(tǒng)。前者二只青蛙號(hào)大；后者二只青蛙號(hào)小。先跳號(hào)大的，再跳號(hào)小的。二只青蛙號(hào)大；后者二只青蛙號(hào)小。先跳號(hào)大的，再跳號(hào)小的。從第五步到第九步可以看出的確是這么做的。從第五步到第九步可以看出的確是這么做的。第93頁(yè)/共1

54、74頁(yè)第九十三頁(yè)，共174頁(yè)。2YRSL31第94頁(yè)/共174頁(yè)第九十四頁(yè)，共174頁(yè)。Jump(0,1)兩個(gè)系統(tǒng)之和為2*Jump(0,1)，因此有：Jump(1,1)=2*Jump(0,1)=2*2=4 第95頁(yè)/共174頁(yè)第九十五頁(yè)，共174頁(yè)?，F(xiàn)在再看現(xiàn)在再看S=2，y=1 Jump(2,1) 我們將河中的兩個(gè)石柱稱作我們將河中的兩個(gè)石柱稱作S1和和S2，荷葉叫，荷葉叫y，考慮先將考慮先將L上的青蛙的一半借助于上的青蛙的一半借助于S2和和y轉(zhuǎn)轉(zhuǎn)移移(zhuny)到到S1上，當(dāng)然是一半小號(hào)的青上，當(dāng)然是一半小號(hào)的青蛙在蛙在S1上，大的留在上，大的留在L上。上。y yLR RS1S1S2S

55、2第96頁(yè)/共174頁(yè)第九十六頁(yè)，共174頁(yè)。 1第97頁(yè)/共174頁(yè)第九十七頁(yè)，共174頁(yè)。S19. 8 2 4第98頁(yè)/共174頁(yè)第九十八頁(yè)，共174頁(yè)。LRYS2876543S1214321第99頁(yè)/共174頁(yè)第九十九頁(yè)，共174頁(yè)。LS2YR S1S2YR第100頁(yè)/共174頁(yè)第一百頁(yè)，共174頁(yè)。這樣這樣 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*J

56、ump(S-1, y)第101頁(yè)/共174頁(yè)第一百零一頁(yè)，共174頁(yè)。5. 將上述分析出來(lái)的規(guī)律寫(xiě)成遞歸形式將上述分析出來(lái)的規(guī)律寫(xiě)成遞歸形式(xngsh)的與或結(jié)點(diǎn)圖為：的與或結(jié)點(diǎn)圖為：Jump(S,y)y+1S!=0S=0Jump(S-1,y)2*Jump(S-1,y)第102頁(yè)/共174頁(yè)第一百零二頁(yè)，共174頁(yè)。舉例(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頁(yè)/共1

57、74頁(yè)第一百零三頁(yè)，共174頁(yè)。/ */ * 程程 序：序：6_5.cpp */ * 作作 者：者：wuwh */ * 編制時(shí)間：編制時(shí)間：2002年年10月月20日日 */ * 主要功能：青蛙過(guò)河主要功能：青蛙過(guò)河 */ *#include /預(yù)編譯預(yù)編譯(biny)命令命令int Jump(int, int);/聲明有被調(diào)用函數(shù)聲明有被調(diào)用函數(shù)void main()/主函數(shù)主函數(shù)/主程序開(kāi)始主程序開(kāi)始int s=0,y=0,sum=0;/整型變量整型變量,s為河中石柱數(shù)為河中石柱數(shù),y為荷葉數(shù)為荷葉數(shù)cout s;/輸入正整數(shù)輸入正整數(shù)scout y;/輸入正整數(shù)輸入正整數(shù)ysum = J

58、ump ( s , y ) ;/Jump(s,y)為被調(diào)用函數(shù)為被調(diào)用函數(shù)cout Jump( s , /輸出結(jié)果輸出結(jié)果 y )= sum endl;/主程序結(jié)束主程序結(jié)束第104頁(yè)/共174頁(yè)第一百零四頁(yè)，共174頁(yè)。/ */ * 程程 序：序：6_5.cpp */ * 作作 者：者：wuwh */ * 編制時(shí)間：編制時(shí)間：2002年年10月月20日日 */ * 主要主要(zhyo)功能：青蛙過(guò)河功能：青蛙過(guò)河(遞歸遞歸) */ *第105頁(yè)/共174頁(yè)第一百零五頁(yè)，共174頁(yè)。#include /預(yù)編譯命令預(yù)編譯命令int Jump(int, int);/聲明聲明(shngmng)有被調(diào)

59、用函數(shù)有被調(diào)用函數(shù)int main()/主函數(shù)主函數(shù) int s=0,y=0,sum=0; cout s;/輸入正整數(shù)輸入正整數(shù)s cout y;/輸入正整數(shù)輸入正整數(shù)y sum = Jump ( s , y ) ;/Jump(s,y)為被調(diào)用函數(shù)為被調(diào)用函數(shù) cout Jump( s , /輸出結(jié)果輸出結(jié)果 y )= sum =rl=rA sort(l,r)數(shù)據(jù)在al,.,ar中數(shù)據(jù)在al,.,ar中B什么也不做什么也不做ClrD分區(qū)處理分區(qū)處理Fsort(m+1,r)Esort(l,m-1)第111頁(yè)/共174頁(yè)第一百一十一頁(yè)，共174頁(yè)。第112頁(yè)/共174頁(yè)第一百一十二頁(yè)，共174頁(yè)。

60、分區(qū)處理：分區(qū)處理：1、讓、讓 k=a z 2、將、將 k 放在放在 a m 3、使、使 az, az+1 , , a m-1 = a m 4、使、使 a m = y，則什么也不做。這是直，則什么也不做。這是直接可解結(jié)點(diǎn)接可解結(jié)點(diǎn)(ji din)。C 結(jié)點(diǎn)結(jié)點(diǎn)(ji din)是在是在 z y 情況下情況下 A 結(jié)點(diǎn)結(jié)點(diǎn)(ji din)的解。的解。C 是一個(gè)與結(jié)點(diǎn)是一個(gè)與結(jié)點(diǎn)(ji din)。要對(duì)。要對(duì) C 求解需分解為三步。求解需分解為三步。依次為：依次為：第113頁(yè)/共174頁(yè)第一百一十三頁(yè)，共174頁(yè)。1、先解、先解 D 結(jié)點(diǎn)，結(jié)點(diǎn)，D 結(jié)點(diǎn)是一個(gè)直接可解結(jié)點(diǎn)，功能是進(jìn)行結(jié)點(diǎn)是一個(gè)直接可解

61、結(jié)點(diǎn)，功能是進(jìn)行所謂的分區(qū)處理，規(guī)定這一步所謂的分區(qū)處理，規(guī)定這一步(y b)要做的事情是要做的事情是（1）將）將 a z 中的元素放到它應(yīng)該在的位置上，比如中的元素放到它應(yīng)該在的位置上，比如 m 位位置。這時(shí)置。這時(shí) a m a z ；（2）讓下標(biāo)從）讓下標(biāo)從 z 到到 m-1 的數(shù)組元素小于等的數(shù)組元素小于等 a m ；（3）讓下標(biāo)從）讓下標(biāo)從 m+1 到到 y 的數(shù)組元素大于的數(shù)組元素大于a m ；比如比如 a 數(shù)組中數(shù)組中 a z = 5，經(jīng)分組處理后，經(jīng)分組處理后，5 送至送至 a 4 。5 到到位后，其左邊位后，其左邊 a 0 a 3 的值都小于的值都小于 5；其右邊；其右邊 a

62、5 , a 6 大于大于 5。（見(jiàn)下圖）（見(jiàn)下圖）第114頁(yè)/共174頁(yè)第一百一十四頁(yè)，共174頁(yè)。azyam下標(biāo)下標(biāo)(xi bio)：下標(biāo)下標(biāo)(xi bio)：zm-1ym+1第115頁(yè)/共174頁(yè)第一百一十五頁(yè)，共174頁(yè)。2、再解、再解 E 結(jié)點(diǎn)，這時(shí)要處理結(jié)點(diǎn)，這時(shí)要處理(chl)的是的是 a 0 a 3 ；3、再解、再解 F 結(jié)點(diǎn)，處理結(jié)點(diǎn)，處理(chl)a 5 ,a 6 。下面按照這種思路構(gòu)思一個(gè)快速排序的程序框圖。下面按照這種思路構(gòu)思一個(gè)快速排序的程序框圖。void sort( int array , int zz, int yy )int z, y, i , k ;第116頁(yè)/

63、共174頁(yè)第一百一十六頁(yè)，共174頁(yè)。 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 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 ;

64、 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頁(yè)/共174頁(yè)第一百一十七頁(yè)，共174頁(yè)。下面舉例說(shuō)明排序下面舉例說(shuō)明排序(pi x)(pi x)過(guò)程過(guò)程圖圖1 a數(shù)組中有數(shù)組中有7個(gè)元素個(gè)元素(yun s)待排序待排序1 讓讓 k = a z = a 0 = 5zy圖圖 1k第118頁(yè)/共174頁(yè)第一百一十八頁(yè)，共174頁(yè)。2 進(jìn)入直到型循環(huán)進(jìn)入直到型循環(huán)執(zhí)行（執(zhí)行（1）ay=a6=4 不滿足不滿足(mnz)當(dāng)循環(huán)條件，當(dāng)循環(huán)條件，

65、y不動(dòng)。不動(dòng)。執(zhí)行（執(zhí)行（2）zy，做兩件事：，做兩件事：a z = a y ，即，即a 0 = a 6 = 4，z = z +1 = 0+1 = 1，見(jiàn)圖，見(jiàn)圖2zy 圖圖 2k第119頁(yè)/共174頁(yè)第一百一十九頁(yè)，共174頁(yè)。執(zhí)行（執(zhí)行（3）圖）圖2中的中的a1k滿足滿足(mnz)當(dāng)循環(huán)的條件，當(dāng)循環(huán)的條件，y = y-1 = 6-1 = 5見(jiàn)圖見(jiàn)圖5，之后退出當(dāng)循環(huán)，因?yàn)?，之后退出?dāng)循環(huán)，因?yàn)?a y = 3kzy圖圖 5k第122頁(yè)/共174頁(yè)第一百二十二頁(yè)，共174頁(yè)。執(zhí)行執(zhí)行(zhxng)（2）a z =a y ，并讓，并讓 z = z+1=3，見(jiàn)圖，見(jiàn)圖6 zy圖圖 6k第123

66、頁(yè)/共174頁(yè)第一百二十三頁(yè)，共174頁(yè)。執(zhí)行執(zhí)行(zhxng)（3）由于）由于a3=1k，退出循環(huán)。見(jiàn)圖，退出循環(huán)。見(jiàn)圖7 zy圖圖 7k第124頁(yè)/共174頁(yè)第一百二十四頁(yè)，共174頁(yè)。執(zhí)行（執(zhí)行（4）az=ay，a5=7。見(jiàn)圖。見(jiàn)圖8 這時(shí)仍然這時(shí)仍然 zk，讓，讓 y = y-1 = 4。見(jiàn)圖。見(jiàn)圖9zy圖圖 9k第126頁(yè)/共174頁(yè)第一百二十六頁(yè)，共174頁(yè)。之后，之后，z = y，退出直到型循環(huán)，做，退出直到型循環(huán)，做 a z = k，z = 4， a 4 = 5，這是，這是 5 的最終位置，的最終位置，5 將整個(gè)將整個(gè)(zhngg)數(shù)據(jù)分成數(shù)據(jù)分成左右兩個(gè)集合，見(jiàn)圖左右兩個(gè)集合，見(jiàn)圖10。zy圖圖 10左左右右k第127頁(yè)/共174頁(yè)第一百二十七頁(yè)，共174頁(yè)。用上述思路去排左邊的部分用上述思路去排左邊的部分(b fen)從從 z = 0 到到 y = 3，見(jiàn)圖，見(jiàn)圖11。讓。讓 k = a z = a 0 = 4，然后進(jìn)，然后進(jìn)到直到型循環(huán)，到直到型循環(huán)，執(zhí)行（執(zhí)行（1）a y = 1k，不滿足當(dāng)循環(huán)的條件，不滿足當(dāng)循環(huán)的條件，y不動(dòng)。不動(dòng)。執(zhí)行（執(zhí)行（2）a z =