漢諾塔問題研究

摘 要: 漢諾塔問題作為一個古老的傳說，號稱世界十大最難游戲之一，是遞歸最為典型的例子。本文通過遞歸推理、探究其遞推數列，總結出各柱子的奇偶盤子數目搬運規律，進而重點分析和研究了雙色Hanoi塔問題，根據分析研究結果，得出結論:無論是出發還是過渡或目標柱子，柱子上始終不會出現同色盤子疊加，完全符合基本漢諾塔搬運規則。

關鍵詞: 漢諾塔 遞歸 雙色 Free Pascal

1.引言

漢諾塔(Tower of Hanoi)問題[1]起源于這樣一段故事:在創世紀時，Benare有一座波羅教塔，由三根鉆石柱子支撐，神在第一根柱子上放置了64枚上小下大依次排列的金盤子，令門徒將所有的金盤子從第一根柱子可經第二根移至第三根柱子上，且搬運過程中遵守上小下大的原則，若每天只搬運一枚金盤子，當金盤子全部搬運完畢之時，此塔將會毀滅，就是世界末日來臨之時。

遞歸關系[2]作為數學與計算機科學的一個重要研究對象，特別是在算法分析中有著廣泛的應用。Hanoi塔問題直觀地演示了遞歸過程。本文將從標準Hanoi塔問題出發，通過遞歸推理、探究其遞推數列，總結出各柱子的奇偶盤子數目移動規律，以發散性思維深入研究了雙色Hanoi塔問題并得出相應結論。

2.標準Hanoi 塔問題

n個大小不一的圓盤依半徑的大小，從下而上地套在柱子A上。如圖1所示，現在要將n個圓盤借助B從柱子A上全部轉移到柱子C[3]。在移動圓盤時遵循以下條件:

條件1:每次只允許移動一個圓盤;

條件2:在轉移過程中不允許出現大圓盤放在小圓盤上。

條件3:在滿足移動規則(1)—(2)的前提下，可將圓盤移至A，B，C中任一個柱子上。

圖1 Hanoi問題

試設計一個算法，用最少的移動次數將塔座A上的n個圓盤移到塔座C上，并仍按同樣順序疊置。

2.1遞歸算法

初始A柱上有n個盤子，以下從n=1逐步分析推理n在不同情況下的操作步驟:

當n=1時:將盤子從A柱直接移到C柱，完成移動，即(A→C)。

當n=2時:先把n-1=1個盤子從A柱移動到B柱，再將A柱上最后一個盤子從A柱移動到C柱，最后將B柱上的n—1個盤子從B柱移動到C柱上，完成移動，即A→B，A→C，B→C。

當n=3時:先把n-1=2個盤子從A柱移動到B柱(借助C)，再將B柱上剩余的盤子移動到C柱(借助A)。

當n為任意正整數時:同樣是先把n-1個盤子從A柱移動到B柱(借助C)，方法與上述相同。

通過以上分析，Hanoi問題是典型的利用遞歸來解決的，是將規模為n的問題，降解為規模為n-1的小問題、n-2的較小問題……依次降解，直到遞歸出口，求出最低階規模的解，代入高一階問題中，直至求出規模為n的問題的解。遞歸包括回溯和遞推兩個過程。

2.2遞推數列

為了分辨n個不同的盤子，將其由小到大依序編號為1，2，3，…，n-1，n，以便于研究其所需的移動次數及次序、探求其規則性。

從n=1、n=2的移動情況，可歸納出一個結論:即n=2時處理n=1兩次，共須移動22-1=3步，其Hanoi數列為121。同理可知n=3時，處理n=2兩次，共須移動23-1=7步，其Hanoi數列為1213121，同理可知n=4時，處理n=3兩次，總共須移動24-1=15步，其漢諾塔數列為121312141213121，依此類推。

分析得出遞歸模型:

f(1)=1 (n=1)f(n)=2×f(n-1)+1 (n>1)

f(n)=2×f(n-1)+1

=2×(2×f(n-2)+1)+1

=2×(2×(2×f(n-3)+1)+1)+1

……

因此，n個盤子總共需移動最少步數計算公式為:f(n)=2n-1。

2.3盤子總數奇偶性分析

圓盤總數n存在兩種情況，即n為奇數和n為偶數。下面對這兩種情況進行分析。

搬運總數n為奇數1時，最小編號為1的盤子，直接從A移動到目標C柱上，為3時，1號盤子同樣移動到目標C柱上，2號盤子移動到過渡B柱上，1號盤子再移動到相對于1號盤子的目標柱子:過渡B柱上，3號盤子直接移動到目標C柱上，過渡B柱上有1和2號盤子為偶數，將1號盤子移動到過渡A柱上，2號盤子直接移動到目標C柱上，再把1號盤子移動到目標C柱上……

搬運總數n為偶數2時，最小編號為1的盤子，先從A移動到過渡B柱上，再把2號盤子移動到目標C柱上，為4時，1號盤子同樣移動到過渡B柱上，A柱上剩余3個盤子，同上述奇數理:2號盤子移動到目標C柱上，1號盤子再移動到目標C柱子，A柱上剩余2個盤子，偶數:3號盤子移動到過渡B柱上，同理1、2號盤子經A柱過渡移動到B柱上，4號盤子直接移動到目標C柱上，過渡B柱上有1、2、3號盤子為奇數，此時A柱為過渡柱子，按奇數原理，再將1、2、3號盤子分別移動到目標C柱上……

由上述分析可知:當n為偶數時，最上層小盤子首先移動到過渡柱上，為奇數時最上層小盤子首先移動到目標柱上，只有按此規律移動，才能得出最少的移動步數。

同時可知:不論n為奇偶，過渡和目標柱上，盤子的疊加編號始終是奇偶疊加，不會出現奇數或偶數連續疊加。

3.雙色Hanoi問題

n個大小不一的圓盤依半徑的大小，從下而上地套在柱子A上。這些圓盤從小到大編號為1，2，…，n，奇數號圓盤著紅色，偶數號圓盤著藍色，如圖2所示。現在要將n個圓盤借助C從柱子A上全部轉移到柱子B，并仍按同樣順序疊置。在移動圓盤時應遵循以下條件:

條件1:每次只允許移動一個圓盤;

條件2:在轉移過程中不允許出現大圓盤放在小圓盤上;

條件3:在轉移過程中任何時刻都不允許將同色圓盤疊在一起;

條件4:在滿足移動規則(1)—(3)的前提下，可將圓盤移至A，B，C中任一柱子上。

圖2 雙色Hanoi問題

試設計一個算法，用最少的移動次數將塔座A上的n個圓盤移到塔座B上，并仍按同樣順序疊置。

3.1問題分析

該問題的關鍵在于規則(3):任何時刻都不允許將同色圓盤疊在一起，只有證明了在移動過渡過程中，不會出現同色圓盤疊在一起的情況即可。

經過以上奇偶異同分析可知，當出發柱子A為奇數個盤子時;最上與最下層顏色為紅色，過渡柱子C有偶數個盤子，且最底層為藍色;最上層位紅色，目標B柱子最底層為紅色，A柱子最上層顏色為奇數-(奇數+偶數)=偶數→藍色，過渡柱子C上的偶數個盤子，移動時就變成出發柱子，A柱變成過渡柱子且疊加的第一個盤子為紅色，目標柱子疊加的是藍色。以此類推，不會出現同色疊加。

同理，當出發柱子A為偶數個盤子時，最上層為紅色、最底層為藍色，過度柱子C有奇數個盤子，且最上、最底層為紅色，目標B柱子最底層為藍色，A柱子最上層顏色為偶數-(奇數+奇數)=偶數→藍色，過渡柱子C上的奇數個盤子，移動時就變成出發柱子，A柱變成過度柱子且疊加的第一個盤子為藍色，目標柱子疊加的是紅色。以此類推，同樣不會出現同色疊加的情況。

經過以上奇偶性分析研究，雙色Hanoi塔問題完全符合基本漢諾塔算法規則。

3.2程序實現與結果分析

按照上述分析，對該問題用競賽語言Free Pascal[4]來實現得出結果如表1。

表1圓盤搬運步驟

從輸出結果可以看出，A，B，C三根柱子，無論是出發還是過渡或目標柱子，柱子上始終不會出現同色疊加，與標準Hanoi問題的搬運方法完全相同。可見，雙色只是一種迷霧，只有撥開烏云，才能見彩虹。

4.結語

本文從標準Hanoi問題出發，通過遞歸推理給出了解決該問題的解法。同時分類對圓盤子總數n的奇偶性進行分析，從而揭示了雙色Hanoi問題的實質，即雙色Hanoi問題與標準Hanoi問題本質完全相同。最后使用競賽語言Free Pascal對其進行編程實現進一步證實了該理論。

參考文獻:

[1]王善發，吳道榮.討論Hanoi塔問題[J].保山師專學報.2008，VOL27，(2):74-77.

[2]嚴蔚敏，吳偉明.數據結構[M].北京:清華大學出版社，2005.

[3]王曉東.算法設計與分析[M].北京:清華大學出版社，2008.

[4]張長海.PASCAL語言程序設計[M].北京:電子工業出版社，2001.