漢諾塔問(wèn)題的非遞歸算法設(shè)計(jì)及可視化實(shí)現(xiàn)＊

彭 偉

（武漢城市職業(yè)學(xué)院，湖北武漢 430064）

漢諾塔游戲最早于19世紀(jì)出現(xiàn)在歐洲，它展示了一項(xiàng)正在婆羅門(mén)寺廟進(jìn)行的任務(wù)：在創(chuàng)世之初，牧師被授予一個(gè)銅盤(pán)，上面有3根鉆石針，在第1根針上疊放著64個(gè)碟片，每一個(gè)都比它下面的稍小一些，這位牧師被安排了一項(xiàng)任務(wù)，那就是將所有的碟片從第1根針移到第3根針，但要遵循的規(guī)則是：一次只能移動(dòng)一個(gè)碟片，并且不允許將任何一個(gè)碟片放在比它小的碟片上面。牧師被告知：當(dāng)他將64個(gè)碟片移動(dòng)到第3根針時(shí)，世界末日將會(huì)到來(lái)。

編寫(xiě)程序算法求解漢諾塔問(wèn)題是一項(xiàng)很有趣的任務(wù)，特別是其算法設(shè)計(jì)思想對(duì)很多類(lèi)似問(wèn)題的求解都有借鑒作用。本文將分別討論解決該問(wèn)題的經(jīng)典遞歸算法及該算法與二叉樹(shù)結(jié)構(gòu)的內(nèi)在關(guān)系，進(jìn)一步研究解決該問(wèn)題的非遞歸算法，最后在可視化程序開(kāi)發(fā)平臺(tái)上實(shí)現(xiàn)移動(dòng)過(guò)程的動(dòng)態(tài)模擬。

1 漢諾塔問(wèn)題遞歸算法及二叉樹(shù)分析

各種版本的《數(shù)據(jù)結(jié)構(gòu)》、《計(jì)算機(jī)算法》等教材都詳細(xì)講述了如何使用遞歸算法解決該問(wèn)題。以將N個(gè)碟片由第1針移到第3針為例，算法基本思想表述如下：

（1）首先將上面的N－1片移到第2針；

（2）再將第N片移到第3針；

（3）將第2針上共N－1片移到第3針。

對(duì)于第2步中暫時(shí)回避了的N－1片的移動(dòng)問(wèn)題，它將繼續(xù)遵循同樣的移動(dòng)思路。

上述問(wèn)題的求解過(guò)程體現(xiàn)了遞歸算法思想，對(duì)復(fù)雜的問(wèn)題分而治之，將工作分解成越來(lái)越小的部分，使得每一個(gè)部分都比原始問(wèn)題易于解決。

Hanoi問(wèn)題的經(jīng)典遞歸算法如下：

其中N為碟片數(shù)，s、e為起／止針編號(hào)，t為所借助的針編號(hào)。

觀察該算法，很容易發(fā)現(xiàn)它與二叉樹(shù)的中序遍歷算法非常相似：

受版面局限，本文中包括上述代碼在內(nèi)的所有代碼均未使用標(biāo)準(zhǔn)縮進(jìn)風(fēng)格編寫(xiě)。上述兩段代碼解決的問(wèn)題毫不相關(guān)，但在代碼結(jié)構(gòu)、語(yǔ)句順序上卻極其相似。對(duì)于4個(gè)碟片的漢諾塔問(wèn)題，可以很容易地使用遞歸樹(shù)分析工具對(duì)算法進(jìn)行分析，得出程序執(zhí)行的清晰路線圖。

Hanoi的遞歸樹(shù)如圖1所示，按照上述算法，實(shí)際應(yīng)該還有一層，但由于該層遇到N＝0而立即返回，未執(zhí)行任何移動(dòng)操作，故略去。程序的執(zhí)行路線如圖1中帶箭頭的線條所示，可以設(shè)想，圖1中每個(gè)圓圈內(nèi)包含了上述函數(shù)的完整“代碼副本”，它們由三個(gè)部分構(gòu)成：

第①部分，即 Move（N–1，s，t，e），形成向左的調(diào)用（遞進(jìn)調(diào)用）；

第②部分，即printf（"%d，%d－＞%d.＼n"，N，s，e），它處于兩個(gè)遞歸調(diào)用語(yǔ)句的中間，圖中反向箭頭指向該部分，它將產(chǎn)生一次打印輸出（一次回歸）；

第③部分，即 Move（N–1，t，e，s），形成向右的調(diào)用（遞進(jìn)調(diào)用）。

所繪制的“遞歸樹(shù)”清晰地呈現(xiàn)出“二叉樹(shù)”結(jié)構(gòu)特征，其中“向下箭頭”為“遞進(jìn)”調(diào)用，“向上箭頭”則為一次“回歸”，整個(gè)遞歸過(guò)程由此構(gòu)成。

考察“二叉遞歸樹(shù)”可知，Hanoi算法的執(zhí)行路線正好是二叉樹(shù)的Mid＿Order算法路線，即它們走的都是中序遍歷路線。而且，Hanoi的遞歸樹(shù)還是一棵滿二叉樹(shù)，樹(shù)的高度等于總碟片數(shù)N。類(lèi)似地，八皇后問(wèn)題的遞歸樹(shù)一定是八叉樹(shù)，只不過(guò)它不一定是滿的。由該二叉樹(shù)可以很容易計(jì)算出解決4個(gè)碟片問(wèn)題的總移動(dòng)次數(shù)，由于每一個(gè)結(jié)點(diǎn)中含有一次打?。ㄎ串?huà)出的一層中不含有任何操作），對(duì)應(yīng)于總共N個(gè)碟片的N層滿二叉樹(shù)，其結(jié)點(diǎn)總數(shù)為：2N–1，可見(jiàn)，4個(gè)碟片的漢諾塔問(wèn)題共需要24–1＝15次移動(dòng)。

回到最初的64個(gè)碟片的漢諾塔問(wèn)題，顯然共需要264–1次移動(dòng)，假定牧師每秒移動(dòng)一個(gè)碟片，則共需時(shí)間約為：5×1011年。天文學(xué)家估算的宇宙年齡約為2×1010年，那么解決漢諾塔問(wèn)題所花的時(shí)間將是宇宙年齡的25倍，看來(lái)漢諾塔的預(yù)言并非完全是虛妄的。

2 非遞歸算法的設(shè)計(jì)分析

漢諾塔問(wèn)題的遞歸算法非常簡(jiǎn)潔，但是要直接回答問(wèn)題：N片的漢諾塔問(wèn)題中第i步應(yīng)該移動(dòng)哪一片？遞歸算法顯然效率低下，因?yàn)樗仨氁恢边f歸到二叉樹(shù)中的相應(yīng)結(jié)點(diǎn)位置時(shí)，才能回答這一問(wèn)題。

如果能找出某種解決方法，僅僅給出變量i即可知道應(yīng)該移動(dòng)誰(shuí)及如何移動(dòng)，那么整個(gè)算法中通過(guò)2N－1次循環(huán)即可打印出所有移動(dòng)步驟。

下面進(jìn)一步考察分析Hannio問(wèn)題二叉遞歸樹(shù)中各結(jié)點(diǎn)的碟片移動(dòng)規(guī)律，研究漢諾塔問(wèn)題的非遞歸算法。

整個(gè)非遞歸算法要解決的問(wèn)題有兩個(gè)：

（1）第i步（即結(jié)點(diǎn)i）應(yīng)移動(dòng)哪一碟片

首先約定，將二叉樹(shù)最底層編號(hào)設(shè)為1，依次向上一直到根結(jié)點(diǎn)，分別為2、3、4層（這與數(shù)據(jù)結(jié)構(gòu)教材中定義的一般順序相反），層的編號(hào)用變量Ln（Level Number）表示。二叉樹(shù)中的各結(jié)點(diǎn)則按中序遍歷序列逐一編號(hào)，分別為1～15?？疾靾D1所示二叉樹(shù)發(fā)現(xiàn)：

圖1 用二叉遞歸樹(shù)跟蹤分析求解漢諾塔問(wèn)題的遞歸算法

（Ⅰ）第Ln層移動(dòng)的碟片固定為L(zhǎng)n號(hào)碟片，即同一層總是處理同一片碟片。

（Ⅱ）第Ln層各結(jié)點(diǎn)編號(hào)的最大公約數(shù)為2LN－1。

例如1、2、3、4層內(nèi)各結(jié)點(diǎn)編號(hào)的最大公約數(shù)分別為1、2、4、8，每上升一層，最大公約數(shù)遞增一倍。它們實(shí)際上就是各層二叉樹(shù)最左邊分支的結(jié)點(diǎn)編號(hào)。

顯然，假設(shè)當(dāng)前要執(zhí)行第i步移動(dòng)（對(duì)應(yīng)于結(jié)點(diǎn)i），由結(jié)點(diǎn)編號(hào)i求出層號(hào)Ln，也就得到了第i步要移動(dòng)的碟片號(hào)。根據(jù)所分析得出的規(guī)律，可通過(guò)如下方法求取Ln：

例如：i＝12，先假定它所在層為L(zhǎng)n＝1，然后將i／2，除盡，故得Ln＝2；再將i／4，又除盡，故得Ln＝3；繼續(xù)將i／8時(shí)，不能除盡，故得Ln最后為3。

對(duì)應(yīng)的C程序代碼實(shí)現(xiàn)為：

（2）如何確定起、止針編號(hào)

得出根據(jù)i值獲取當(dāng)前待移動(dòng)碟片號(hào)的算法以后，還需要進(jìn)一步研究找出第i步所移動(dòng)的碟片的起始位置和目標(biāo)位置。進(jìn)一步考察二叉樹(shù)可知：

（Ⅰ）各層的第一個(gè)結(jié)點(diǎn)移動(dòng)碟片時(shí)，起始針編號(hào)均為1，因?yàn)閷?duì)于任意規(guī)模的問(wèn)題，最初所有碟片都在1針上，目標(biāo)針是2或3；

（Ⅱ）當(dāng)前樹(shù)的層數(shù)N（即總碟片數(shù)）與結(jié)點(diǎn)i所在的層數(shù)Ln同奇或同偶時(shí)，目的針為3，否則必為2。

（Ⅲ）樹(shù)中每一層存在固定的移動(dòng)回路。

對(duì)于圖1所示二叉遞歸樹(shù)中的第1層，它所移動(dòng)的都是第1片，其中前三次移動(dòng)為：

這一序列剛好形成一個(gè)有3個(gè)頂點(diǎn)3條邊的回路，碟片從第1針出發(fā)，走過(guò)另兩針后回到起點(diǎn)，后面接著的三個(gè)結(jié)點(diǎn)將以同樣的回路移動(dòng)。

增加問(wèn)題的規(guī)模，例如N＝5、6，可以清晰地觀察到其對(duì)應(yīng)的遞歸二叉樹(shù)中每一層（包括最下層）都具有固定的移動(dòng)回路，且周期性重復(fù)?？梢?jiàn)，每層移動(dòng)的是同一碟片，且同一碟片的移動(dòng)總是按固定的回路重復(fù)輪轉(zhuǎn)。

由上述三個(gè)特征可知，在已經(jīng)通過(guò)i值得出層編號(hào)Ln，也就是待移動(dòng)碟片號(hào)以后，根據(jù)它在當(dāng)前層內(nèi)部的橫向編號(hào)，可推導(dǎo)出它的原始位置與目標(biāo)位置。

假設(shè)Sn為第i個(gè)結(jié)點(diǎn)在Ln層內(nèi)的橫向編號(hào)，例如第1層內(nèi)結(jié)點(diǎn)橫向編號(hào)范圍為1～8，第11號(hào)結(jié)點(diǎn)處于第1層，它在該層內(nèi)的橫向編號(hào)為6。

由于第Ln層內(nèi)結(jié)點(diǎn)的編號(hào)間隔為2Ln，例如第2層內(nèi)結(jié)點(diǎn)的編號(hào)間隔為22＝4，編號(hào)分別為2、6、10、14。

根據(jù)這一特點(diǎn)可得層內(nèi)橫向編號(hào)公式：

用C實(shí)現(xiàn)四舍五入函數(shù)ROUND時(shí)有：

例如：Sn＝（int）（11／21＋0.5）＝6，即11號(hào)編點(diǎn)在其所在層（第1層）內(nèi)橫向編號(hào)為6。

由i值已經(jīng)可以得出當(dāng)前移動(dòng)的Ln號(hào)碟片在Ln層橫向編號(hào)為Sn，由于橫向編號(hào)為1的起始針編號(hào)必為1，且根據(jù)同奇／同偶的特征可得到周期出現(xiàn)的移動(dòng)回路。

故接著僅僅還需要得出Sn在當(dāng)前層周期為3的移動(dòng)回路內(nèi)部的序號(hào)，為解決這個(gè)問(wèn)題，可定義變量p，其中1≤p≤3。有：

例如：第11號(hào)結(jié)點(diǎn)（i＝11）在第1層內(nèi)的橫向編號(hào)為Sn＝6，循環(huán)移動(dòng)回路為：

它是第二個(gè)循環(huán)中的第3步，即p＝3。

由于循環(huán)回路中第1步移動(dòng)為“1→2”，則第二步移動(dòng)必定為：

由“2→3”又可以得出第三步移動(dòng)為：

又如：i＝15，得p＝2，故移動(dòng)必為：

可見(jiàn)，由結(jié)點(diǎn)號(hào)（即步驟號(hào)）i可得出層編號(hào)Ln，也就是將移動(dòng)的碟號(hào)；同時(shí)，由i還可得出它在層中的橫向編號(hào)Sn，從而得出它在回路中所處的移動(dòng)步驟號(hào)p（1≤p≤3）。而任一回路第1步移動(dòng)的起／止針編號(hào)為（s，d），根據(jù)（Ⅰ）與（Ⅱ）可知它們分別為：

故而由p可得出橫向編號(hào)為Sn的結(jié)點(diǎn)的移動(dòng)方法，也就是結(jié)點(diǎn)i的移動(dòng)方法。問(wèn)題最終得解。

基于對(duì)二叉遞歸樹(shù)各結(jié)點(diǎn)對(duì)應(yīng)的碟片移動(dòng)情況的深入分析及研究結(jié)果，所得出的不使用堆棧技術(shù)的漢諾塔問(wèn)題非遞歸算法C程序代碼如下：

3 兩種算法的可視化設(shè)計(jì)與模擬移動(dòng)

為了更直觀的驗(yàn)證顯示漢諾塔問(wèn)題的遞歸算法及由二叉遞歸樹(shù)研究分析所得出的非遞歸算法的運(yùn)行效果，可考慮選擇基于.NET開(kāi)發(fā)平臺(tái)，用VB.NET或C＃.NET開(kāi)發(fā)可視化程序，實(shí)現(xiàn)整個(gè)移動(dòng)過(guò)程的動(dòng)態(tài)模擬。所設(shè)計(jì)的可視化模擬動(dòng)態(tài)移動(dòng)程序界面如圖2所示，其中：

（Ⅰ）用樹(shù)形視圖組件（TreeView）顯示的遞歸樹(shù)窗口中，每一結(jié)點(diǎn)名稱(chēng)前形如“（？）”的數(shù)值為結(jié)點(diǎn)編號(hào)，與圖1對(duì)應(yīng)。

（Ⅱ）移動(dòng)過(guò)程窗口用于順序顯示每一步移動(dòng)的碟片號(hào)及起／止針名稱(chēng)（A／B／C）。

（Ⅲ）碟片的動(dòng)態(tài)移動(dòng)過(guò)程在最上面的圖形窗口用Graphics繪圖對(duì)象顯示。

限于篇幅，本文僅列出兩種算法的VB.NET版相關(guān)核心代碼，更完整的 WinForm程序可由讀者自行完善。

圖2 遞歸與非遞歸算法運(yùn)行測(cè)試及可視化移動(dòng)模擬

（1）相關(guān)變量定義

（2）漢諾塔的遞歸函數(shù)

（3）漢諾塔的非遞歸函數(shù)

（4）模擬碟片移動(dòng)過(guò)程的函數(shù)

4 結(jié) 語(yǔ)

本文結(jié)合遞歸樹(shù)分析工具，對(duì)解決漢諾塔問(wèn)題的經(jīng)典遞歸算法進(jìn)行分析研究，并基于對(duì)二叉遞歸樹(shù)的深入分析研究結(jié)論，得出了未使用堆棧的非遞歸解法，并在.NET可視化程序設(shè)計(jì)平臺(tái)對(duì)兩種算法均進(jìn)行了模擬移動(dòng)驗(yàn)證，取得了所預(yù)期的理想效果。

1 Robert Kruse，CL Tondo，Bruce Leung.DATA STRUCTURE ＆ PROGRAM DESIGN IN C［M］.PRENTICE HALL，2001

2（美）維斯.數(shù)據(jù)結(jié)構(gòu)與算法分析C＋＋描述（第三版）［M］.人民郵電出版社，2007

3（美）麥克米蘭.數(shù)據(jù)結(jié)構(gòu)與算法（C＃語(yǔ)言版［M］.清華大學(xué)出版社，2009

4（美）薩尼.數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用：C＋＋語(yǔ)言描術(shù)［M］.機(jī)械工業(yè)出版社，2005

5 余祥宣，崔國(guó)華，鄒海明.計(jì)算機(jī)算法基礎(chǔ)（第二版）［M］.華中科技大學(xué)出版社，2000