《算法語言與數(shù)據(jù)結(jié)構(gòu)課件》由會員分享，可在線閱讀，更多相關(guān)《算法語言與數(shù)據(jù)結(jié)構(gòu)課件（174頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第5章 函數(shù)數(shù) / */ * 程 序：6_3.cpp（驗證素數(shù)程序） */ * 作 者：wuwh */ * 編制時間：2002年10月20日 */ * 主要功能：可驗證某數(shù)是否為素數(shù) */ *#include / 預(yù)編譯命令#include / 預(yù)編譯命令int checkprime( int );/ 子函數(shù)聲明int main()/ 主函數(shù)int a=0;/ 定義整型變量，初始化為0cout a; / 鍵盤輸入一個整數(shù)/ 用實參a調(diào)用子函數(shù)，該子函數(shù)的/ 返回值作為if語句的分支條件if ( checkprime(a) ) / checkprime(a)為1cout a 是素數(shù) endl;e

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

3、return 1;/ b不能被不能被k整除，則返回整除，則返回1第第5章章 函數(shù)函數(shù)第第5章章 函數(shù)函數(shù) bool checkprime( int b ) / 子函數(shù)子函數(shù) int k=0; 形式參數(shù)形式參數(shù)for ( k=2; k=sqrt( (double) b ); k=K+1 ) if ( b % k = 0 ) return 0; return 1; / b不能被不能被k整除，則返回整除，則返回1 / 說明說明 b 是質(zhì)數(shù)是質(zhì)數(shù)第第5章章 函數(shù)函數(shù) 講這一程序的目的：講這一程序的目的：如何定義一個函數(shù)如何定義一個函數(shù)主函數(shù)怎樣調(diào)用子函數(shù)主函數(shù)怎樣調(diào)用子函數(shù)實在參數(shù)和形式參數(shù)實在參數(shù)和

4、形式參數(shù)返回值是什么意思返回值是什么意思第第5章章 函數(shù)函數(shù)第第5章章 函數(shù)函數(shù) 1nkxx4444441 2 3 4 5 6 p o w e r ( , )li li i=1,2,n l = k 4441 , 2, 61SOP( , )power( , )mim li l 例例: int power(int p, int n)power 為函數(shù)名，要以英文字母開頭。為函數(shù)名，要以英文字母開頭。int 是函數(shù)值的數(shù)據(jù)類型，這里是是函數(shù)值的數(shù)據(jù)類型，這里是int（整型）。（整型）。(int p, int n) 括號中的括號中的 p, n為函數(shù)的形式參數(shù)，形式為函數(shù)的形式參數(shù)，形式參數(shù)也要定義其數(shù)

5、據(jù)類型。參數(shù)也要定義其數(shù)據(jù)類型。 ()1、形式參數(shù)形式參數(shù)是在定義函數(shù)時放在函數(shù)名后括號中的參數(shù)。在是在定義函數(shù)時放在函數(shù)名后括號中的參數(shù)。在未進(jìn)行函數(shù)調(diào)用時，并不對形式參數(shù)分配內(nèi)存單元。在發(fā)未進(jìn)行函數(shù)調(diào)用時，并不對形式參數(shù)分配內(nèi)存單元。在發(fā)生函數(shù)調(diào)用時，立刻給形式參數(shù)分配內(nèi)存單元。調(diào)用結(jié)束生函數(shù)調(diào)用時，立刻給形式參數(shù)分配內(nèi)存單元。調(diào)用結(jié)束后，釋放掉行參所占的內(nèi)存單元。后，釋放掉行參所占的內(nèi)存單元。2、因此，形參變量屬于局部變量，其作用域在它所在的函數(shù)、因此，形參變量屬于局部變量，其作用域在它所在的函數(shù)體內(nèi)。體內(nèi)。3、在定義函數(shù)的時候，必須指定形參變量的類型，如下所示、在定義函數(shù)的時候，必須指

6、定形參變量的類型，如下所示int power(int p, int n) / 函數(shù)體函數(shù)體 c 執(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 = 354 i=5: sum = sum + power(i,l) = 354 + 625 = 979 i=6: sum = s

7、um + 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): 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í)行 powe

8、r(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)用 遞遞 推推 定義數(shù)組 fish6，并初始化為 1； 定義循環(huán)控制變量 i，并初始化為 0。 輸出計算結(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) fi

9、shi = fishi+1*5/4+1; 該圖可分為三部分該圖可分為三部分(1) 是說明部分：包含定義數(shù)組是說明部分：包含定義數(shù)組 fish6，并初始化為，并初始化為 1 和和定義循環(huán)控制變量定義循環(huán)控制變量 i，并初始化為，并初始化為 0。(2) 是是 do.while 直到型循環(huán)，其循環(huán)體又含兩塊：直到型循環(huán)，其循環(huán)體又含兩塊：(2).1 是枚舉過程中的是枚舉過程中的 fish5 的初值設(shè)置，一開始的初值設(shè)置，一開始 fish5=1+5; 以后每次增以后每次增 5。(2).2 是一個是一個 for 循環(huán)，循環(huán)，i 的初值為的初值為 4，終值為，終值為 1，步長，步長為為 -1，該循環(huán)的循環(huán)

10、體是一個分支語句，該循環(huán)的循環(huán)體是一個分支語句， 如果如果 fishi+1不能被不能被 4 整除，則跳出整除，則跳出 for 循環(huán)（使用循環(huán)（使用 break 語句）語句）; 否則，從否則，從 fishi+1 算出算出 fishi。遞歸算法在可計算性理論中占有重要地位，它是遞歸算法在可計算性理論中占有重要地位，它是算法設(shè)計的有力工具，對于拓展編程思路非常有用。算法設(shè)計的有力工具，對于拓展編程思路非常有用。就遞歸算法而言并不涉及高深數(shù)學(xué)知識，只不過初就遞歸算法而言并不涉及高深數(shù)學(xué)知識，只不過初學(xué)者要建立起遞歸概念不十分容易。學(xué)者要建立起遞歸概念不十分容易。我們先從一個最簡單的例子導(dǎo)入。我們先從一

11、個最簡單的例子導(dǎo)入。遞歸及其實現(xiàn)遞歸及其實現(xiàn)用遞歸算法求用遞歸算法求n!定義：函數(shù)定義：函數(shù) fact( n ) = n!fact( n-1 ) = ( n-1 )!則有則有 fact( n ) = n fact( n-1 )已知已知 fact( 1 ) = 1為了表述得直觀清晰，我們定義兩個結(jié)點：或結(jié)點和為了表述得直觀清晰，我們定義兩個結(jié)點：或結(jié)點和與結(jié)點。與結(jié)點。圖示的直觀性與思維助力。圖示的直觀性與思維助力。1、或結(jié)點、或結(jié)點,BZ trueCZfalseA（真）（假） A 條條件件Z 條條件件!Z B C A為為“或結(jié)點或結(jié)點”，A依不同條件會有兩種不同的取值依不同條件會有兩種不同的取

12、值, B 或或C。結(jié)點用。結(jié)點用 表示。表示。 如果有多于如果有多于2 種取值，可用下圖：種取值，可用下圖： Z1 Z2 Zn B C G A 條件為條件為Z1,Z2,Zn,Z1,Z2,Zn,取值為取值為 B B 或或C,C,或或G G2、與結(jié)點、與結(jié)點與結(jié)點要涂實心，相與結(jié)點要涂實心，相關(guān)聯(lián)的關(guān)聯(lián)的B與與C之間要用之間要用弧線連起來?；【€連起來。A為與結(jié)點，為與結(jié)點，A的最終取值為的最終取值為C結(jié)點的值，但為結(jié)點的值，但為了求得了求得C的值，得先求出的值，得先求出B結(jié)點的值，結(jié)點的值，C是是B的的函數(shù)。函數(shù)。ABC仍以求仍以求 n! 為例畫出如下與或圖為例畫出如下與或圖A 為或結(jié)點；為或結(jié)點

13、；B 為直接可解結(jié)點，值為為直接可解結(jié)點，值為 1；C 為與結(jié)點，當(dāng)為與結(jié)點，當(dāng) n1 時，時，A 的取值即的取值即 C 的值，而的值，而 C 的值即的值即 E 的值，為了求得的值，為了求得 E 的值，需要先求出的值，需要先求出 D 的值。的值。D 值值 fact( n-1 ) 乘以乘以 n 即為即為 E 的值。的值。A fact(n)Bfact(1)=1Cn1n=1Dfact(n-1)En*fact(n-1)與結(jié)點可能有多個相關(guān)聯(lián)的點，這時可描述為下圖與結(jié)點可能有多個相關(guān)聯(lián)的點，這時可描述為下圖A 結(jié)點的值最終為結(jié)點的值最終為 D 的值，但為了求的值，但為了求 D 需先求需先求 B 和和 C

14、。從圖上看。從圖上看, 先求左邊的點才能求最右邊的點的先求左邊的點才能求最右邊的點的值，我們約定最右邊值，我們約定最右邊 D 點的值就是點的值就是 A 結(jié)點的值。結(jié)點的值。ABDC下面我們以下面我們以3！為例來畫與或結(jié)點圖，目的是體！為例來畫與或結(jié)點圖，目的是體會遞歸的含義。會遞歸的含義。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下面畫出了調(diào)用和返回的遞歸示意圖下面畫出了調(diào)用和返回的遞歸示意圖 Bfact(2)fact(2)=2*f

15、act(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)用從圖可以想象：從圖可以想象：欲求欲求 fact( 3 )，先要求，先要求 fact( 2 )；要求；要求 fact( 2 ) 先先求求 fact( 1 )。就象剝一顆圓白菜，從外向里，一層層。就象剝一顆圓白菜，從外向里，一層層剝下來，到了菜心，遇到剝下來，到了菜心，遇到 1 的階乘，其值為的階乘，其值為1，到達(dá)，到達(dá)了遞歸的邊界。然后再用了遞歸的邊界。然后再用 fact( n )=n

16、*fact( n-1 ) 這個這個普遍公式，從里向外倒推回去得到普遍公式，從里向外倒推回去得到 fact( n ) 的值。的值。為了把這個問題說得再透徹一點。我們畫了如下為了把這個問題說得再透徹一點。我們畫了如下的流程圖：的流程圖： 31 fact(3) 真真 假假 調(diào)調(diào)用用 fact(2) 計計算算 3*fact(2) fact(2) fact(1) 21 真真 假假 調(diào)調(diào)用用 fact(1) 計計算算 2*fact(1) 11 真真 假假 fact(1) 1 返返回回 返返回回 為了形象地描述遞歸過程，將上圖改畫成下圖為了形象地描述遞歸過程，將上圖改畫成下圖 fact(3) 真真 假假 3

17、=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 返返回回 在這個圖中在這個圖中“內(nèi)層內(nèi)層”與與“外層外層”有著相同的結(jié)構(gòu)。有著相同的結(jié)構(gòu)。它們之間它們之間“你中有我，我中有你你中有我，我中有你”，呈現(xiàn)相互依存，呈現(xiàn)相互依存的關(guān)系。的關(guān)系。為了進(jìn)一步講清遞歸的概念，將遞歸與遞推做一比為了進(jìn)一步講清遞歸的概念，將遞歸與遞推做一比較。仍以求階乘為例。較。仍以求階乘為例。遞推是從已知的初始條件出發(fā)，逐次去求所需要的遞推是從已知的初始條件出發(fā)

18、，逐次去求所需要的階乘值。階乘值。如求如求 3！初始條件初始條件 fact( 1 ) = 1fact( 2 ) = 2 * fact( 1 ) = 2fact( 3 ) = 3 * fact( 2 ) = 6這相當(dāng)于從菜心這相當(dāng)于從菜心“推到推到”外層。而遞歸算法的出外層。而遞歸算法的出發(fā)點不放在初始條件上，而放在求解的目標(biāo)上，從發(fā)點不放在初始條件上，而放在求解的目標(biāo)上，從所求的未知項出發(fā)逐次調(diào)用本身的求解過程，直到所求的未知項出發(fā)逐次調(diào)用本身的求解過程，直到遞歸的邊界（即初始條件）。就本例而言，讀者會遞歸的邊界（即初始條件）。就本例而言，讀者會認(rèn)為遞歸算法可能是多余的，費力而不討好。但許認(rèn)為

19、遞歸算法可能是多余的，費力而不討好。但許多實際問題不可能或不容易找到顯而易見的遞推關(guān)多實際問題不可能或不容易找到顯而易見的遞推關(guān)系，這時遞歸算法就表現(xiàn)出了明顯的優(yōu)越性。下面系，這時遞歸算法就表現(xiàn)出了明顯的優(yōu)越性。下面我們將會看到，遞歸算法比較符合人的思維方式，我們將會看到，遞歸算法比較符合人的思維方式，邏輯性強(qiáng)，可將問題描述得簡單扼要，具有良好的邏輯性強(qiáng)，可將問題描述得簡單扼要，具有良好的可讀性，易于理解，許多看來相當(dāng)復(fù)雜，或難以下可讀性，易于理解，許多看來相當(dāng)復(fù)雜，或難以下手的問題，如果能夠使用遞歸算法就會使問題變得手的問題，如果能夠使用遞歸算法就會使問題變得易于處理。下面舉一個盡人皆知的例

20、子哈諾（易于處理。下面舉一個盡人皆知的例子哈諾（Hanoi）塔問題。塔問題。故事：故事：相傳在古代印度的相傳在古代印度的 Bramah 廟中，有位僧人整天把廟中，有位僧人整天把三根柱子上的金盤倒來倒去，原來他是想把三根柱子上的金盤倒來倒去，原來他是想把64個一個一個比一個小的金盤從一根柱子上移到另一根柱子上個比一個小的金盤從一根柱子上移到另一根柱子上去。移動過程中恪守下述規(guī)則：每次只允許移動一去。移動過程中恪守下述規(guī)則：每次只允許移動一只盤，且大盤不得落在小盤上面。有人會覺得這很只盤，且大盤不得落在小盤上面。有人會覺得這很簡單，真的動手移盤就會發(fā)現(xiàn)，如以每秒移動一只簡單，真的動手移盤就會發(fā)現(xiàn)，

21、如以每秒移動一只盤子的話，按照上述規(guī)則將盤子的話，按照上述規(guī)則將64只盤子從一個柱子移只盤子從一個柱子移至另一個柱子上，所需時間約為至另一個柱子上，所需時間約為5800億年。億年。 怎樣編寫這種程序？思路上還是先從最簡單的情況分怎樣編寫這種程序？思路上還是先從最簡單的情況分析起，搬一搬看，慢慢理出思路。析起，搬一搬看，慢慢理出思路。1、在、在A柱上只有一只盤子，假定盤號為柱上只有一只盤子，假定盤號為1，這時只，這時只需將該盤從需將該盤從A搬至搬至C，一次完成，記為，一次完成，記為move 1 from A to C (演示演示)ABC12、在、在A柱上有二只盤子，柱上有二只盤子，1為小盤，為小

22、盤，2為大盤。為大盤。第（第（1）步將）步將1號盤從號盤從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;3、在、在A柱上有柱上有3只盤子，從小到大分別為只盤子，從小到大分別為1號，號，2號，號，3號號第（第（1）步）步 將將1號盤和號盤和2號盤視為一個整體；先將二者作號盤視為一個整體；先將二者作為整體從為整體從A移

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

24、做完了不言自明。所謂借助是什么意思，等這件事做完了不言自明。move (3, A, B, C)move (2, A, C, B)move (1, A, B, C)move (2, B, A, C)ABC213演示：移動演示：移動3 3個個盤子盤子的分解的分解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, C)move (2, B, A, C)move (1, B, C, A)move (1, B, A, C)move (1, A, B, C)A

25、BC2134、從題目的約束條件看，大盤上可以隨便摞小、從題目的約束條件看，大盤上可以隨便摞小盤，相反則不允許。在將盤，相反則不允許。在將1號和號和2號盤當(dāng)整體從號盤當(dāng)整體從A移至移至B的過程中的過程中 move(2, A, C, B) 實際上是分實際上是分解為以下三步解為以下三步第（第（1）.1步：步：move 1 form A to C;第（第（1）.2步：步：move 2 form A to B;第（第（1）.3步：步：move 1 form C to B;經(jīng)過以上步驟，將經(jīng)過以上步驟，將 1 號和號和 2 號盤作為整體號盤作為整體從從 A 移至移至 B，為，為 3 號盤從號盤從 A 移至

26、移至 C 創(chuàng)造了條創(chuàng)造了條件。同樣，件。同樣，3號盤一旦到了號盤一旦到了 C，就要考慮如何，就要考慮如何實現(xiàn)將實現(xiàn)將 1 號和號和 2 號盤當(dāng)整體從號盤當(dāng)整體從 B 移至移至 C 的過的過程了。實際上程了。實際上 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;5、看、看 move(2, A, C, B) 是說要將是說要將 2 只盤子從只盤子從 A 搬至搬至 B，但沒有，但沒有 C 是不行的，

27、因為第（是不行的，因為第（1）.1步就要將步就要將 1 盤從盤從 A 移到移到 C，給，給 2 盤創(chuàng)造條件盤創(chuàng)造條件從從 A 移至移至 B，然后再把，然后再把 1 盤從盤從 C 移至移至 B?？?。看到這里就能明白借助到這里就能明白借助 C 的含義了。因此，在的含義了。因此，在構(gòu)思搬移過程的參量時，要把構(gòu)思搬移過程的參量時，要把 3 個柱子都用上。個柱子都用上。6、定義搬移函數(shù)、定義搬移函數(shù) move(n, A, B, C)，物理意義是，物理意義是將將 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

28、,B,C)考慮到前面已考慮到前面已經(jīng)研究過的經(jīng)研究過的(1)(2)(3)步，可步，可以將搬移過程以將搬移過程用如下的與或用如下的與或結(jié)點圖表示。結(jié)點圖表示。這里用與或結(jié)點的含義是分解為這里用與或結(jié)點的含義是分解為(1)(2)(3)步。這步。這3步是相關(guān)的，相互依存的，而且是有序的，從左至步是相關(guān)的，相互依存的，而且是有序的，從左至右執(zhí)行。右執(zhí)行。move(n, A, B, C) 分解為分解為3步步(1)move(n-1, A, C, B)理解為將上面的理解為將上面的n-1只盤子作為一只盤子作為一個整體從個整體從A經(jīng)經(jīng)C移至移至B；(2)輸出輸出n：A to C，理解將，理解將n號盤從號盤從A移

29、至移至C，是直接可，是直接可解結(jié)點；解結(jié)點；(3)Move(n-1, B, A, C)理解為將上面的理解為將上面的n-1只盤子作為一只盤子作為一個整體從個整體從B經(jīng)經(jīng)A移至移至C。這里顯然是一種遞歸定義，當(dāng)著解這里顯然是一種遞歸定義，當(dāng)著解 move(n-1, A, C, B)時又可想到，將其分解為時又可想到，將其分解為 3 步：步：第第1步：將上面的步：將上面的n-2只盤子作為一個整體從只盤子作為一個整體從A經(jīng)經(jīng)B到到C，move(n-2, A, B, C)；第第2步：第步：第n-1號盤子從號盤子從A直接移至直接移至B，即，即n-1:A to B；第第3步：再將上面的步：再將上面的n-2只盤

30、子作為一個整體從只盤子作為一個整體從C經(jīng)經(jīng)A移至移至B，move(n-2, C, A, B)；下面，我們還是以下面，我們還是以3只盤子為例畫出遞歸的與或圖。只盤子為例畫出遞歸的與或圖。這個圖很象一顆倒置著的樹，結(jié)點這個圖很象一顆倒置著的樹，結(jié)點move(3, A, B, C)是樹是樹根，與結(jié)點是樹的分枝，葉子都是直接可解結(jié)點。根，與結(jié)點是樹的分枝，葉子都是直接可解結(jié)點。輸出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

31、: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) 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)用用 move(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

32、,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) 輸出輸出 3: A to C 調(diào)用調(diào)用 move(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

33、,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 4 5 6 7 / */ * 程程 序：序：6_hanoi2002.cpp */ * 作作 者：者：wuwh */ * 編制時間：編制時間：2002年年10月月13日日 */ * 主要功能：用遞歸求解主要功能：用遞歸求解Ha

34、noi問題問題 */ *#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ù)/ 主程序開始主程序開始int n;/ 整型變量整型變量,n為盤數(shù)為盤數(shù),printf( 請輸入盤數(shù)請輸入盤數(shù) n=“);/ 提示信息提示信息scanf(“/%d”),&n);/ 輸入正整數(shù)輸入正整數(shù)nprintf( 在在3根柱子上移根柱子上移%d只盤的步驟為只盤的步驟為:“,n); / 輸

35、出提示信息輸出提示信息 move(n,a,b,c);/ 調(diào)用函數(shù)調(diào)用函數(shù) move(n,a,b,c)/ 主函數(shù)結(jié)束主函數(shù)結(jié)束/ 以下函數(shù)是被主程序調(diào)用的函數(shù)以下函數(shù)是被主程序調(diào)用的函數(shù)/ 函數(shù)名：函數(shù)名：move/ 輸輸 入：入：m，整型變量，表示盤子數(shù)目，整型變量，表示盤子數(shù)目/ p，q，r為字符型變量，表示柱子標(biāo)號為字符型變量，表示柱子標(biāo)號/ 返回值：無返回值：無void move(int m, char p, char q, char r)/ 自定義函數(shù)體開始自定義函數(shù)體開始if (m=1)/ 如果如果m為為1,則為直接可解結(jié)點則為直接可解結(jié)點,/ 直接可解結(jié)點直接可解結(jié)點,輸出移盤信息

36、輸出移盤信息printf(%d move 1# from p to r”, step); step+;/ 步數(shù)加步數(shù)加1else/ 如果不為如果不為1,則要調(diào)用則要調(diào)用move(m-1)move(m-1,p,r,q);/ 遞歸調(diào)用遞歸調(diào)用move(m-1)/直接可解結(jié)點直接可解結(jié)點,輸出移盤信息輸出移盤信息 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é)束1111,125;123nmnnnmmmnm nmmnCmnCCCCC習(xí)

37、題：已知表示從 個元素中取 個的組合數(shù)，又知、試畫出符合上述關(guān)系的與或結(jié)合圖；、指出哪個是直接可解結(jié)點；、畫出求解結(jié)點圖；4、寫出遞歸程序求解組合問題。/ */ * 程程 序：序：6_7.cpp * / * 編制時間：編制時間：2002年年10月月28日日 * / * 主要功能：計算組和數(shù)主要功能：計算組和數(shù)C(m,n) */ *#include / 預(yù)編譯命令預(yù)編譯命令Using namespace std;int main()/ 主函數(shù)開始主函數(shù)開始/ 測試一些結(jié)果測試一些結(jié)果cout C(6,0)= Cmn(6,0) endl;cout C(6,1)= Cmn(6,1) endl;cou

38、t 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# 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#表一表一 為了將過河過程描述得更清楚，我們給出了表

39、為了將過河過程描述得更清楚，我們給出了表1 1。表。表中中L1 L2 L3 L4L1 L2 L3 L4表示左岸石柱上落在一起的青蛙的高度位置。表示左岸石柱上落在一起的青蛙的高度位置。L1 L1 在最上面，在最上面，L4 L4 在最下面的位置。引入這個信息就可比在最下面的位置。引入這個信息就可比較容易地看出對青蛙占位的約束條件。同理較容易地看出對青蛙占位的約束條件。同理R1 R2 R3 R4R1 R2 R3 R4也也是如此。對水中石柱是如此。對水中石柱S S，也分成兩個高度位置，也分成兩個高度位置S1 S2S1 S2。對荷。對荷葉葉Y Y無須分層，因為它只允許一只青蛙落在其上。無須分層，因為它只

40、允許一只青蛙落在其上。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跳跳至石柱至石柱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#，好象是原來在，好象是原

41、來在L L上的上的4 4只青蛙，分成了上下兩部分，上只青蛙，分成了上下兩部分，上面的面的2 2只通過荷葉只通過荷葉y y轉(zhuǎn)移到了轉(zhuǎn)移到了S S上。這一過程是一分為二的過上。這一過程是一分為二的過程。即將程。即將L L上的一隊青蛙，分解為兩個隊，每隊各二只，且上的一隊青蛙，分解為兩個隊，每隊各二只，且將上面的二只轉(zhuǎn)移到了將上面的二只轉(zhuǎn)移到了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)。前者二只青蛙號大；后者二只青蛙號小。先跳號大的，再跳號小的。青蛙號大；后者二只青蛙號小

42、。先跳號大的，再跳號小的。從第五步到第九步可以看出的確是這么做的。從第五步到第九步可以看出的確是這么做的。 2YRSL31現(xiàn)在再看現(xiàn)在再看S=2，y=1 Jump(2,1) 我們將河中的兩個石柱稱作我們將河中的兩個石柱稱作S1和和S2，荷葉叫，荷葉叫y，考慮先，考慮先將將L上的青蛙的一半借助于上的青蛙的一半借助于S2和和y轉(zhuǎn)移到轉(zhuǎn)移到S1上，當(dāng)然是上，當(dāng)然是一半小號的青蛙在一半小號的青蛙在S1上，大上，大的留在的留在L上。上。y yLR RS1S1S2S2LRYS2876543S1214321這樣這樣 L S1 S2 y R 系統(tǒng)分解為系統(tǒng)分解為 ： （L S2 y R 系統(tǒng)）系統(tǒng)） + （S

43、1 S2 y R 系統(tǒng)）系統(tǒng)）= 2 * （L S2 y R 系統(tǒng)）系統(tǒng)）= 2 * Jump(1,1)用歸納法用歸納法Jump(S, y)=2*Jump(S-1, y)5. 將上述分析出來的規(guī)律寫成遞歸形式的與或結(jié)點圖為：將上述分析出來的規(guī)律寫成遞歸形式的與或結(jié)點圖為：Jump(S,y)y+1S!=0S=0Jump(S-1,y)2*Jump(S-1,y)舉例：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)40

44、SJumpy/ */ * 程程 序：序：6_5.cpp */ * 作作 者：者：wuwh */ * 編制時間：編制時間：2002年年10月月20日日 */ * 主要功能：青蛙過河主要功能：青蛙過河 */ *#include /預(yù)編譯命令預(yù)編譯命令int Jump(int, int);/聲明有被調(diào)用函數(shù)聲明有被調(diào)用函數(shù)void main()/主函數(shù)主函數(shù)/主程序開始主程序開始int s=0,y=0,sum=0;/整型變量整型變量,s為河中石柱數(shù)為河中石柱數(shù),y為荷葉數(shù)為荷葉數(shù)cout s;/輸入正整數(shù)輸入正整數(shù)scout y;/輸入正整數(shù)輸入正整數(shù)ysum = Jump ( s , y ) ;/

45、Jump(s,y)為被調(diào)用函數(shù)為被調(diào)用函數(shù)cout Jump( s , /輸出結(jié)果輸出結(jié)果 y )= sum endl;/主程序結(jié)束主程序結(jié)束/ */ * 程程 序：序：6_5.cpp */ * 作作 者：者：wuwh */ * 編制時間：編制時間：2002年年10月月20日日 */ * 主要功能：青蛙過河主要功能：青蛙過河(遞歸遞歸) */ *#include /預(yù)編譯命令預(yù)編譯命令int Jump(int, int);/聲明有被調(diào)用函數(shù)聲明有被調(diào)用函數(shù)int main()/主函數(shù)主函數(shù) int s=0,y=0,sum=0; cout s;/輸入正整數(shù)輸入正整數(shù)s cout y;/輸入正整數(shù)

46、輸入正整數(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) 分區(qū)處理：分區(qū)處理：1、讓、讓 k=a z 2、將、將 k 放在放在 a m 3、使、使 az, az+1 , , a m-1 = a m 4、使、使 a m = y，則什么也不做。這是直接可，則什么也不做。這是直接可解結(jié)點。解結(jié)點。C 結(jié)點是在結(jié)點是在

47、z y 情況下情況下 A 結(jié)點的解。結(jié)點的解。C 是一個與結(jié)是一個與結(jié)點。要對點。要對 C 求解需分解為三步。依次為：求解需分解為三步。依次為：1、先解、先解 D 結(jié)點，結(jié)點，D 結(jié)點是一個直接可解結(jié)點，功能是結(jié)點是一個直接可解結(jié)點，功能是進(jìn)行所謂的分區(qū)處理，規(guī)定這一步要做的事情是進(jìn)行所謂的分區(qū)處理，規(guī)定這一步要做的事情是 （1）將）將 a z 中的元素放到它應(yīng)該在的位置上，比中的元素放到它應(yīng)該在的位置上，比如如 m 位置。這時位置。這時 a m a z ； （2）讓下標(biāo)從）讓下標(biāo)從 z 到到 m-1 的數(shù)組元素小于等的數(shù)組元素小于等 a m ； （3）讓下標(biāo)從）讓下標(biāo)從 m+1 到到 y 的

48、數(shù)組元素大于的數(shù)組元素大于a m ；比如比如 a 數(shù)組中數(shù)組中 a z = 5，經(jīng)分組處理后，經(jīng)分組處理后，5 送至送至 a 4 。5 到位后，其左邊到位后，其左邊 a 0 a 3 的值都小于的值都小于 5；其右；其右邊邊 a 5 , a 6 大于大于 5。（見下圖）（見下圖）azyam下標(biāo)：下標(biāo)：下標(biāo)：下標(biāo)：zm-1ym+12、再解、再解 E 結(jié)點，這時要處理的是結(jié)點，這時要處理的是 a 0 a 3 ；3、再解、再解 F 結(jié)點，處理結(jié)點，處理a 5 ,a 6 。下面按照這種思路構(gòu)思一個快速排序的程序框圖。下面按照這種思路構(gòu)思一個快速排序的程序框圖。void sort( int array ,

49、 int zz, int yy )int z, y, i , k ; 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

50、= 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 ); 下面舉例說明排序過程下面舉例說明排序過程圖圖1 a數(shù)組中有數(shù)組中有7個元素待排序個元素待排序1 讓讓 k = a z = a 0 = 5zy圖圖 1k2 進(jìn)入直到型循環(huán)進(jìn)入直到型循環(huán) 執(zhí)行（執(zhí)行（1）ay=a6=4 不滿足當(dāng)循環(huán)條件，不滿足當(dāng)循環(huán)條件，y不動。不動。 執(zhí)行（執(zhí)行（2）zy，做兩件事：，做兩件事： a z = a y ，即，即a 0 = a 6 = 4

51、， z = z +1 = 0+1 = 1，見圖，見圖2zy 圖圖 2k 執(zhí)行（執(zhí)行（3）圖）圖2中的中的a1k滿足當(dāng)循環(huán)的條件，滿足當(dāng)循環(huán)的條件，y = y-1 = 6-1 = 5見圖見圖5，之后退出當(dāng)循環(huán)，因為，之后退出當(dāng)循環(huán)，因為 a y = 3kzy圖圖 5k 執(zhí)行（執(zhí)行（2）a z =a y ，并讓，并讓 z = z+1=3，見圖，見圖6 zy圖圖 6k 執(zhí)行（執(zhí)行（3）由于）由于a3=1k，退出循環(huán)。見圖，退出循環(huán)。見圖7 zy圖圖 7k 執(zhí)行（執(zhí)行（4）az=ay，a5=7。見圖。見圖8 這時仍然這時仍然 zk，讓，讓 y = y-1 = 4。見圖。見圖9zy圖圖 9k 之后，之后

52、，z = y，退出直到型循環(huán)，做，退出直到型循環(huán)，做 a z = k，z = 4， a 4 = 5，這是，這是 5 的最終位置，的最終位置，5 將整個數(shù)據(jù)分成左右將整個數(shù)據(jù)分成左右兩個集合，見圖兩個集合，見圖10。zy圖圖 10左左右右k用上述思路去排左邊的部分用上述思路去排左邊的部分從從 z = 0 到到 y = 3，見圖，見圖11。讓。讓 k = a z = a 0 = 4，然后，然后進(jìn)到直到型循環(huán)，進(jìn)到直到型循環(huán)， 執(zhí)行（執(zhí)行（1）a y = 1k，不滿足當(dāng)循環(huán)的條件，不滿足當(dāng)循環(huán)的條件，y不動。不動。 執(zhí)行（執(zhí)行（2）a z = a y ，z = z+1 = 1, 見圖見圖12zy圖圖

53、 12zy圖圖 11k 執(zhí)行（執(zhí)行（3）a z k，z=z+1=2，a2k，z=z+1=3，這時，這時z=y，不會執(zhí)行（，不會執(zhí)行（4），同時退出直到型循環(huán)，見圖），同時退出直到型循環(huán)，見圖13。然后做然后做 a z =k，即，即a 3 =4，見圖，見圖14，左邊也排好了。，左邊也排好了。圖圖 14zy圖圖 13zykk4、用上述思路去排右邊的部分，見圖、用上述思路去排右邊的部分，見圖15，讓，讓k = a z = a 5 = 7，進(jìn)入直到型循環(huán)；，進(jìn)入直到型循環(huán)； 執(zhí)行（執(zhí)行（1）a y = 6k，y不動不動 執(zhí)行（執(zhí)行（2）a z = a y =6，z = z+1=5+1=6，見圖，見圖1

54、6圖圖 16zy圖圖 15zyk這時這時 z = y，不再執(zhí)行（，不再執(zhí)行（3）（）（4），退出直到型循環(huán)后，），退出直到型循環(huán)后，做做 a z = k，見圖，見圖17。圖圖 17zyk在有了遞歸調(diào)用函數(shù)之后，主程序很容易寫，主程序中應(yīng)在有了遞歸調(diào)用函數(shù)之后，主程序很容易寫，主程序中應(yīng)包含包含1、 定義整型變量：數(shù)組定義整型變量：數(shù)組 a10 ，i ；2、 用循環(huán)結(jié)構(gòu)輸入待排序的數(shù)，將其放入用循環(huán)結(jié)構(gòu)輸入待排序的數(shù)，將其放入 a 數(shù)組；數(shù)組；3、 調(diào)用調(diào)用 sort 函數(shù)，使用三個實際參數(shù)函數(shù)，使用三個實際參數(shù)a將數(shù)組將數(shù)組 a 當(dāng)實參；當(dāng)實參；0數(shù)組下標(biāo)下界；數(shù)組下標(biāo)下界；9數(shù)組下標(biāo)上界；數(shù)

55、組下標(biāo)上界；4、 輸出排序結(jié)果輸出排序結(jié)果下面給出參考程序（分兩頁）下面給出參考程序（分兩頁）/ */ * 程程 序：序：6_6.cpp */ * 作作 者：者：wuwh */ * 編制時間：編制時間：2002年年10月月28日日 */ * 主要功能：快速排序主要功能：快速排序 */ *#include /預(yù)編譯命令預(yù)編譯命令void sort(int array , int zz, int yy)/被調(diào)用函數(shù)，數(shù)組被調(diào)用函數(shù)，數(shù)組array,zz,yy為形參為形參 /函數(shù)體開始函數(shù)體開始 int z,y,i,k; /定義變量定義變量 if ( zzyy ) /如果如果 zz yy ,則做下列

56、則做下列 7 件事件事: / 7 件事開始件事開始z = zz; y = yy; k = array z ; /第第1件事件事do /第第2件事件事(開始開始) while( z=k) y-; /2.1,右邊的元素右邊的元素=k,讓讓 y 往中間移往中間移 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

57、 k, 讓讓 array z array y = array z ; /送給送給array y while( z != y ) ; /第第2件事件事(結(jié)束結(jié)束)array z = k; /第第3件事件事,k已排到位已排到位for(i = zz ;i = yy ;i+) /第第4件事，輸出件事，輸出 coutai=arrayi; ;cout endl; /第第5件事，換行件事，換行sort( array, zz ,z-1 ); /第第6件事，排左邊部分件事，排左邊部分sort( array ,z+1, yy); /第第7件事，排右邊部分件事，排右邊部分 /7件事結(jié)束件事結(jié)束 /函數(shù)體結(jié)束函數(shù)體結(jié)

58、束void main() /主函數(shù)開始主函數(shù)開始 int a10,i; /整型變量整型變量cout 請輸入請輸入10個整數(shù)個整數(shù)n; /提示信息提示信息for (i = 0; i a i ;sort(a,0,9);/調(diào)用調(diào)用sort函數(shù)函數(shù),實參為數(shù)組實參為數(shù)組a和和0，9cout 排序結(jié)果為排序結(jié)果為:; /提示信息提示信息for (i =0; i10 ;i+ ) cout a i ;/輸出排序結(jié)果輸出排序結(jié)果cout 0)&(bookj=0) 條件C=(likeij0)&(bookj=0)LpLp什么也不做什么也不做sh3c=1c=1c!=1n=n+1;輸出方案n;輸出方案n;takei=

59、-1;bookj=0;takei=j;bookj=1;sh1i=4 i!=4i=4 i!=4Try(i+1);Try(i+1);sh2說明：說明：（1）試著給第）試著給第 i 個人分書，先試分個人分書，先試分 0 號書，再分號書，再分 1 號書，號書，分分 2 號書號書，因此有一個與結(jié)點，讓，因此有一個與結(jié)點，讓 j 表示書表示書 j = 0, 1, 2, 3 , 4 。（2）LP 為循環(huán)結(jié)構(gòu)的循環(huán)體。為循環(huán)結(jié)構(gòu)的循環(huán)體。（3）條件）條件 C 是由兩部分是由兩部分“與與”起來的。起來的?！暗诘?i 個人喜歡個人喜歡 j 書，且書，且 j 書尚未被分走書尚未被分走”。滿足這個條件是第。滿足這個條

60、件是第 i 人能夠人能夠得到得到 j 書的條件。書的條件。（4）如果不滿足）如果不滿足 C 條件，則什么也不做，這是直接可解條件，則什么也不做，這是直接可解結(jié)點。結(jié)點。（5）滿足）滿足C條件，做三件事。條件，做三件事。sh1第一件事：第一件事： 將將 j書分給書分給 i，用一個數(shù)組，用一個數(shù)組 take i =j， 記住書記住書 j 給了給了 i ， 同時記錄同時記錄 j 書已被選用，書已被選用，book j = 1。 void Try (int i) for ( j=0; j0)&(bookj=0) T F T F takei=j; 將書將書 j 給給 i sh1 bookj=1; j 書已

61、分書已分 i=4 sh2 n=n+1; 輸出方案輸出方案 n; Try(i+1); 試分下一試分下一人人 takei=-1; i 將書退回將書退回 sh3 bookj=0; 書書 j 待選待選 什 么 也什 么 也不做不做 / */ * 程程 序：序：6_7.cpp */ * 作作 者：者：wuwh */ * 編制時間：編制時間：2002年年10月月28日日 */ * 主要功能：分書問題主要功能：分書問題 */ *#include /預(yù)編譯命令預(yù)編譯命令int take5,n;/整型變量整型變量 int like55 = 0,0,1,1,0, 1,1,0,0,1, 0,1,1,0,1, 0,0

62、,0,1,0, 0,1,0,0,1 ;/整型變量整型變量,定義數(shù)組，初始化定義數(shù)組，初始化int book5=0,0,0,0,0;/整型變量整型變量,定義數(shù)組，初始化定義數(shù)組，初始化下面討論主程序應(yīng)該做的事情下面討論主程序應(yīng)該做的事情 1、將分書方案號預(yù)置、將分書方案號預(yù)置0 2、從第、從第0號人（號人（A）開始試分書，調(diào)用）開始試分書，調(diào)用Try(0)void Try(int i)/函數(shù)體開始函數(shù)體開始int j,k;/定義變量定義變量for(j=0;j0)&(bookj=0) /如果滿足分書條件作下列事如果滿足分書條件作下列事 takei=j;/把把j號書給號書給i bookj=1;/記錄

63、記錄j書已分書已分if(i=4)/如果如果i=4,輸出分書方案輸出分書方案 n+;/讓方案數(shù)加讓方案數(shù)加1 cout 第第 n 個方案個方案n;/輸出分書方案號輸出分書方案號 for(k=0; k=4; k+) /輸出分書方案輸出分書方案 cout takek 號書分給號書分給 char(k+65) endl; cout endl;/換行換行else /如果如果i!=4,繼續(xù)給下一人分書繼續(xù)給下一人分書 Try(i+1);/遞歸調(diào)用遞歸調(diào)用Try(i+1) takei=-1;/讓讓i把書退還把書退還bookj=0;/記錄記錄j書待分書待分 void main()/主函數(shù)主函數(shù)/主函數(shù)開始主函數(shù)開始 n=0;/分書方案號預(yù)置分書方案號預(yù)置0Try(0);/調(diào)用調(diào)用Try函數(shù)函數(shù),實參為實參為0/主函數(shù)結(jié)束主函數(shù)結(jié)束 結(jié)結(jié) 束束Related DocumentsChart DocumentsChart DocumentsRelated DocumentsRelated DocumentsRelated DocumentsRelated Documents