戴莉萍，黃龍軍，劉清華

(江西師范大學(xué)　軟件學(xué)院，南昌　330022)

?

自底向上記錄式Hanoi塔非遞歸算法

戴莉萍，黃龍軍，劉清華

(江西師范大學(xué)軟件學(xué)院，南昌330022)

Hanoi塔問題的經(jīng)典遞歸算法雖然代碼量小，但時間復(fù)雜度卻是指數(shù)級的，而且難以理解。該文基于Hanoi塔問題的遞歸思想，構(gòu)造出Hanoi塔的樹模型，仔細(xì)分析遞歸函數(shù)的調(diào)用參數(shù)和語句執(zhí)行時盤子移動的順序，巧妙地找到兩者之間的對應(yīng)關(guān)系，從而提出一種新的自底向上非遞歸算法。該算法逐一地記錄下n從1開始時盤子從源柱到目標(biāo)柱時經(jīng)歷過的移動軌跡，進(jìn)而直接應(yīng)用到n+1個盤子的移動問題。實驗結(jié)果表明，該算法對應(yīng)的代碼易讀且高效，時間復(fù)雜度降為O(n)，是對Hanoi塔問題的非遞歸算法研究的進(jìn)一步實踐與探討。

Hanoi塔問題；自底向上記錄式；非遞歸算法；目標(biāo)柱

許多有趣的數(shù)學(xué)問題都是計算機(jī)算法所研究和解決的對象，如Fibonacci問題、水仙花問題、Hanoi塔(漢諾塔)問題等，其中Hanoi塔問題更為復(fù)雜和有趣。Hanoi塔問題本身是一個數(shù)學(xué)游戲，它由3根柱子和一堆可擺放在不同柱上的大小不一的盤子組成。最初所有盤子按照尺寸大小順序地被放置在一根柱子上，最大的盤子在最下面，最小的盤子在最上面，從而形成一個圓錐形狀。游戲的結(jié)果是將所有的盤子移動到另一根柱子上，移動過程中的規(guī)則是：1)每次只能移動一個盤子；2)每次將一根柱子上面的盤子移動到另一根柱子的上面，即只有某根柱子最上面的盤子才可以移動；3)大盤子不能放置在小盤子之上。3個盤子需要移動7次，n個盤子最少需要移動2n-1次[1]。

目前為止，已經(jīng)有很多種算法來解決Hanoi問題[1-4]，最為經(jīng)典的是遞歸算法，每種解決方法各有著重點。本文通過分析參數(shù)賦值順序與盤子的移動順序找出其中對應(yīng)的規(guī)律，提出一種自底向上記錄式的Hanoi塔非遞歸算法，使復(fù)雜的Hanoi塔問題在解決過程中變得更加簡單直接。最終實現(xiàn)的代碼短而精，易于理解，極大提高了執(zhí)行速度。

1　Hanoi塔遞歸算法中的移動規(guī)律

解決Hanoi塔問題著名而經(jīng)典的算法就是遞歸算法。設(shè)有A，B，C共3根柱子，開始時在A柱上疊有n個盤子，盤子從小到大編號為1，2，…，n，現(xiàn)在要求將A柱上的所有盤子移到C柱上。其基本思想是：1個盤子的Hanoi塔問題可直接移動；n個盤子的Hanoi塔問題可遞歸表示為首先把上邊的n-1個盤子從A柱移到B柱，然后把最下邊的一個盤子從A柱移到C柱，最后把移到B柱的n-1個盤子再移到C柱。由此可見，n個盤子的移動問題可以分為兩次n-1個盤子的移動問題，這又可以遞歸地用上述方法來做，因此可以設(shè)計出Hanoi塔問題的遞歸算法[5]。

下面的函數(shù)Hanoi(int n，charA，charC，charB)表示需要將n個盤子從柱子A移動到柱子C，期間可借助柱子B。圖1是Hanoi塔問題示意圖。

圖1　Hanoi塔模型

Hnaoi塔遞歸算法表示如下:

voidHanoi(inti，charA，charC，charB)

{

if (i==1)move(A，i，C)-遞歸調(diào)用的出口

else

{

--兩次遞歸調(diào)用自身函數(shù)

Hanoi(i-1，A，B，C);

Move(A，i，C);

Hanoi(i-1，B，C，A);

}

}

從代碼組成以及遞歸調(diào)用的過程可以看出盤子移動步驟可以表示為一棵二叉樹結(jié)構(gòu)，而且移動過程正好是二叉樹的中序遍歷，2個盤子和3個盤子的執(zhí)行順序，如圖2和圖3所示。

圖2　(n=2)時盤子移動過程

圖3　(n=3)時盤子移動過程

現(xiàn)在來分析一下移動n個盤子所需要的移動次數(shù)f(n)：根據(jù)Hanoi塔遞歸算法中的步驟，可以發(fā)現(xiàn)f(n)=2f(n-1)+1，解此遞歸關(guān)系可以得出f(n)=2n-1。

根據(jù)二叉樹的性質(zhì)可以發(fā)現(xiàn)結(jié)果剛好等于深度為n的滿二叉樹所具有的結(jié)點數(shù)。這樣的時間復(fù)雜度是非常大的。

現(xiàn)在來分析一下在遞歸調(diào)用和盤子移動之間是否存在一定的規(guī)律性。在圖2中，n=2時Hanoi(2，A，C，B)盤子的移動順序可以表示為1AB2AC1BC，其中1AB表示編號為1的盤子從A柱移動到B柱。在圖3中，樹左邊n=2時Hanoi(2，A，B，C)盤子的移動順序為1AC2AB1CB，樹右邊n=2時Hanoi(2，B，C，A)盤子的移動順序為1BA2BC1AC。這兩個圖中n=2時的參數(shù)位置和移動位置的相對關(guān)系，如圖4所示。

圖4　n=2時，函數(shù)參數(shù)位置與移動位置

從圖4可以看出函數(shù)傳遞參數(shù)的位置和移動位置存在一定的規(guī)律性，即函數(shù)中同一位置上的傳遞參數(shù)無論是什么，該參數(shù)在移動過程中出現(xiàn)的位置總是固定的，這里忽略盤子的編號數(shù)。例如Hanoi函數(shù)中傳遞的第1個參數(shù)arg1始終出現(xiàn)移動過程中的第1和第3位置；參數(shù)2即arg2出現(xiàn)在移動過程中的第4和第6的位置，參數(shù)3即arg3出現(xiàn)在移動過程中的第2和第5的位置。這樣，只要知道n-1個盤子的移動過程，則在求n個盤子移動過程時，就可直接利用n-1個盤子的移動規(guī)律，通過相應(yīng)的參數(shù)替換功能即可得到答案。下面舉例說明。

已知n=2時從源柱A到目標(biāo)柱子C的移動過程:

Hanoi(2，A，C，B)=Hanoi(2，arg1，arg2，arg3)

=’1AB2AC1BC’

=’1 arg1 arg3 2 arg1 arg2 1 arg3 arg2’

求n=3時前2個盤子的先后移動過程:

Hanoi(2，A，B，C)=Hanoi(2，arg1，arg2，arg3)

=’1 arg1 arg3 2 arg1 arg2 1 arg3 arg2’

=’1AC2AB1CB’

Hanoi (2，B，C，A)=Hanoi(2，arg1，arg2，arg3)

=’1 arg1 arg3 2 arg1 arg2 1 arg3 arg2’

=’1BA2BC1AC’

在求取Hanoi(2，A，B，C)或Hanoi(2，B，C，A)時，可以不需要再進(jìn)行遞歸調(diào)用，而是直接利用’1AB2AC1BC’的結(jié)果，將對應(yīng)的移動軌跡轉(zhuǎn)換成對應(yīng)的函數(shù)傳遞參數(shù)即可。

2　記錄式Hanoi塔非遞歸算法描述

盡管Hanoi塔的遞歸技術(shù)能利用系統(tǒng)內(nèi)部功能自動實現(xiàn)調(diào)用過程中信息的保存與恢復(fù)，省略了程序設(shè)計中的許多細(xì)節(jié)操作，簡化了程序設(shè)計過程，但仍然存在一些問題，如運(yùn)行效率較低，遞歸內(nèi)部的實現(xiàn)原理比較難理解，程序閱讀較為困難，因此，為消除算法的遞歸調(diào)用，大大節(jié)省運(yùn)行時間，增強(qiáng)程序的可讀性，提出了記錄式Hanoi塔的非遞歸算法。

利用函數(shù)的參數(shù)位置和移動位置的對應(yīng)關(guān)系，可以自底向上逐步求取并記錄下當(dāng)盤子數(shù)i=1，2，…，n時從源柱A到目標(biāo)柱C期間所有各個盤子移動的順序和位置，從而將遞歸算法自頂向下產(chǎn)生的各個子問題求解過程直接轉(zhuǎn)換為循環(huán)非遞歸求解過程，算法復(fù)雜性大大降低了，時間復(fù)雜度得到了很好的改善。當(dāng)n=3時自底向上記錄式非遞歸算法過程如圖5所示。

圖5　n=3時，記錄式算法的計算過程

從圖5可以看出，要求取3個盤子從A到C的移動過程：首先得到1個盤子從A到C的移動過程；再求得2個盤子從A到C的移動過程，期間利用1個盤子的移動軌跡，根據(jù)參數(shù)位置改變移動軌跡的相應(yīng)值；最后利用2個盤子的移動軌跡和傳遞參數(shù)替換得到3個盤子的最終移動結(jié)果。

下面是自底向上記錄式的Hanoi塔非遞歸算法偽碼表示。其中字符串變量result保存的就是前n-1個盤子從A柱到C柱所經(jīng)歷的盤子移動次序。HanoiRecord函數(shù)的主體部分仍與遞歸算法過程類似，只不過不要遞歸調(diào)用，而是采用循環(huán)，并直接通過HanoiReplace函數(shù)獲取移動值。HanoiReplace函數(shù)中第1個參數(shù)表示當(dāng)前盤子的個數(shù)，第2個參數(shù)表示當(dāng)前所在柱，第3個參數(shù)表示當(dāng)前目的柱，第4個參數(shù)表示當(dāng)前輔助柱，第5個參數(shù)表示當(dāng)前盤子數(shù)從A到C的已知移動軌跡。HanoiReplace函數(shù)主要的功能就是將result改成符合當(dāng)前移動要求的順序，簡單來說就是替換。

輸入:盤子個數(shù)n，起始柱A，目的柱C，輔助柱B

輸出:結(jié)果字符串result

過程:

HanoiRecord(intn，charA，charC，charB)

{

if (n==1) result=’1AC’;

else

for (i=2;i<=n;i++)

{

firststep=HanoiReplace(i-1，A，B，C，result);

secondstep=str(i)+”AC’;//i變?yōu)樽址?/p>

laststep=HanoiReplace(i-1，B，C，A，result);

result=firststep+secondstep+laststep;

}

}

當(dāng)n=1時，result變量直接賦值，這也是result的初始值，在計算n=2時盤子的移動過程會使用到它。firsttep是字符串變量，保存著前i-1個盤子從源柱A移動到輔助柱B經(jīng)歷的移動順序，在這里輔助柱B相當(dāng)于就是當(dāng)前的目標(biāo)柱了，求取過程中需要利用已知的前i-1個盤子從源柱A到目標(biāo)柱C時移動軌跡的字符串result，然后加以參數(shù)替換。secondstep也是字符串變量，直接保存的就是編號為n的盤子從A柱到C柱的過程，str(i)是類型轉(zhuǎn)換，將整數(shù)型轉(zhuǎn)換為字符串型。字符串變量laststep求取的是將放置在B柱的前i-1個盤子移動到C柱，利用的仍然是已知的前i-1個盤子從A柱到C柱的移動字符串result。最后將這三步得到的字符串進(jìn)行連接，保存在result變量中，即已知i個盤子從源柱A到目標(biāo)柱C的所有路徑，從而在下一個循環(huán)中加以利用。表1列出了部分執(zhí)行過程中對應(yīng)的變量值。

表1　Hanoitest表部分對應(yīng)值

3　算法的代碼實現(xiàn)

本文中采用Visual Basic來實現(xiàn)所提出的算法，由于這里主要體現(xiàn)算法思想，因此并不對執(zhí)行過程做可視化處理；繪制的界面比較簡單，如圖6所示。界面使用了1個textbox用于輸入盤子個數(shù)n值，另1個textbox用于顯示各個盤子的移動過程，即結(jié)果。算法實現(xiàn)放置在按鈕Hanoi的單擊事件當(dāng)中，采用循環(huán)替代了遞歸過程。除此之外，定義了一個函數(shù)Hanoireplace來進(jìn)行字符替換，主要使用VB中的字符串函數(shù)replace來完成[6-7]。

圖5　設(shè)計界面效果圖

在Hanoireplace函數(shù)實現(xiàn)過程中，輸入?yún)?shù)中result表示i-1個盤子從A到C的移動軌跡結(jié)果，source表示當(dāng)前i-1個盤子所在位置，dest表示當(dāng)前i-1個盤子將要被放置到的目標(biāo)位置，auxi表示當(dāng)前需要使用到的輔助位置。Hanoireplace主要使用了replace這個字符串函數(shù)，先將原有移動軌跡中的A、B、C替換成X、Y、Z，再將X、Y、Z替換成當(dāng)前的源柱、輔助柱和目標(biāo)柱表示。這樣就體現(xiàn)了參數(shù)位置和移動順序之間的對應(yīng)關(guān)系，使得問題的解決更加簡單明了。具體代碼如下。

Public Function Hanoireplace(result As String，source As String，dest As String，auxi As String) As String

Dim varstep As String

varstep = result

varstep = Replace(varstep，"A"，"X")

varstep = Replace(varstep，"C"，"Z")

varstep = Replace(varstep，"B"，"Y")

varstep = Replace(varstep，"X"，source)

varstep = Replace(varstep，"Z"，dest)

varstep = Replace(varstep，"Y"，auxi)

Hanoireplace = varstep

End Function

按鈕點擊事件代碼中則會調(diào)用上面定義好的Hanoireplace函數(shù)，最終求得n個盤子從A到C的移動軌跡結(jié)果。具體代碼如下:

Dimi，nAs Integer

Dim firststep，secondstep，laststep，result As String

n= tx_n.Text

result = "1AC"

If (n= 1) Then

result = "1AC"

Else

Fori= 2 Ton

firststep = Hanoireplace(result，"A"，"B"，"C")

secondstep = CStr(i) + "AC"

laststep = Hanoireplace(result，"B"，"C"，"A")

result = firststep + secondstep + laststep

Nexti

End If

tx_result.Text = result

代碼中n表示盤子個數(shù)，變量i是循環(huán)變量，在循環(huán)體內(nèi)也表示當(dāng)前盤子的個數(shù)。firststep表示i-1個盤子暫時從A柱移動到輔助柱B的移動結(jié)果，secondstep表示編號i的盤子直接A柱到C柱的結(jié)果，laststep表示i-1個盤子從輔助柱B到C柱的結(jié)果，result則是前面3個步驟的結(jié)果串聯(lián)，初始值為1個盤子直接從A移動到C。

例如觀察n=2時的記錄，n為2表示當(dāng)前盤子個數(shù)為2，firststep保存前n-1即1個盤子從源A柱到輔助B柱的移動軌跡:“1AB”，secondstep保存著第n個盤子即2號盤從源A柱直接移動到目標(biāo)C柱的軌跡:“2AC”；laststep保存著前n-1即1個盤子從輔助B柱到目標(biāo)C柱的移動軌跡:“1BC”；result則保存著全部路徑，即前面三個字符串的合集:“1AB2AC1BC”。即先生成二叉樹左子樹，而后生成二叉樹的中間節(jié)點，最后生成二叉樹的右子樹，符合遞歸過程的執(zhí)行思路。

從算法分析和代碼實現(xiàn)可以很容易地看出程序的主體就是一個循環(huán)體，分別獲取了n=1，2，3……n個盤子的移動過程，時間復(fù)雜度為O(n)，將遞歸過程很巧妙地轉(zhuǎn)換成為非遞歸調(diào)用。

4　結(jié)束語

自底向上記錄式Hanoi塔非遞歸方法雖然變量result會隨著n的增大而占用更大的空間，但時間復(fù)雜度為O(n)，執(zhí)行效率仍有了非常大的提高。而且該算法的主體部分仍借鑒了Hanoi塔遞歸算法的基本思想，并在此基礎(chǔ)上進(jìn)行靈活的改進(jìn)，從而使得代碼簡短、易于理解，極大地降低了程序的復(fù)雜性。本算法從另一個角度揭示了Hanoi塔問題中的其中一個特點，對于Hanoi塔問題的進(jìn)一步研究提供了一定的參考思路和方法。

[1]王曉東.算法設(shè)計與分析[M].2版.北京：清華大學(xué)出版社，2010.

[2]嚴(yán)蔚敏，陳文博.數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程[M].北京：清華大學(xué)出版社，2011.

[3]陳業(yè)紅，張潔，陳琦.基于動態(tài)規(guī)劃技術(shù)的漢諾塔趣味遞推實現(xiàn)[J].山東輕工業(yè)學(xué)院學(xué)報，2011，25(4):47-49 .

[4]魏斌，馬繼輝，牛虎.基于遞歸算法的樹型結(jié)構(gòu)圖的設(shè)計與實現(xiàn)[J].計算機(jī)應(yīng)用與軟件，2011，28(1):96-98.

[5]周斌.“Problem of Towers of Hanoi”仿真軟件的設(shè)計[J].實驗室研究與探索，2011，30(7):61-63，71.

[6]陳瑞環(huán)，楊慶紅，姚興.使用遞推解決遞歸問題的研究與應(yīng)用[J].計算機(jī)應(yīng)用與軟件，2011，28(3):186-188.

[7]胡英.Visual Basic程序設(shè)計[M].北京：清華大學(xué)出版社.2014.

Non-Recursive Algorithm Based on Down-Up Record Method for Hanoi Tower

DAI Liping，HUANG Longjun，LIU Qinghua

(Software School，Jiangxi Normal University，Nanchang 330022，China)

The code of classical recursion algorithm for Hanoi tower problem is simple，but the time complexity isO(2n) and the code is difficult to understand.Understanding recursive idea of Hanoi tower problem and constructing a tree model based on the function，two objectives of the function’s parameters and the execution result are analyzed carefully.Then the relationship between them is obtained and used to design a new down-up non-recursive algorithm.This algorithm here records the moving paths ofnplates (n=1，2，…)，which could be applied to get the moving result ofn+1 plates directly.The experimental results show that the corresponding code is very easy to read，and its time complexity is onlyO(n)，which is further practice and study for the non-recursive research of Hanoi tower problem.

Hanoi tower problem; down-up record; non-recursive algorithm; Visual Basic

2014-12-30

江西省自然科學(xué)基金項目(20132BAB201031)。

戴莉萍(1979-)，女，碩士，講師，主要從事軟件工程、數(shù)據(jù)庫技術(shù)方面的研究。

TP301.6

A

10.3969/j.issn.1672-4550.2016.01.016