計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ) 5

1、121nkxx34自定義函數(shù)自定義函數(shù) ( ()例例: int power(p,n)power為函數(shù)名，要以英文字母開(kāi)頭。為函數(shù)名，要以英文字母開(kāi)頭。int是函數(shù)值的數(shù)據(jù)類型，這里是是函數(shù)值的數(shù)據(jù)類型，這里是int（整型）。（整型）。(p,n)括號(hào)中的括號(hào)中的p,n為函數(shù)的形式參數(shù)，形式參數(shù)也要定義其數(shù)據(jù)為函數(shù)的形式參數(shù)，形式參數(shù)也要定義其數(shù)據(jù)類型。類型。函數(shù)定義的一般格式：函數(shù)定義的一般格式： ()為了突出重點(diǎn)，先學(xué)會(huì)基本東西，省略掉一些事情先不講。為了突出重點(diǎn)，先學(xué)會(huì)基本東西，省略掉一些事情先不講。51、形式參數(shù)是在定義函數(shù)時(shí)放在函數(shù)名后括號(hào)中的參數(shù)。在未進(jìn)、形式參數(shù)是在定義函數(shù)時(shí)放在函數(shù)

2、名后括號(hào)中的參數(shù)。在未進(jìn)行函數(shù)調(diào)用時(shí)，并不對(duì)形式參數(shù)分配內(nèi)存單元。在發(fā)生函數(shù)調(diào)行函數(shù)調(diào)用時(shí)，并不對(duì)形式參數(shù)分配內(nèi)存單元。在發(fā)生函數(shù)調(diào)用時(shí)，立刻給形式參數(shù)分配內(nèi)存單元。調(diào)用結(jié)束后，釋放掉行用時(shí)，立刻給形式參數(shù)分配內(nèi)存單元。調(diào)用結(jié)束后，釋放掉行參所占的內(nèi)存單元。參所占的內(nèi)存單元。2、因此，形參變量屬于局部變量，其作用域在它所在的函數(shù)體內(nèi)。、因此，形參變量屬于局部變量，其作用域在它所在的函數(shù)體內(nèi)。3、在定義函數(shù)的時(shí)候，必須指定形參變量的類型，如何指定？有、在定義函數(shù)的時(shí)候，必須指定形參變量的類型，如何指定？有二種方法：二種方法：形式參數(shù)與實(shí)在參數(shù)形式參數(shù)與實(shí)在參數(shù)(1) int power(p,n)

3、 int p,n; (2) int power(int p,int n) 有些編譯系統(tǒng)不認(rèn)識(shí)第（有些編譯系統(tǒng)不認(rèn)識(shí)第（2）種形式）種形式64、實(shí)在參數(shù)是一個(gè)具有確定值的表達(dá)式。函數(shù)在調(diào)用時(shí)，將實(shí)在、實(shí)在參數(shù)是一個(gè)具有確定值的表達(dá)式。函數(shù)在調(diào)用時(shí)，將實(shí)在參數(shù)賦給形式參數(shù)。參數(shù)賦給形式參數(shù)。比如，主函數(shù)調(diào)用比如，主函數(shù)調(diào)用SOP(n,k)，這時(shí)，這時(shí)，n,k為實(shí)在參數(shù)，為實(shí)在參數(shù)，n的的值為值為6，k的值為的值為4。在被調(diào)用函數(shù)定義中，。在被調(diào)用函數(shù)定義中，int SOP(m,l)中的中的m,l為形式參數(shù)，在為形式參數(shù)，在SOP被調(diào)用時(shí)，系統(tǒng)給被調(diào)用時(shí)，系統(tǒng)給m,l這兩個(gè)形式參數(shù)分配這兩個(gè)形式參數(shù)

4、分配了內(nèi)存單元。之后，了內(nèi)存單元。之后，n的值的值6賦給賦給m，k的值的值4賦給賦給l。 m l 4 6 實(shí)在參數(shù)的個(gè)數(shù)及類型應(yīng)與形式參數(shù)一致。賦值時(shí)前后對(duì)應(yīng)關(guān)系實(shí)在參數(shù)的個(gè)數(shù)及類型應(yīng)與形式參數(shù)一致。賦值時(shí)前后對(duì)應(yīng)關(guān)系不會(huì)改變。下面畫(huà)出主函數(shù)與不會(huì)改變。下面畫(huà)出主函數(shù)與SOP函數(shù)，調(diào)用與被調(diào)用時(shí)參數(shù)函數(shù)，調(diào)用與被調(diào)用時(shí)參數(shù)傳遞關(guān)系：傳遞關(guān)系：761(4)lxsumxlli8power(i,l)處在處在SOP(m,l)函數(shù)中，表示函數(shù)中，表示SOP函數(shù)去調(diào)用函數(shù)去調(diào)用power 函數(shù)。其中函數(shù)。其中i,l為實(shí)在參數(shù)，而為實(shí)在參數(shù)，而int power(p,q)中中的的p,q為形式參數(shù)。為形式參數(shù)

5、。比如，執(zhí)行比如，執(zhí)行SOP(6,4)時(shí)，時(shí)，l=4,m=6,當(dāng)當(dāng)i=1時(shí)，時(shí)，sum=sum+power(1,4)這里這里1，4為實(shí)在參數(shù)，調(diào)用為實(shí)在參數(shù)，調(diào)用power(p,q)，兩個(gè)形式參數(shù)，兩個(gè)形式參數(shù)p,q分別被賦以分別被賦以1，4。9 執(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)

6、 = 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): product = 3*3*3*3 return(81) = 81

7、 調(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)用用 10遞歸算法遞歸算法在可計(jì)算性理論中占有重要地位，它是算法在可計(jì)算性理論中占有重要地位，它是算法設(shè)計(jì)的有力工具，對(duì)于拓展編程思路非常有用。就設(shè)計(jì)的有力工具，對(duì)于拓展編程思路非常有用。就遞歸算法而

8、言并不涉及高深數(shù)學(xué)知識(shí)，只不過(guò)初學(xué)遞歸算法而言并不涉及高深數(shù)學(xué)知識(shí)，只不過(guò)初學(xué)者要建立起遞歸概念不十分容易。者要建立起遞歸概念不十分容易。我們先從一個(gè)最簡(jiǎn)單的例子導(dǎo)入。我們先從一個(gè)最簡(jiǎn)單的例子導(dǎo)入。用遞歸算法求用遞歸算法求n!定義：函數(shù)定義：函數(shù) fact(n) = n!fact(n-1) = (n-1)!則有則有 fact(n) = n fact(n-1)已知已知 fact(1) = 111為了表述得直觀清晰，我們定義兩個(gè)結(jié)點(diǎn)：為了表述得直觀清晰，我們定義兩個(gè)結(jié)點(diǎn)：或結(jié)點(diǎn)或結(jié)點(diǎn)與與與結(jié)點(diǎn)。與結(jié)點(diǎn)。圖示的直觀性與思維助力。圖示的直觀性與思維助力。1、或結(jié)點(diǎn)、或結(jié)點(diǎn),BZ trueCZfalse

9、A（真）（假） A 條條件件Z 條條件件!Z B C A為為“或結(jié)點(diǎn)或結(jié)點(diǎn)”，A依不同條件會(huì)有兩種不同的取值依不同條件會(huì)有兩種不同的取值B或或C。結(jié)點(diǎn)用。結(jié)點(diǎn)用 表示。表示。 12如果有多于如果有多于2種取值，可用下圖：種取值，可用下圖： Z1 Z2 Zn B C G A 條件為條件為Z1, Z2, Z1, Z2, ,Zn,Zn，取值為，取值為B B或或C,C,或或G G132、與結(jié)點(diǎn)、與結(jié)點(diǎn)與結(jié)點(diǎn)要涂黑，相關(guān)聯(lián)與結(jié)點(diǎn)要涂黑，相關(guān)聯(lián)的的B B與與C C之間要用弧線之間要用弧線連起來(lái)。連起來(lái)。A A為與結(jié)點(diǎn)，為與結(jié)點(diǎn)，A A的最終取值為的最終取值為C C結(jié)點(diǎn)的值，但為了結(jié)點(diǎn)的值，但為了求得求得C

10、 C的值，得先求出的值，得先求出B B結(jié)點(diǎn)的值，結(jié)點(diǎn)的值，C C是是B B的函數(shù)。的函數(shù)。ABC14仍以求仍以求n!為例畫(huà)出如下與或圖為例畫(huà)出如下與或圖A為或結(jié)點(diǎn)；為或結(jié)點(diǎn)；B為直接可解結(jié)點(diǎn)，值為為直接可解結(jié)點(diǎn)，值為1；C為與結(jié)點(diǎn)，當(dāng)為與結(jié)點(diǎn)，當(dāng)n1時(shí)，時(shí)，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)15與結(jié)點(diǎn)可能有多個(gè)相關(guān)聯(lián)的點(diǎn)，這時(shí)可描述為下圖與結(jié)點(diǎn)可能有多個(gè)

11、相關(guān)聯(lián)的點(diǎn)，這時(shí)可描述為下圖A結(jié)點(diǎn)的值最終為結(jié)點(diǎn)的值最終為D的值，但為了求的值，但為了求D需先求需先求B和和C。從。從圖上看先求左邊的點(diǎn)才能求最右邊的點(diǎn)的值，我們圖上看先求左邊的點(diǎn)才能求最右邊的點(diǎn)的值，我們約定最右邊約定最右邊D點(diǎn)的值就是點(diǎn)的值就是A結(jié)點(diǎn)的值。結(jié)點(diǎn)的值。ABDC16下面我們以下面我們以3！為例來(lái)畫(huà)與或結(jié)點(diǎn)圖，目的是體會(huì)遞歸！為例來(lái)畫(huà)與或結(jié)點(diǎn)圖，目的是體會(huì)遞歸的含義。的含義。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)AE211

12、7下面畫(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)用18從圖可以想象：從圖可以想象：欲求欲求fact(3)，先要求，先要求fact(2)；要求；要求fact(2)先求先求fact(1)。就象剝一顆圓白菜，從外向里，一層層剝下來(lái)，到就象剝一顆圓白菜，從外向里，一層層剝下來(lái)，到了菜心，遇到了菜心，遇到1的階乘，其值為的階乘，其值為1，

13、到達(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à)了如下的流程圖：程圖：19 31 fact(3) 真真 假假 調(diào)調(diào)用用 fact(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 返返回回 返返回回 20為了形象地描述遞歸過(guò)程，將上圖改畫(huà)成下圖為了形

14、象地描述遞歸過(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 返返回回 21在這個(gè)圖中在這個(gè)圖中“內(nèi)層內(nèi)層”與與“外層外層”有著相同的結(jié)構(gòu)。它有著相同的結(jié)構(gòu)。它們之間們之間“你中有我，我中有你你中有我，我中有你”，呈現(xiàn)相互依存的，呈現(xiàn)相互依存的關(guān)系。關(guān)系。為了進(jìn)一步講清遞歸的概念，將為了進(jìn)一步講清遞歸的概念，將遞歸遞歸與與遞推遞推做一比較。做一比較。仍以求階乘為例。仍以求階乘為例。

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

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

17、法就會(huì)使問(wèn)題變得易于處理。下面舉一個(gè)盡人皆知的例子處理。下面舉一個(gè)盡人皆知的例子哈諾（哈諾（Hanoi）塔）塔問(wèn)題。問(wèn)題。23故事：相傳在古代印度的故事：相傳在古代印度的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)，

18、如以每秒移動(dòng)一很簡(jiǎn)單，真的動(dòng)手移盤(pán)就會(huì)發(fā)現(xiàn)，如以每秒移動(dòng)一只盤(pán)子的話，按照上述規(guī)則將只盤(pán)子的話，按照上述規(guī)則將64只盤(pán)子從一個(gè)柱子只盤(pán)子從一個(gè)柱子移至另一個(gè)柱子上，所需時(shí)間約為移至另一個(gè)柱子上，所需時(shí)間約為5800億年。億年。 24怎樣編寫(xiě)這種程序？思路上還是先從最簡(jiǎn)單的情況分怎樣編寫(xiě)這種程序？思路上還是先從最簡(jiǎn)單的情況分析起，搬一搬看，慢慢理出思路。析起，搬一搬看，慢慢理出思路。1、在、在A柱上只有一只盤(pán)子，假定盤(pán)號(hào)為柱上只有一只盤(pán)子，假定盤(pán)號(hào)為1，這時(shí)只，這時(shí)只需將該盤(pán)從需將該盤(pán)從A搬至搬至C，一次完成，記為，一次完成，記為move 1 from A to C A B C 252、在、在A

19、柱上有二只盤(pán)子，柱上有二只盤(pán)子，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；這三步記為：這三步記為：move 1 from A to B;move 2 from A to C;move 3 form B to C; A B C 1 3 2 263 3、在、在A A柱上有柱上有3 3只盤(pán)子，從小到大分別為只盤(pán)子，從小到大分別為1 1號(hào)，號(hào)，2 2號(hào)，號(hào)，3 3號(hào)號(hào)第（第（1 1）步將）步將1 1號(hào)盤(pán)和號(hào)盤(pán)

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

21、move( 2, B, A, C)意思是將意思是將2 2只盤(pán)子作為整體從只盤(pán)子作為整體從B B借助借助A A移至移至C C。所謂所謂借助借助是什么意思，等這件事做完了不言自明。是什么意思，等這件事做完了不言自明。27 A B C 1 3 2 284、從題目的約束條件看，大盤(pán)上可以隨便摞小盤(pán)，相、從題目的約束條件看，大盤(pán)上可以隨便摞小盤(pán)，相反則不允許。在將反則不允許。在將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í)際上是分解為以下三步實(shí)際上是分解為以下三步第（第（1）.1步：步：move 1 form A to C;第（第（1）.2步：步：m

22、ove 2 form A to B;第（第（1）.3步：步：move 1 form C to B;經(jīng)過(guò)以上步驟，將經(jīng)過(guò)以上步驟，將1號(hào)和號(hào)和2號(hào)盤(pán)作為整體從號(hào)盤(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ò)程了。實(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）

23、.3步：步：move 1 form A to C;295、看、看move(2, A, C, B)是說(shuō)要將是說(shuō)要將2只盼自從只盼自從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，然后再把，然后再把1盤(pán)從盤(pán)從C移移至至B?？吹竭@里就能明白借助?？吹竭@里就能明白借助C的含義了。因此，在的含義了。因此，在構(gòu)思搬移過(guò)程的參量時(shí)，要把構(gòu)思搬移過(guò)程的參量時(shí)，要把3個(gè)柱子都用上。個(gè)柱子都用上。6、定義搬移函數(shù)、定義搬移函數(shù)move(n, A, B, C)，物理意義是將，物理意義是將n只只盤(pán)子從盤(pán)子

24、從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)步，可步，可以將搬移過(guò)程以將搬移過(guò)程用如下的與或用如下的與或結(jié)點(diǎn)圖表示。結(jié)點(diǎn)圖表示。30這里用與或結(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)理解為將上面的理解為將上面的n-1只盤(pán)

25、子作為一只盤(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移至移至C，是直接可，是直接可解結(jié)點(diǎn)；解結(jié)點(diǎn)；(3)Move(n-1, B, A, C)理解為將上面的理解為將上面的n-1只盤(pán)子作為一只盤(pán)子作為一個(gè)整體從個(gè)整體從B經(jīng)經(jīng)A移至移至C。31這里顯然是一種遞歸定義，當(dāng)著解這里顯然是一種遞歸定義，當(dāng)著解move(n-1, A, C, B)時(shí)時(shí)又可想到，將其分解為又可想到，將其分解為3步：步：第第1步：將上面的步：將上面的n-2只盤(pán)子作為一個(gè)整體從只盤(pán)子作為一個(gè)整體從A經(jīng)經(jīng)B到到C，move(n-2, A, B, C)；第第2步：第步：

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

27、)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)33 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)用

28、調(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) 34 輸出輸出 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,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