馬健喆

摘 要： 為了提升學(xué)生的編程能力，從解決計(jì)算機(jī)科學(xué)和應(yīng)用中經(jīng)典的漢諾塔問題入手，分析了分治算法與遞歸算法的關(guān)系，分別給出了分治算法、遞歸算法的設(shè)計(jì)步驟，給出了分治法的時(shí)間復(fù)雜度計(jì)算公式和求解方法。深入分析了漢諾塔問題的簡化過程、分解步驟，設(shè)計(jì)了漢諾塔算法，給出了完成漢諾塔搬遷需要移動(dòng)盤子次數(shù)的計(jì)算公式和求解方法。使學(xué)生能夠把所學(xué)的方法用于解決具體問題，并對(duì)算法進(jìn)行比較分析，從而將理論和實(shí)際應(yīng)用切實(shí)結(jié)合起來。

關(guān)鍵詞： 漢諾塔； 時(shí)間復(fù)雜度； 遞歸方法； 分治算法

中圖分類號(hào)：TP302 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2015）08-49-03

Analysis and design of Hanoi tower algorithm

Ma Jianzhe

（School of Information Engineering， Taiyuan University of Technology， Taiyuan， Shanxi 030024， China）

Abstract： In order to improve the students' ability of programming， starting with the classic Hanoi tower problem in computer science and application， this paper analyzes the relationship between the divide-and-conquer algorithm and the recursive algorithm， gives the design steps of the divide-and-conquer algorithm and the recursive algorithm respectively， gives the calculation formula and the solving method of the time complexity for the divide-and-conquer algorithm， deeply analyzes the simplification process and the decomposition steps of Hanoi tower problem， designs the algorithm for Hanoi tower problem， and gives the calculation formula and the solving method to work out the number of movements required to complete relocation of Hanoi tower. Student can use the method learnt to solve the specific problems， thereby combine theory with practical application.

Key words： Hanoi tower； time complexity； recursive method； divide-and-conquer algorithm

0 引言

任何一個(gè)可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問題規(guī)模越小，解題所需的計(jì)算時(shí)間往往也越少，計(jì)算也越容易。要解決一個(gè)較大的問題，有時(shí)是相當(dāng)困難的。分治策略是應(yīng)用最多的一種有效方法，它的基本思想是將問題分解成若干個(gè)子問題，然后求解子問題。子問題較原問題無疑是會(huì)容易些，由此得出原問題的解，就是所謂的“分而治之”的意思。分治策略還可以遞歸，即子問題仍然可以用分治策略來處理，最后的問題非?；径液唵蝃1-2]。

分治的基本思想是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。找出各部分的解，然后把各部分的解組合成整個(gè)問題的解。實(shí)現(xiàn)算法的同時(shí)，需要估計(jì)算法所需時(shí)間。分治算法在每一層遞歸上分為三個(gè)步驟。

⑴ 分：將原問題分解成一系列子問題。

⑵ 治：遞歸地解各子問題，若子問題足夠小，則直接解之。

⑶ 合：將子問題的結(jié)果合并成原問題的解。

分治算法的時(shí)間由解決各個(gè)子問題所需的時(shí)間（由子問題的個(gè)數(shù)、解決每個(gè)子問題的時(shí)間決定）確定。

由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。

在C語言中，重復(fù)性操作可以通過循環(huán)結(jié)構(gòu)或者遞歸結(jié)構(gòu)完成。遞歸結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便[3-5]。

從遞歸算法的結(jié)構(gòu)來分析，設(shè)計(jì)遞歸算法時(shí)，無非要解決兩個(gè)問題：遞歸出口和遞歸體。即要確定何時(shí)到達(dá)遞歸出口，何時(shí)執(zhí)行遞歸體，執(zhí)行什么樣的遞歸體。遞歸算法設(shè)計(jì)的關(guān)鍵是保存每一層的局部變量并運(yùn)用這些局部變量。由此，遞歸算法的設(shè)計(jì)步驟可從以下三步來進(jìn)行：

⑴ 分析問題，分解出小問題；

⑵ 找出小問題與大問題之間的關(guān)系，確定遞歸出口；

⑶ 寫出算法。

評(píng)定算法優(yōu)劣的標(biāo)準(zhǔn)要看它的時(shí)間復(fù)雜性、空間復(fù)雜性和人工復(fù)雜性，其中時(shí)間復(fù)雜性最為重要，通常是用時(shí)間復(fù)雜性來衡量某個(gè)算法的“好”或“壞”。不同的算法具有不同的時(shí)間復(fù)雜性函數(shù)，說它們當(dāng)中哪些“效率足夠高”，哪些“效率太低”，總要看當(dāng)時(shí)的情況。但是，計(jì)算機(jī)科學(xué)家公認(rèn)一種簡單的區(qū)別，這種區(qū)別對(duì)這些問題提供了重要的透徹的分析，這就是多頂式時(shí)間算法和非多頂式時(shí)間算法之間的區(qū)別。時(shí)間復(fù)雜性表示成n的函數(shù)T（n）。凡是T（n）為n的對(duì)數(shù)函數(shù)、線性函數(shù)或多項(xiàng)式的冪函數(shù)（也是多項(xiàng)式的特例），稱這類算法為“有效算法”，或好的算法；反之，凡是T（n）為指數(shù)函數(shù)或階乘函數(shù)的，稱之為壞的算法。

1 分治法的時(shí)間復(fù)雜度分析

從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的算法一般是遞歸算法。因此，分治法的計(jì)算效率通?？梢杂眠f歸方程來進(jìn)行分析。一個(gè)分治法將規(guī)模為n的問題分成k個(gè)規(guī)模為n/m的子問題去解。為方便起見，設(shè)解規(guī)模為1的問題耗費(fèi)1個(gè)單位時(shí)間。另外，再設(shè)將原問題分解為k個(gè)子問題以及將k個(gè)子問題的解合并為原問題的解需用f（n）個(gè)單位時(shí)間。如果用T（n）表示該分治法解規(guī)模為|P|=n的問題所需的計(jì)算時(shí)間，則時(shí)間復(fù)雜度T（n）為：

下面討論如何求解這個(gè)與分治法有密切關(guān)系的遞歸方程。通常可以用展開遞歸式的方法來解這類遞歸方程，反復(fù)代入求解，解此遞歸方程可得時(shí)間復(fù)雜度T（n）。從目標(biāo)（要解決的問題）出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個(gè)平凡的本原問題集合。

2 漢諾塔算法設(shè)計(jì)與分析

相傳印度教的天神梵天在創(chuàng)造地球這一世界時(shí)，建了一座神廟，神廟里豎有三根寶石柱子，柱子由一個(gè)銅座支撐。梵天將64個(gè)直徑大小不一的金盤子，按照從大到小的順序依次套放在第一根柱子上，形成一座金塔，即所謂的漢諾塔（又稱Hanoi塔）。天神讓廟里的僧侶們將第一根柱子上的64個(gè)盤子借助第二根柱子全部移到第三根柱子上，即將整個(gè)塔遷移，同時(shí)定下三條規(guī)則：

⑴ 每次只能移動(dòng)一個(gè)盤子；

⑵ 盤子只能在三根柱子上來回移動(dòng)，不能放在他處；

⑶ 在移動(dòng)過程中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。

天神說：“當(dāng)這64個(gè)盤子全部移到第三根柱子上后，世界末日就要到了”。這就是著名的漢諾塔問題。用計(jì)算機(jī)求解一個(gè)實(shí)際問題，首先要從這個(gè)實(shí)際問題中抽象出一個(gè)數(shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，最后根據(jù)算法編寫程序，調(diào)試、編譯、連接和運(yùn)行，從而形成該問題的求解。圖1給出了求解n個(gè)圓盤難題的總體求解過程。其漢諾塔問題的算法為：

⑴ 遞歸調(diào)用n-1個(gè)圓盤的漢諾塔問題算法，把上面的n-1個(gè)圓盤從A柱移到B柱；

⑵ 把最下面的一個(gè)圓盤從A柱直接移到C柱；

⑶ 遞歸調(diào)用n-1個(gè)圓盤的漢諾塔問題算法，把B柱上臨時(shí)存放的n-1個(gè)圓盤移到C柱。

圖1 n個(gè)圓盤難題總體求解過程

漢諾塔問題是一個(gè)典型的只有用遞歸方法（而不能用其他方法）來解決的問題。根據(jù)遞歸方法，可發(fā)現(xiàn)將64個(gè)盤子的漢諾塔問題轉(zhuǎn)化為求解63個(gè)盤子先移動(dòng)到第二個(gè)柱子上，再將最后一個(gè)盤子直接移動(dòng)到第三個(gè)柱子上，最后又一次將63個(gè)盤子從第二個(gè)柱子移動(dòng)到第三個(gè)柱子上，這樣則可以解決64個(gè)盤子的漢諾塔問題。依此類推，63個(gè)盤子的漢諾塔求解問題可以轉(zhuǎn)化為62個(gè)盤子的漢諾塔求解問題，62個(gè)盤子的漢諾塔求解問題又可以轉(zhuǎn)化為61個(gè)盤子的漢諾塔求解問題，直到1個(gè)盤子的漢諾塔求解問題。再由1個(gè)盤子的漢諾塔的求解求出2個(gè)盤子的漢諾塔，直到解出64個(gè)盤子的漢諾塔問題。圖2給出了漢諾塔算法的程序流程圖。

[n==1？][開始][輸入盤子的數(shù)量n][調(diào)用遞歸函數(shù)hanoi（）][調(diào)用move（）函數(shù)

將盤子從A移到C][將前n-1個(gè)盤子

從A移到B][再將A的第n個(gè)

盤子移動(dòng)到C][最后將B上的n-1個(gè)

盤子移到C上] [Y][N] [結(jié)束]

圖2 漢諾塔算法程序流程圖

下面利用C語言給出該問題的求解算法的描述。

hanoi（int n，char left，char middle，char right）

{ if（n==1） move（1，one，_，three）；

else

{ hanoi（n-1，left，right，middle）；

move（1，left，_，right）；

hanoi（n-1，middle，left，right）；

}

}

以上代碼中，n表示n個(gè)盤子的漢諾塔問題，left表示第一個(gè)柱子，middle表示第二個(gè)柱子，right表示第三個(gè)柱子。函數(shù)hanoi（n-1，left，right，middle）表示n-1階漢諾塔從第一個(gè)柱子借助第三個(gè)柱子先移到第二個(gè)柱子上，函數(shù)move（1，left，_，right）表示將第一個(gè)柱子上最后一個(gè)盤子直接放到第三個(gè)柱子上，函數(shù)hanoi（n-1，middle，left，right）表示n-1個(gè)盤子借助第一個(gè)柱子移到第三個(gè)柱子上。在以上C語言描述的算法基礎(chǔ)上，進(jìn)行適當(dāng)擴(kuò)充就可以形成一個(gè)完整的程序，經(jīng)過編譯和連接后，計(jì)算機(jī)就可以執(zhí)行這個(gè)程序，按照遞歸的方法將問題求解出來。

現(xiàn)在的問題是當(dāng)n=64時(shí)，即有64個(gè)盤子時(shí)，需要移動(dòng)多少次盤子，要用多少時(shí)間。按照上面的算法，n個(gè)盤子的漢諾塔問題需要移動(dòng)的盤子數(shù)是n-1個(gè)盤子的漢諾塔問題需要移動(dòng)的盤子數(shù)的2倍加1。于是

h（n）=2h（n-1）+1

=2（2h（n-2）+1）+1=22h（n-2）+2+1

=23h（n-3）+22+2+1

……

=2nh（0）+2n-1+…+22+2+1

=2n-1+…+22+2+1=2n-1

因此，要完成漢諾塔的搬遷，需要移動(dòng)盤子的次數(shù)為：

2n-1=18446744073709551615

如果每秒移動(dòng)一次，一年有31536000秒，則僧侶們一刻不停地來回搬動(dòng)，也需要花費(fèi)5849億年的時(shí)間。假定計(jì)算機(jī)以每秒1000萬個(gè)盤子的速度進(jìn)行搬遷，則需要花費(fèi)大約58490年的時(shí)間。從這個(gè)例子可以了解到理論上可以計(jì)算的問題，而實(shí)際上并不一定能行，這屬于算法復(fù)雜性方面的研究內(nèi)容。

圖3給出了Hanoi塔問題3圓盤難題的運(yùn)行結(jié)果，可以看到，將3個(gè)盤子從第一個(gè)柱子移動(dòng)到第三個(gè)柱子需要移動(dòng)7次。對(duì)上述遞歸在Hanoi塔問題上的應(yīng)用分析，如果將64個(gè)盤子從第一個(gè)柱子移動(dòng)到第三個(gè)柱子需要移動(dòng)264-1次。