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

馬健喆

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

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

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

⑴ 分：將原問(wèn)題分解成一系列子問(wèn)題。

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

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

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

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

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

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

⑴ 分析問(wèn)題，分解出小問(wèn)題；

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

⑶ 寫出算法。

評(píng)定算法優(yōu)劣的標(biāo)準(zhǔn)要看它的時(shí)間復(fù)雜性、空間復(fù)雜性和人工復(fù)雜性，其中時(shí)間復(fù)雜性最為重要，通常是用時(shí)間復(fù)雜性來(lái)衡量某個(gè)算法的“好”或“壞”。不同的算法具有不同的時(shí)間復(fù)雜性函數(shù)，說(shuō)它們當(dāng)中哪些“效率足夠高”，哪些“效率太低”，總要看當(dāng)時(shí)的情況。但是，計(jì)算機(jī)科學(xué)家公認(rèn)一種簡(jiǎn)單的區(qū)別，這種區(qū)別對(duì)這些問(wèn)題提供了重要的透徹的分析，這就是多頂式時(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歸方程來(lái)進(jìn)行分析。一個(gè)分治法將規(guī)模為n的問(wèn)題分成k個(gè)規(guī)模為n/m的子問(wèn)題去解。為方便起見，設(shè)解規(guī)模為1的問(wèn)題耗費(fèi)1個(gè)單位時(shí)間。另外，再設(shè)將原問(wèn)題分解為k個(gè)子問(wèn)題以及將k個(gè)子問(wèn)題的解合并為原問(wèn)題的解需用f（n）個(gè)單位時(shí)間。如果用T（n）表示該分治法解規(guī)模為|P|=n的問(wèn)題所需的計(jì)算時(shí)間，則時(shí)間復(fù)雜度T（n）為：

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

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

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

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

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

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

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

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

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

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

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

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

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è)盤子的漢諾塔問(wèn)題，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語(yǔ)言描述的算法基礎(chǔ)上，進(jìn)行適當(dāng)擴(kuò)充就可以形成一個(gè)完整的程序，經(jīng)過(guò)編譯和連接后，計(jì)算機(jī)就可以執(zhí)行這個(gè)程序，按照遞歸的方法將問(wèn)題求解出來(lái)。

現(xiàn)在的問(wèn)題是當(dāng)n=64時(shí)，即有64個(gè)盤子時(shí)，需要移動(dòng)多少次盤子，要用多少時(shí)間。按照上面的算法，n個(gè)盤子的漢諾塔問(wèn)題需要移動(dòng)的盤子數(shù)是n-1個(gè)盤子的漢諾塔問(wèn)題需要移動(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秒，則僧侶們一刻不停地來(lái)回搬動(dòng)，也需要花費(fèi)5849億年的時(shí)間。假定計(jì)算機(jī)以每秒1000萬(wàn)個(gè)盤子的速度進(jìn)行搬遷，則需要花費(fèi)大約58490年的時(shí)間。從這個(gè)例子可以了解到理論上可以計(jì)算的問(wèn)題，而實(shí)際上并不一定能行，這屬于算法復(fù)雜性方面的研究?jī)?nèi)容。

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