漢諾塔算法的分析與設計

馬健喆

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

關鍵詞： 漢諾塔； 時間復雜度； 遞歸方法； 分治算法

中圖分類號：TP302 文獻標志碼：A 文章編號：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 引言

任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題規模越小，解題所需的計算時間往往也越少，計算也越容易。要解決一個較大的問題，有時是相當困難的。分治策略是應用最多的一種有效方法，它的基本思想是將問題分解成若干個子問題，然后求解子問題。子問題較原問題無疑是會容易些，由此得出原問題的解，就是所謂的“分而治之”的意思。分治策略還可以遞歸，即子問題仍然可以用分治策略來處理，最后的問題非常基本而且簡單[1-2]。

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

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

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

⑶ 合：將子問題的結果合并成原問題的解。

分治算法的時間由解決各個子問題所需的時間（由子問題的個數、解決每個子問題的時間決定）確定。

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

在C語言中，重復性操作可以通過循環結構或者遞歸結構完成。遞歸結構清晰，可讀性強，而且容易用數學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便[3-5]。

從遞歸算法的結構來分析，設計遞歸算法時，無非要解決兩個問題：遞歸出口和遞歸體。即要確定何時到達遞歸出口，何時執行遞歸體，執行什么樣的遞歸體。遞歸算法設計的關鍵是保存每一層的局部變量并運用這些局部變量。由此，遞歸算法的設計步驟可從以下三步來進行：

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

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

⑶ 寫出算法。

評定算法優劣的標準要看它的時間復雜性、空間復雜性和人工復雜性，其中時間復雜性最為重要，通常是用時間復雜性來衡量某個算法的“好”或“壞”。不同的算法具有不同的時間復雜性函數，說它們當中哪些“效率足夠高”，哪些“效率太低”，總要看當時的情況。但是，計算機科學家公認一種簡單的區別，這種區別對這些問題提供了重要的透徹的分析，這就是多頂式時間算法和非多頂式時間算法之間的區別。時間復雜性表示成n的函數T（n）。凡是T（n）為n的對數函數、線性函數或多項式的冪函數（也是多項式的特例），稱這類算法為“有效算法”，或好的算法；反之，凡是T（n）為指數函數或階乘函數的，稱之為壞的算法。

1 分治法的時間復雜度分析

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

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

2 漢諾塔算法設計與分析

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

⑴ 每次只能移動一個盤子；

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

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

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

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

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

⑶ 遞歸調用n-1個圓盤的漢諾塔問題算法，把B柱上臨時存放的n-1個圓盤移到C柱。

圖1 n個圓盤難題總體求解過程

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

[n==1？][開始][輸入盤子的數量n][調用遞歸函數hanoi（）][調用move（）函數

將盤子從A移到C][將前n-1個盤子

從A移到B][再將A的第n個

盤子移動到C][最后將B上的n-1個

盤子移到C上] [Y][N] [結束]

圖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個盤子的漢諾塔問題，left表示第一個柱子，middle表示第二個柱子，right表示第三個柱子。函數hanoi（n-1，left，right，middle）表示n-1階漢諾塔從第一個柱子借助第三個柱子先移到第二個柱子上，函數move（1，left，_，right）表示將第一個柱子上最后一個盤子直接放到第三個柱子上，函數hanoi（n-1，middle，left，right）表示n-1個盤子借助第一個柱子移到第三個柱子上。在以上C語言描述的算法基礎上，進行適當擴充就可以形成一個完整的程序，經過編譯和連接后，計算機就可以執行這個程序，按照遞歸的方法將問題求解出來。

現在的問題是當n=64時，即有64個盤子時，需要移動多少次盤子，要用多少時間。按照上面的算法，n個盤子的漢諾塔問題需要移動的盤子數是n-1個盤子的漢諾塔問題需要移動的盤子數的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

因此，要完成漢諾塔的搬遷，需要移動盤子的次數為：

2n-1=18446744073709551615

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

圖3給出了Hanoi塔問題3圓盤難題的運行結果，可以看到，將3個盤子從第一個柱子移動到第三個柱子需要移動7次。對上述遞歸在Hanoi塔問題上的應用分析，如果將64個盤子從第一個柱子移動到第三個柱子需要移動264-1次。