７.１遞歸

遞歸(ｒｅｃｕｒｓｉｏｎ)是計算科學領域的一種重要的思維模式，是一種問題求解的方法。例如，數(shù)學公式ｎ!＝１×２×···×ｎ的計算可以取ｎ－１次乘法的結果，也可以采用另一種思維方法———ｎ!＝ｎ(ｎ－１)!。也就是說，給定ｎ，則ｎ!可由(ｎ－１)!求出，(ｎ－１)!可由(ｎ－２)!求出，···，２!可由１!求出。而１!＝１已知，那么２!可求得，

從而３!可求得，

依次類推，

ｎ!可求得。

這種思維方式便是一種遞歸。

遞歸思維將復雜的計算簡化為簡單計算的不斷重復，是最重要的計算思維。在Ｃ/Ｃ＋＋語言中，遞歸的實現(xiàn)是采用函數(shù)的自我調用來實現(xiàn)。函數(shù)直接

(或間接)調用自己就稱為函數(shù)的遞歸調用，這種函數(shù)就稱為遞歸函數(shù)。遞歸函數(shù)將反復調用其自身，每調用一次就進入新的一層，當最內層的函數(shù)執(zhí)行完畢后，

就一層一層地由里到外返回。

調用自身的過程又稱為“遞推”，由里到外返回的過程又稱為“回歸”，所以遞歸過程可以分為“遞推”和“回歸”兩個階段。下一頁返回７.１遞歸

本節(jié)以一個簡單示例為基點，闡述應用遞歸的程序設計過程?！纠罚薄坑眠f歸函數(shù)編寫計算階乘ｎ!的函數(shù)ｆａｃｔｏｒｉａｌ?！痉治觥侩A乘ｎ!的計算公式如下:根據(jù)上面階乘的計算公式可以發(fā)現(xiàn)，階乘的計算公式是一個遞歸計算公式。為了計算ｎ!，

需要調用計算階乘的函數(shù)ｆａｃｔｏｒｉａｌ(ｎ)，

它因要計算(ｎ－１)!，

而調用ｆａｃｔｏｒｉａｌ(ｎ－１)，于是形成遞歸調用。

這個過程一直持續(xù)到１!為止。

在求得１!＝１以后，

逐層返回，

最后求得ｎ!。上一頁下一頁返回７.１遞歸

算法的偽代碼如下:(１)輸入一個自然數(shù)，

存入變量ｎ；(２)遞歸調用函數(shù)ｆａｃｔｏｒｉａｌ；(３)輸出ｎ!的值；上一頁下一頁返回７.１遞歸

７.１.１

遞歸的思想遞歸是程序設計中的一種常見方法。采用遞歸方法編寫程序可以使程序更加簡潔、清晰、

容易理解。

階乘問題是一個經(jīng)典的數(shù)學遞歸問題。

為了得到ｎ!，

操作步驟如下(注意參數(shù)的變化):(１)第１次調用函數(shù)ｆａｃｔｏｒｉａｌ(ｎ)。

根據(jù)公式可知:ｎ!＝ｎ×(ｎ－１)!。所以，

需要知道(ｎ－１)!的數(shù)值，

那么就需要第２次調用函數(shù)ｆａｃｔｏｒｉａｌ。(２)第２次調用函數(shù)ｆａｃｔｏｒｉａｌ(ｎ－１)。

根據(jù)公式可知:(ｎ－１)!＝(ｎ－１)×(ｎ－２)!。所以，需要知道(ｎ－２)!的數(shù)值，

那么就需要第３次調用函數(shù)ｆａｃｔｏｒｉａｌ。(３)第３次調用函數(shù)ｆａｃｔｏｒｉａｌ(ｎ－２)。

根據(jù)公式可知:(ｎ－２)!＝(ｎ－２)×(ｎ－３)!。所以，需要知道(ｎ－３)!的數(shù)值，

那么就需要第４次調用函數(shù)ｆａｃｔｏｒｉａｌ。上一頁下一頁返回７.１遞歸

直到調用函數(shù)ｆａｃｔｏｒｉａｌ(２)，

都可采用同樣的方法進行處理，

２!＝２×１!。

根據(jù)公式可知:１!＝１。

因此，

問題最終可以求解?？梢钥闯觯看蚊鎸Φ膯栴}在本質上是同一個問題，只是問題的規(guī)模不同。上面的解決方法體現(xiàn)了遞歸的思想，將復雜問題分解為規(guī)模較小的子問題，

且子問題和原問題本質上是相同的問題。在將子問題求解后，原問題也將求解。接下來，

以求解５!為例，

說明遞歸的遞推過程和回歸過程。上一頁下一頁返回７.１遞歸

７.１.２

遞歸的遞推求解５!的遞推過程如下:(１)求解５!，

即調用ｆａｃｔｏｒｉａｌ(５)。

當進入ｆａｃｔｏｒｉａｌ()函數(shù)體后，

由于形參ｎ的值為５，不等于１，

所以執(zhí)行ｆａｃｔｏｒｉａｌ(ｎ－１)?ｎ，

即執(zhí)行ｆａｃｔｏｒｉａｌ(４)?５。

為了求得這個表達式的結果，

必須先調用ｆａｃｔｏｒｉａｌ(４)，

并暫停其他操作。

換言之，

在得到ｆａｃｔｏｒｉａｌ(４)的結果之前，不能進行其他操作。(２)調用ｆａｃｔｏｒｉａｌ(４)時，

實參為４，

形參ｎ

也為４，

不等于１，

因此將繼續(xù)執(zhí)行ｆａｃｔｏｒｉａｌ(ｎ－１)?ｎ，

即執(zhí)行ｆａｃｔｏｒｉａｌ(３)?４。

為了求得這個表達式的結果，

必須先調用ｆａｃｔｏ-ｒｉａｌ(３)。上一頁下一頁返回７.１遞歸

(３)調用ｆａｃｔｏｒｉａｌ(３)時，

實參為３，

形參ｎ

也為３，

不等于１，

因此將繼續(xù)執(zhí)行ｆａｃｔｏｒｉａｌ(ｎ－１)?ｎ，

也即執(zhí)行ｆａｃｔｏｒｉａｌ(２)?３。

為了求得這個表達式的結果，

又必須先調用ｆａｃｔｏｒｉａｌ(２)。(４)調用ｆａｃｔｏｒｉａｌ(２)時，

實參為２，

形參ｎ也為２，

不等于１，

因此將繼續(xù)執(zhí)行ｆａｃｔｏｒｉａｌ(ｎ－１)?ｎ，

即執(zhí)行ｆａｃｔｏｒｉａｌ(１)?２。

為了求得這個表達式的結果，

必須先調用ｆａｃｔｏ-ｒｉａｌ(１)。(５)在進行４次調用后，

實參的值為１，

因此將調用ｆａｃｔｏｒｉａｌ(１)。

此時，

能夠直接得到常量為１的值，

并把結果返回，

不需要再次調用ｆａｃｔｏｒｉａｌ()函數(shù)，

遞歸結束。表７－１列出了在遞歸調用過程中逐層進入的遞推過程。上一頁下一頁返回７.１遞歸

７.１.３遞歸的回歸當遞歸進入最內層時，就結束遞歸，開始逐層退出，即逐層執(zhí)行ｒｅｔｕｒｎ語句，這就是遞歸的回歸過程。

求解５!的回歸過程如下:(１)當ｎ的值為１時，

達到最內層，

此時ｒｅｔｕｒｎ的結果為１，

即ｆａｃｔｏｒｉａｌ(１)的調用結果為１。(２)有了ｆａｃｔｏｒｉａｌ(１)的結果，

就可以返回上一層，

計算ｆａｃｔｏｒｉａｌ(１)?２的值。

此時，得到的值為２，

ｒｅｔｕｒｎ的結果也為２，

即ｆａｃｔｏｒｉａｌ(２)的調用結果為２。(３)有了ｆａｃｔｏｒｉａｌ(２)的結果，

就可以返回上一層，

計算ｆａｃｔｏｒｉａｌ(２)?３的值。

此時，得到的值為６，

ｒｅｔｕｒｎ的結果也為６，

即ｆａｃｔｏｒｉａｌ(３)的調用結果為６。上一頁下一頁返回７.１遞歸

(４)有了ｆａｃｔｏｒｉａｌ(３)的結果，

就可以返回上一層，

計算ｆａｃｔｏｒｉａｌ(３)?４的值。

此時，得到的值為２４，

ｒｅｔｕｒｎ的結果也為２４，

即ｆａｃｔｏｒｉａｌ(４)的調用結果為２４。(５)有了ｆａｃｔｏｒｉａｌ(４)的結果，

就可以返回上一層，

計算ｆａｃｔｏｒｉａｌ(４)?５的值。

此時，得到的值為１２０，

ｒｅｔｕｒｎ的結果也為１２０，

即ｆａｃｔｏｒｉａｌ(５)的調用結果為１２０。

這樣就得到了５!的值。表７－２列出了在遞歸調用過程中逐層退出的回歸過程。上一頁下一頁返回７.１遞歸

７.１.４遞歸的條件每一個遞歸函數(shù)都應該只進行有限次遞歸調用，否則就會進入死胡同，

永遠也不能退出，這樣的程序是沒有意義的。要想讓遞歸函數(shù)逐層進入再逐層退出，需要解決以下兩方面的問題:(１)存在限制條件，

當符合該條件時，

遞歸便不再繼續(xù)。

對于函數(shù)ｆａｃｔｏｒｉａｌ，

當形參ｎ等于１時，遞歸就結束。這種限制條件就是遞歸結束條件，稱為遞歸出口。(２)每次遞歸調用后，

越來越接近該限制條件。

對于函數(shù)ｆａｃｔｏｒｉａｌ，

每次遞歸調用的實參為ｎ－１，這會使形參ｎ的值逐漸減小，越來越趨近于１。上一頁下一頁返回７.１遞歸

７.１.５

遞歸的實現(xiàn)經(jīng)過上面遞歸調用的分析，例７－１的程序代碼如下:上一頁下一頁返回７.１遞歸

上一頁下一頁返回７.１遞歸

【練習】(１)用遞歸方法求１~１００的和，

即１＋２＋３＋４＋···＋１００。提示:遞歸求和公式為(２)用遞歸方法求１~１００的連乘積，

即１×２×３×４×···×１００。提示:遞歸求連乘積公式為(３)從１，２，３，···，ｎ中取出ｍ個數(shù)，一共有多少種選擇方案?提示:計算從ｎ個數(shù)中取ｍ個數(shù)的組合數(shù)的公式為上一頁返回７.２迭代與遞歸

在計算機編程實現(xiàn)中，

常常有兩種編程思想:迭代(ｉｔｅｒａｔｅ)；

遞歸(ｒｅｃｕｒｓｉｏｎ)。

從概念上講，遞歸是指程序調用自身的編程思想，即一個函數(shù)調用本身；迭代是利用已知的變量值，根據(jù)遞推公式不斷演進得到變量新值的編程思想。簡而言之，遞歸將大問題化為相同結構的小問題，從待求解的問題出發(fā)，一直分解到已知答案的最小問題為止，然后逐級返回，從而得到大問題的解；而迭代則從已知值出發(fā)，通過遞推式，不斷更新變量新值，直到能夠解決問題為止。下面以斐波那契數(shù)列的求解為例，介紹這兩種典型編程思想的實現(xiàn)，并分析二者的區(qū)別與聯(lián)系。下一頁返回７.２迭代與遞歸

【例７－２】斐波那契數(shù)列(又稱為黃金分割數(shù)列，

通常記做Ｆｉｂｏｎａｃｃｉ)指的是這樣一個數(shù)列:１，１，２，３，５，８，１３，２１，···這個數(shù)列從第３項開始，每一項都等于前兩項之和。該數(shù)列剛好和一個有趣的兔子問題相關。一般而言，兔子在出生兩個月后，就有繁殖能力，一對兔子每個月能生出一對小兔子來。如果所有兔子都不死，那么若干個月以后的兔子對數(shù)為:１，１，２，３，５，８，１３，３１，···【分析】如果在數(shù)列的前面加上數(shù)字“０”，那么從第２項開始，每一項都是該項前兩項的數(shù)字之和。

數(shù)列的通項表達式Ｆ(ｎ)如下:上一頁下一頁返回７.２迭代與遞歸

７.２.１

遞歸實現(xiàn)可以采用遞歸的編程方式求解例７－２的問題，方法是定義一個函數(shù)Ｆｉｂ，返回數(shù)列第ｎ項的值。將規(guī)模為ｎ的問題分解為更小規(guī)模的問題，即規(guī)模為ｎ－１的問題與規(guī)模為ｎ－２的問題，

一直分解到規(guī)模為０和規(guī)模為１的問題。

數(shù)列的通項表達式Ｆｉｂ(ｎ)如下所示:例７－２遞歸函數(shù)的偽代碼如下:(１)如果函數(shù)形參是０，

則函數(shù)返回０，

并回歸上一層；(２)如果函數(shù)形參是１，

則函數(shù)返回１，

并回歸上一層；(３)如果函數(shù)形參大于１，

則繼續(xù)遞歸調用函數(shù)。上一頁下一頁返回７.２迭代與遞歸

將例７－２采用遞歸求解的函數(shù)Ｆｉｂ的代碼如下:上一頁下一頁返回７.２迭代與遞歸

７.２.２

迭代實現(xiàn)例７－２也可以采用迭代的方式求解。同樣，需要定義一個函數(shù)Ｆｉｂ，但不將問題分解，而是直接利用已知的變量值，根據(jù)遞推公式不斷演進。由例７－２的遞推公式可知，已知兩個初值(即數(shù)列第０項的值和數(shù)列第１項的值)，那么根據(jù)遞推公式，就可以得到第２項的值，，得到第ｎ項的值。算法的偽代碼如下:(１)定義兩個變量ｆ０和ｆ１，

初值分別為０和１；(２)如果函數(shù)形參ｎ是０，

則函數(shù)返回０；(３)如果函數(shù)形參ｎ是１，

則函數(shù)返回１；(４)循環(huán)變量ｉ初始化為２，

當循環(huán)變量ｉ≤ｎ時，(４.１)計算數(shù)列下一項的值，

ｆ＝ｆ０＋ｆ１；(４.２)更新變量，

ｆ０＝ｆ１，

ｆ１＝ｆ；(４３)ｉ＋＋；(５)函數(shù)返回ｆ的值。上一頁下一頁返回７.２迭代與遞歸

將例７－２采用迭代求解的函數(shù)Ｆｉｂ代碼如下:上一頁下一頁返回７.２迭代與遞歸

上一頁下一頁返回７.２迭代與遞歸

【練習】(１)改寫上述迭代算法，

將一維數(shù)組作為Ｆｉｂ函數(shù)的形參，

把前ｎ項斐波那契數(shù)列存入數(shù)組，并編寫ｍａｉｎ函數(shù)，輸出斐波那契數(shù)列前１００項的數(shù)值，輸出方式為每行１０項。(２)將７１５節(jié)練習１和練習２的遞歸程序改寫為迭代程序。(３)求ｘ平方根近似值的迭代公式為ｘｎ

＋

１＝(ｘｎ＋ｘ/ｘｎ

)/２。

當ｎ為１時，

ｘ１為ｘ，

迭代一次求得的平方根近似值為ｘ２；ｎ為２時，求得的近似值為ｘ３，依次類推。輸入正整數(shù)ｘ和整數(shù)ｎ(ｎ≥０，

且ｘ和ｎ都不會出現(xiàn)溢出情況)。

求利用上述公式，

求ｘ迭代ｎ次后的平方根近似值，保留計算結果小數(shù)點后５位有效數(shù)字。例如，輸入１６和４，

則輸出４００２２６。上一頁下一頁返回７.２迭代與遞歸

７.２.３

遞歸與迭代的關系遞歸，實際上就是不斷地深層調用函數(shù)，直到函數(shù)有返回值才會逐層返回。因此，

遞歸涉及運行時的堆棧開銷(參數(shù)必須壓入堆棧保存，直到該層函數(shù)調用返回為止)，有可能導致堆棧溢出的錯誤。但是，遞歸編程所體現(xiàn)的思想正是人們追求簡潔、將問題交給計算機，以及將大問題分解為相同小問題從而解決大問題的動機。迭代在大部分時候需要人為地對問題進行剖析，

將問題轉變?yōu)橐淮未蔚倪f推來逼近答案。迭代不像遞歸一樣對堆棧有一定要求，一旦問題剖析完畢，就可以很容易地通過循環(huán)加以實現(xiàn)。在理論上，遞歸和迭代在時間復雜度方面是等價的(暫不考慮函數(shù)調用開銷和函數(shù)調用產(chǎn)生的堆棧開銷)，但實際上，遞歸的效率比迭代低。既然遞歸沒有任何優(yōu)勢，

那么是不是就沒有使用遞歸的必要了?遞歸的存在有何意義呢?上一頁下一頁返回７.２迭代與遞歸

從理論上說，所有的遞歸函數(shù)都可以轉換為迭代函數(shù)，反之亦然，然而代價通常都比較高。但是，就算法結構而言，遞歸聲明的結構并不總能轉換為迭代結構；就實際而言，所有的迭代都可以轉換為遞歸，但遞歸不一定可以轉換為迭代。迭代雖然效率高，運行時間只因循環(huán)次數(shù)增加而增加，沒什么額外開銷，空間上也沒有什么增加，但其代碼不易理解，

在編寫復雜問題時，算法實現(xiàn)較為困難。上一頁返回７.３實訓與實訓指導

實訓１

走臺階有個人剛剛看完電影?第３９級臺階?，離開電影院時，他數(shù)了數(shù)禮堂前的臺階數(shù)，恰好是３９級!站在臺階前，他想到一個問題:如果我每一步只能邁上１個或２個臺階，先邁左腳，然后左右交替，最后一步邁右腳，也就是說一共要走偶數(shù)步。那么，上完３９級臺階，有多少種不同的上法呢?１實訓分析為了統(tǒng)計走完３９級臺階的方法，設結果變量ｒｅｓｕｌｔ表示上臺階的方法數(shù)，初始值是０。由于每走到一級臺階，都需要統(tǒng)計步數(shù)，所以設變量ｎｕｍ表示臺階，ｓｔｅｐ表示走到ｎｕｍ級臺階的步數(shù)。題目中說明每一步只能邁上１個或２個臺階，所以第ｓｔｅｐ＋１步有可能到達ｎｕｍ＋１級臺階，也有可能到達ｎｕｍ＋２級臺階。第ｓｔｅｐ＋２步也是同樣的情況，依次類推。這里也就是程序的遞歸。那么當ｎｕｍ＝３９時，表示此時走完３９級臺階。下一頁返回７.３實訓與實訓指導

由于題目中要求先邁左腳，然后左右交替，最后一步邁右腳，也就是說一共要走偶數(shù)步，所以當ｎｕｍ＝３９時，還需要判斷當前的步數(shù)是否為偶數(shù)步，即“ｓｔｅｐ％２＝＝０”是否成立。如果滿足偶數(shù)步，則表示一種方案成立，即ｒｅｓｕｌｔ＋＋；如果不滿足偶數(shù)步，表示這種走法不符合要求，舍棄。算法的偽代碼如下:(１)設置遞歸的初始條件，

第ｎｕｍ＝０級臺階，

共走ｓｔｅｐ＝０步；(２)處理遞歸的下一步，

對于ｓｔｅｐ＋１級臺階，

ｎｕｍ－２或者ｎｕｍ－１，

判斷遞歸是否結束；(３)輸出結果。上一頁下一頁返回７.３實訓與實訓指導

程序的代碼如下：上一頁下一頁返回７.３實訓與實訓指導

上一頁下一頁返回７.３實訓與實訓指導

上一頁下一頁返回７.３實訓與實訓指導

２實訓練習編寫程序遞歸實現(xiàn)某個自然數(shù)ｎ的ｋ次冪。提示:遞歸公式為上一頁下一頁返回７.３實訓與實訓指導

實訓２

換汽水已知１元可以買１瓶汽水，３個瓶蓋可以換１瓶汽水，２個空瓶也可以換１瓶汽水。那么，ｎ元總共可以買到多少瓶汽水?１實訓分析不妨設變量ｍｏｎｅｙ、ｗａｔｅｒ分別表示錢的金額數(shù)和當前的汽水數(shù)量。題目中說明１元可以買１瓶汽水，所以汽水的最初數(shù)量等于錢的金額大小，即ｗａｔｅｒ＝ｍｏｎｅｙ。另外，設變量ｃａｐ、ｂｏｔｔｌｅ分別表示當前的瓶蓋數(shù)量和空瓶數(shù)量。由題目可知，３個瓶蓋可以換１瓶汽水，２個空瓶也可以換１瓶汽水，所以此時瓶蓋和空瓶可以兌換的汽水數(shù)量分別為ｃａｐ/３、ｂｏｔｔｌｅ/２。因此，汽水的數(shù)量由兩部分組成，即之前的汽水數(shù)量和兌換的汽水數(shù)量。上一頁下一頁返回７.３實訓與實訓指導

兌換汽水后，

瓶蓋和空瓶的數(shù)量分別是ｃａｐ％３、ｂｏｔｔｌｅ％２，可以用來兌換的汽水數(shù)量是ｃａｐ/３＋ｂｏｔｔｌｅ/２。如此便可以進行下一次兌換，這就是該題的遞歸部分。直到可兌換的汽水數(shù)量等于０時，遞歸結束。算法的偽代碼如下:(１)根據(jù)１元買１瓶汽水的原則，

可知初始汽水的數(shù)量ｗａｔｅｒ＝ｍｏｎｅｙ；(２)初始化遞歸的條件，

可以用來兌換的汽水數(shù)量:ｗａｔｅｒ＝ｍｏｎｅｙ，

ｃａｐ＝０，

ｂｏｔｔｌｅ＝０；(３)兌換后，

更新ｃａｐ、

ｂｏｔｔｌｅ的數(shù)值，

并判斷是否有下一次兌換的可能性。

如果還可以兌換，則繼續(xù)遞歸；否則，退出遞歸。上一頁下一頁返回７.３實訓與實訓指導

程序的代碼如下：上一頁下一頁返回７.３實訓與實訓指導

上一頁下一頁返回７.３實訓與實訓指導

２實訓練習編寫程序，利用遞歸公式求函數(shù)值:上一頁下一頁返回７.３實訓與實訓指導

實訓３

排列數(shù)從ｎ個不同元素中任?。?ｍ≤ｎ)個元素，

按照一定的順序排列起來。

當ｍ＝ｎ時，

所有的排列情況稱為全排列。例如，１、２、３三個元素的全排列如下:１，２，３１，３，２２，１，３２，３，１３，１，２３，２，１上一頁下一頁返回７.３實訓與實訓指導

１實訓分析常用的全排列方法有遞歸算法和非遞歸算法。其中，遞歸算法有四種:字典序法、遞增進位制數(shù)法、遞減進位制數(shù)法和鄰位對換法。字典序法的排列規(guī)則:對給定的字符集中的字符規(guī)定一個先后關系，在此基礎上規(guī)定兩個全排列的先后是從左到右逐個比較對應的字符的先后。

例如，

對于字符集{１，２，３}，

要求將較小的數(shù)字排序較先，

這樣按字典序法生成的全排列是:１２３，１３２，２１３，２３１，３１２，３２１。

遞歸算法由函數(shù)Ｐｅｒｍ(ｉｎｔｌｉｓｔ[]，ｉｎｔｋ，ｉｎｔｍ)實現(xiàn)，將ｌｉｓｔ的前ｋ個元素作為前綴、剩下的ｍ－ｋ個元素進行全排列而得到排列。其想法是將第ｋ個元素與后面的每個元素進行交換，求出其全排列。上一頁下一頁返回７.３實訓與實訓指導

算法的偽代碼如下:(１)讀入?yún)⑴c全排列的數(shù)據(jù)個數(shù)以及具體的數(shù)值；(２)從左向右逐個與后面的元素進行交換；(３)遞歸上述過程，

直到得到ｎ個數(shù)，

得到一個全排列；(４)為了下一個全排列，

需要把剛才發(fā)生交換的兩個數(shù)值恢復原狀態(tài)。

然后，

繼續(xù)２和３，尋找下一種全排列。上一頁下一頁返回７.３實訓與實訓指導

程序的代碼如下：上一頁下一頁返回７.３實訓與實訓指導

上一頁下一頁返回７.３實訓與實訓指導

上一頁下一頁返回７.３實訓與實訓指導

上一頁下一頁返回７.３實訓與實訓指導

２實訓練習Ａ~Ｉ代表１~９的數(shù)字，不同的字母代表不同的數(shù)字。字母Ａ~Ｉ組成了下面的算式:某些數(shù)字的排列剛好使該式成立。例如，６＋８/３＋９５２/７１４就是一種解法，５＋３/１＋９７２/４８６是另一種解法。這個算式一共有多少種解法?提示:考慮１~９的每種全排列能否使該式成立即可。上一頁下一頁返回７.３實訓與實訓指導

實訓４

漢諾塔漢諾塔(ＨａｎｏｉＴｏｗｅｒ)又稱河內塔，

已知有三根柱子，

在一根柱子上從下往上按照大小順序摞著６４個圓盤。現(xiàn)在需要把圓盤按大小順序重新擺放在另一根柱子上。規(guī)定:任何時候，在小圓盤上都不能擺放大圓盤，且在三根柱子之間一次只能移動一個圓盤。如果將三根柱子分別命名為Ａ、Ｂ、Ｃ，Ａ柱子上有ｎ片黃金圓盤，應該如何操作才能實現(xiàn)該任務?編寫程序輸出圓盤移動的操作步驟。要求從鍵盤接收圓盤的數(shù)量。上一頁下一頁返回７.３實訓與實訓指導

１實訓分析對于這樣一個問題，我們很難直接給出圓盤移動的順序。但是，可以先觀察圓盤數(shù)量較少時的規(guī)律，進而解決這個問題。假設Ａ柱子上的ｎ個圓盤從上至下的編號依次為１、２、···、ｎ，規(guī)定將圓盤從Ａ柱子直接移動到Ｃ柱子上的過程記為Ａ→Ｃ，則:(１)當ｎ＝１時，第１次移動:１號圓盤Ａ→Ｃ。(２)當ｎ＝２時，第１次移動:１號圓盤Ａ→Ｂ；第２次移動:２號圓盤Ａ→Ｃ；第３次移動:１號圓盤Ｂ→Ｃ?？梢钥闯?，第１次移動將２號圓盤上的１號圓盤從Ａ柱子移到Ｂ柱子上。第２次移動將２號圓盤從Ａ柱子移到Ｃ柱子上。第３次移動除將２號圓盤外的１號圓盤從Ｂ柱子移動到Ｃ柱子上。上一