基于逆序編碼的漢諾塔非遞歸算法

嚴海兵

（蘇州科技大學 圖書館，江蘇 蘇州 215009）

漢諾塔問題源于古印度的一個游戲。游戲中有A、B、C三根柱子，A柱上從下往上按照大小順序摞著n個圓盤。游戲的目的：把圓盤按大小順序重新擺放到C柱上。規(guī)則為：（1）一次只能移動一只圓盤；（2）每根柱子只有最上面的圓盤可以搬動；（3）小圓盤上不能擺放大圓盤；（4）移動圓盤時可以利用B柱當作過渡柱子。

一些文獻在介紹遞歸算法、借助堆棧轉(zhuǎn)化遞歸算法為非遞歸算法等內(nèi)容時往往引入漢諾塔問題作為典型實例介紹[1－2]。一些學者在提出新的程序算法思路時，也常用漢諾塔問題的解決作為驗證實例。如文獻[3]利用二叉樹的中序遍歷深入理解程序遞歸算法；文獻[4]利用狀態(tài)機的思想提出的非遞歸算法，避免堆棧內(nèi)存溢出問題；文獻[5-7]化解漢諾塔問題為抽象分層樹，利用樹分層次迭代的非遞歸算法；文獻[8]利用人工智能算法中的啟發(fā)式搜索，解決漢諾塔問題，嘗試A算法的執(zhí)行效率。

筆者通過對漢諾塔圓盤搬運過程的分析，改變傳統(tǒng)的圓盤編碼從上到下、由小到大的順序1，2，…，n，為逆序n，n-1，…，1，通過找出圓盤移動的數(shù)學規(guī)律，提出一種新的簡潔高效的非遞歸算法。圖1為漢諾塔的圓盤順序、逆序編碼圖。下文分析中所涉及的圓盤編碼均按逆序編碼。

圖1 漢諾塔的圓盤順序、逆序編碼圖

1 圓盤搬運的數(shù)學規(guī)律

漢諾塔上的圓盤按照從大到小的順序編號1，2，…，n。當n=1時，圓盤搬運順序為，1 A→C；當n=2時，圓盤搬運順序為，2 A→B、1 A→C、2 B→C；當n=3時，圓盤搬運順序見表1；當n=4時，圓盤搬運順序見表2。

表1 3層漢諾塔搬運順序

表2 4層漢諾塔搬運順序

定理1完成n層漢諾塔的搬運總次數(shù)為Tn=2n-1[9]。

對于圓盤數(shù)為n層的漢諾塔可以分三步搬運：（1）將A柱上的n至2號盤，利用C柱過渡，搬運到B柱，搬運次數(shù)為Tn-1；（2）將A柱上的1號盤直接搬運到C柱上，搬運次數(shù)為1；（3）將B柱上的n至2號盤，利用A柱過渡，搬運到C柱，搬運次數(shù)為Tn-1，搬運完成。圓盤搬運總次數(shù)為Tn=2Tn-1+1，進一步利用數(shù)學歸納法可以證明Tn=2n-1。

證明當n=1，T1=1；假設(shè)Tn-1=2n-1-1成立；因為Tn=2Tn-1+1，所以Tn=2（2n-1-1）+1=2n-1，證畢。

因此，n層漢諾塔搬運的完成需要分Tn次步驟。

定理2完成n層漢諾塔的搬運，前1，2，…，n-1號圓盤的搬運次數(shù)、順序與完成n-1層漢諾塔的搬運相同。

4層漢諾塔的搬運見表2，去除4號盤的搬運示例見表3，可以發(fā)現(xiàn)與表1的3層漢諾塔圓盤的搬運次數(shù)、順序完全相同。

表3 去除4號盤的4層漢諾塔搬運順序

n層漢諾塔的n號圓盤在A、B、C柱之間來回搬運的目的是讓開通道，為了n-1層漢諾塔的搬運有序完成，因此，定理2成立。定理2是基于逆序編碼的圓盤搬運規(guī)律，傳統(tǒng)順序編碼此定理不成立。文中后續(xù)定理規(guī)律是以定理2為基礎(chǔ)延伸的。

定理3第k號圓盤搬運總次數(shù)為dk=2k-1。

證明由定理1、定理2可得，dk=Tk-Tk-1=（2k-1）-（2k-1-1）=2k-1。

定理4在完成n層漢諾塔的搬運中，第k號圓盤搬運的步驟號為Stepk（x）=2（n-k）（2x-1），{x|x∈N，1≤x≤dk，dk=2k-1}。

由定理1可知，n層漢諾塔的搬運相當2次n-1層漢諾塔的搬運加1次底層1號圓盤的搬運。底層1號圓盤的搬運順序號在第一次n-1層漢諾塔的搬運結(jié)束后進行，因此，為Step1=（Tn+1）/2=2n-1。以此類推，k號圓盤的首次搬運的步驟號是在其上n，n-1，…，k+1個圓盤組成的漢諾塔搬運第一次搬運結(jié)束后進行，因此，為Stepk（1）=2n-k。

每個圓盤在總的搬運序列中是平均分布的，由定理3可知，第k號圓盤搬運總次數(shù)為dk=2k-1，由定理1可知，n層漢諾塔的搬運總次數(shù)為Tn=2n-1。因此，k號圓盤搬運步驟間隔為（Tn+1）/dk=2n-k+1。因此，在完成n層漢諾塔的搬運中，第k號圓盤搬運的步驟號為

其中x為k號圓盤的搬運次序，因此，x取值為1，2，…，dk，所以，{x|x∈N，1≤x≤dk，dk=2k-1}。

定理5n層漢諾塔的搬運，奇數(shù)號盤按照A→C、C→B、B→A順序循環(huán)搬運，偶數(shù)號盤按照A→B、B→C、C→A順序循環(huán)搬運，直到搬運結(jié)束。

由表2可知，4層漢諾塔第1號盤搬運為A→C，第3號盤搬運為A→C、C→B、B→A、A→C，符合奇數(shù)號盤按照A→C、C→B、B→A順序循環(huán)搬運。第2號盤搬運為A→B、B→C，第4號盤搬運為A→B、B→C、C→A、A→B、B→C、C→A、A→B、B→C，符合偶數(shù)號盤按照A→B、B→C、C→A順序循環(huán)搬運。依據(jù)定理2，可以證明定理5成立。

2 算法實現(xiàn)

2.1 算法思路設(shè)計

輸入：漢諾塔的圓盤層數(shù)n，定義柱子編號“A”、“B”、“C”。

輸出：2n-1次搬運步驟全過程。

步驟：循環(huán)控制整數(shù)k從1到n，分析每只圓盤的搬運情況，執(zhí)行下列步驟：

Step1：計算第k號圓盤搬運總次數(shù)為dk=2k-1；

Step2：計算第k號圓盤首次搬運的步驟號Stepk（1）=2n-k；

Step3：循環(huán)控制k號圓盤搬運次序x從1到dk，

①如果第k號圓盤是奇數(shù)號盤，搬運次序xmod3，依據(jù)計算結(jié)果按照A→C、C→B、B→A順序循環(huán)搬運；

②如果第k號圓盤是偶數(shù)號盤，搬運次序xmod3，依據(jù)計算結(jié)果按照A→B、B→C、C→A順序循環(huán)搬運。

2.2 C程序代碼實現(xiàn)

定義n層漢諾塔的數(shù)據(jù)類型HanoiType，N表示漢諾塔圓盤的層數(shù)。定義圓盤搬運的數(shù)據(jù)類型Result，first、last分別表示被搬運圓盤disk起始柱、目標柱位置。

因為程序算法中涉及指數(shù)函數(shù)2n計算較多，因此定義整數(shù)型函數(shù)npower2（n）計算2n。

2.3 算法時間空間復(fù)雜度

基于逆序的漢諾塔非遞歸算法的時間復(fù)雜度T（n）=21-1+22-1+23-1+…+2n-1=2n-1=O（2n），這與遞歸算法的相當。在空間復(fù)雜度S（n）方面，由于算法中需要建立數(shù)量為2n-1的數(shù)組存儲空間，因此S（n）=O（2n）?？紤]到遞歸算法中統(tǒng)一改屏幕打印顯示為數(shù)組存儲，其空間復(fù)雜度也是相當?shù)?。基于逆序的漢諾塔非遞歸算法在時間空間的復(fù)雜度上沒有優(yōu)勢。傳統(tǒng)漢諾塔算法都是按照圓盤的序號依次順序?qū)ふ野徇\規(guī)律的，該項目研究中筆者掌握了每個圓盤的每次的搬運的數(shù)學規(guī)律，因此，可以隨機尋找出任意號圓盤的任意次搬運規(guī)律，由于沒有基本的堆棧運算，在基礎(chǔ)運算上具有部分優(yōu)勢。下面定義的函數(shù)void find（）屏幕打印k號圓盤的第x次的搬運規(guī)律。

3 運行時間測試

運行文中所寫程序算法的計算機配置信息：操作系統(tǒng)Windows 7（64位操作系統(tǒng)，專業(yè)版），處理器一個Intel（R）Core（TM）i3-2120 CPU@3.3CHz 3.30GHz，內(nèi)存4.00GB。每次運行程序測量的時間有誤差，記錄的運行時間為運行3次后取平均值。為了測試文中基于逆序編碼的漢諾塔非遞歸算法的執(zhí)行效率，進行了三種漢諾塔算法的運行時間比較測試，分別是文中基于逆序編碼的非遞歸算法、傳統(tǒng)的經(jīng)典遞歸算法、借助堆棧實現(xiàn)的非遞歸算法。因三種算法中用于屏幕顯示的語句相同，為屏幕打印printf語句，考慮到屏幕打印語句運行的耗時較長，約占運行測試時間的80%，對三種算法執(zhí)行效率的比較有較大干擾，表4中統(tǒng)計的測試時間數(shù)據(jù)是統(tǒng)一去除屏幕打印printf語句后的程序運行時間[10]，時間單位為秒。因計算機測試的時間最小精度為0.001 s，為便于觀測，問題規(guī)模即漢諾塔的層數(shù)n從10開始試驗計數(shù)統(tǒng)計。當n＞27時，程序運行停止。由表4可知三種算法隨著問題規(guī)模（n）的增大，程序算法運行所需時間都為2的指數(shù)級增長。該文研究的基于逆序編碼的非遞歸算法，執(zhí)行效率優(yōu)勢明顯。

表4 三種漢諾塔程序算法的運行時間 單位：s

4 結(jié)語

漢諾塔問題的求解是很多程序算法思想的試金石，文中的算法是其中一次新的探索。漢諾塔圓盤逆序編碼后所呈現(xiàn)出的移動數(shù)學規(guī)律，比順序編碼的要更加清晰、富有規(guī)律，通過其數(shù)學定理推導(dǎo)，得出的非遞歸程序算法運行效率較高。傳統(tǒng)的漢諾塔算法只能順序求解每個圓盤的搬運規(guī)律，現(xiàn)在可以隨機的尋找出任意圓盤任意次序的搬運規(guī)律。一些需要通過遞歸調(diào)用或者借助堆棧解決的程序算法，或明或暗也有相似的順序編碼問題，文中的算法可以提供借鑒和啟迪作用。