基于遞歸算法的Hanoi Tower動畫演示系統

傳統的漢諾塔遞歸算法需要四個參數。改進后的算法為三個參數,使函數接口更簡單易用。漢諾塔的動畫演示系統采用了采取離散點的方式展示塔盤在移動過程中動畫。動畫采取塔盤移動中間路徑的有限個點進行模擬動畫移動的過程，提高動畫演示程序運行的效率。移動塔盤的過程中會遇到中間塔影響，應當移動路徑應當跳過中間塔。一次移動動畫離散取點個數為10-15個,可模擬出真實的移動效果。

【關鍵詞】遞歸算法 Hanoi Tower動畫演示系統

1 Hanoi Tower問題以及傳統的遞歸算法的解法

漢諾塔問題源自印度神話,大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。常見求解此問題的遞歸函數為void hanoi(intn,charX,charY,charZ),需要四個參數,即移動的盤子數量n,移動的發源地X塔,移動途徑Y塔,移動的目的地Z塔,其中變量X,Y,Z都是字符型變量,取值范圍為{A,B,C}。

2 改進后的漢諾塔問題遞歸算法

傳統的算法求解漢諾塔問題函數有四個參數，第三個參數即移動途經的Y塔。這個參數可以省略，因為總共有三個塔，比如塔的名字為甲塔，乙塔，丙塔，假設移動的個數大于1，從甲塔移動到乙塔必然可以推測出借助丙塔。塔的名字為X塔，Y塔，Z塔，假設移動的個數大于1，從X塔移動到Y塔必然可以推測出必借助Z塔 , 從X塔移動到Z塔必然可以推測出必借助Y塔, 從Y塔移動到X塔必然可以推測出借助必Z塔, 從Y塔移動到Z塔必然可以推測出必借助X塔。從Z塔移動到X塔必然可以推測出借助必Y塔, 從Z塔移動到Y塔必然可以推測出必借助X塔。所以新的遞歸算法就是去掉變量char Y.通過X塔和Z塔可以計算出途徑過哪座塔.改進后的漢諾塔函數聲明為void han (char x, char y ,inti);函數定義為:

voidhan (char x, char y ,inti)

{

if(i>1)

{

han(x,(char)(3*'B'-x-y), i-1);

han(x , y , 1);

han((char)(3*'B'-x-y) ,y, i-1);

}

else

{ printf("%c --->%c ", x , y );

move(x , y ); push(y , readtop(x));

pull(x);

show();

Sleep(1000);

}

}

其中途徑的塔通過表達式3*'B'-x-y計算出來。用三個塔的字母之和減去已知的兩座塔字母和可以得到第三座塔的字母。因為x,y,z三個參數的取值為字符A, B, C,他們的和是3倍的B所以途徑的塔通過表達式3*'B'-x-y計算出來。

改進的漢諾塔演示系統開發工具為VC++6.0,使用C語言。程序頭文件包含了stdio.h,windows.h以及math.h。使用的庫函數有五個,分別為:聲明于stdio頭文件中的函數getchar(),printf(),以及聲明于Windows頭文件的GetStdHandle(),SetConsoleCursorPosition(),Sleep().

由于漢諾塔的計算量是以漢諾塔的層數的指數函數,超過10層的漢諾塔計算量已經很大,為量演示方便特設置漢諾塔演示系統的塔的高度小于10. 考慮到方便演示問題,可以定義全局整型常量MaxHigh為漢諾塔的最大高度,數值為5。同時可以定義全局整型常量MaxWidth為漢諾塔最大寬度。MaxHighMaxWidth可設置均設置5。使用若干個符號橫向排列模擬漢諾塔上的盤子。漢諾塔的底盤用直線段繪制，如圖1所示。

定義全局整型數組Mtrix[3][MaxHigh+1]用于存儲三座塔(A塔,B塔,C塔)的從低到高各層盤子的大小.,其中一維數組Mtrix[0]用于存放A塔各層盤子的大小,Mtrix[1]用于存放B塔各層盤子的大小,Mtrix[0]用于存放C塔各層盤子的大小。例如:Mtrix[0][1]表示A塔的第一層(即底層)盤子的大小;Mtrix[0][4]表示A塔的第4層上盤子的大小;Mtrix[1][2]表示B塔的第2層上盤子的大小;Mtrix[2][3]表示C塔的第3層上盤子的大小.但是三個一維數組的首元素不用來保存盤子的大小,而用來保存每個塔的最大有效高度,即每個塔上有盤子的層數。例如：Mtrix[0][0]表示A塔的盤子的層數，Mtrix[1][0]表示B塔的盤子的層數,Mtrix[2][0]表示C塔的盤子的層數。盤子的層數小于等于全局常量MaxHigh。

全局整型變量 Top表示演示塔的圖像的垂直方向起始位置，全局整型變量Left表示演示塔的圖像的水平方向的起始位置。

函數int* find(char c)用來尋找字母所對應塔的盤數數組的首指針。盤數數組保存了塔的各個層上盤子的大小信息.find函數把塔名和數組聯系在一起.find函數定義為:

int* find(char c)

{ intnum = c - 'A';

returnMtrix[num];

}

漢諾塔移動時需要記載移走的盤子,需要修改盤數數組,首先調用find函數尋找盤數數組的首指針,然后找到最上層的盤子令其數據為0,表示盤子移走,最后讓記載盤子總數的a[0]減一,表示移走了一個盤子. find函數定義為:

voidpull( char c)

{ int *a = find(c);

a[a[0]] = 0 ;

a[0] --;

}

漢諾塔移動時需要讀取記載移走的盤子的大小的信息,需要讀取盤數數組,首先調用find函數尋找盤數數組的首指針,然后返回最數組中最上層的盤子的大小。readtop函數定義為:

intreadtop(char x)

{ int *a = find(x);

return a[a[0]];

}

漢諾塔移動時需要記載移來的新的盤子,需要修改盤數數組,首先調用find函數尋找盤數數組的首指針, 然后讓記載盤子總數的a[0]加一,表示移來了一個新盤子,最后找到最上層的盤子數據等于以來的盤子的大小. 其函數聲明為push( char c , int b) ,其中參數c表示新增盤子所在的塔的名,參數b為移來盤子的大小,其函數定義為:

push( char c , int b)

{ int *a = find(c);

a[0]++;

a[a[0]]= b;

}

漢諾塔需要移動光標來畫像素點，進而模擬塔盤的移動，對于控制臺應用程序來說需要一個移動控制臺光標到制定的坐標(x,y)的函數，x表示垂直方向，y表示水平方向。其函數定義為：

void go(int x, int y)

{

HANDLE hOut =GetStdHandle(STD_OUTPUT_HANDLE);//獲取當前窗口句柄

COORD pos= {y, x};

SetConsoleCursorPosition(hOut,pos);

}

塔盤移動的時候需求塔的最高層盤垂直坐標和水平坐標，分別用自定義函數intfindtop(char x)和函數intfindleft(char x)完成坐標的尋找。

漢諾塔演示系統需要展示出移動每一步的移動之后最終圖形,用show()函數來完成這一功能,但是show函數不具有演示盤子飛到空中的效果,show函數的定義略去。飛到空中的效果用move函數來完成.move(char x , char y )函數的能是展示出從x塔到y塔的塔盤移動的路徑，其中參數x表示出發的塔的名,y表示目標塔的名。move函數的是通過逐幀展示移動盤子的圖像來表現移動的動畫, move函數調用了自定義函數Draw_kong( int x, int y ),其功能為把盤子從位置(x, y)c處移走后空白的效果。move函數調用自定義函數DrawLine( int x, int y , int width)，其功能為移動長度為witth的塔盤到坐標（x,y）處并顯示塔盤。move函數采用了采取離散點的方式展示塔盤在移動過程中動畫。動畫采取塔盤移動中間路徑的有限點進行模擬動畫移動的過程，提高動畫演示程序運行的效率。離散點的選擇方法是均勻選取中間點。離散點的個數為5~9個即可模擬出真實的移動效果。塔盤在二邊的塔互相移動的過程,塔盤中會遇到中間塔影響，塔盤移動路徑應當跳過中間塔，移動算法仍然采取離散取點的方式展示。

系統需要在main函數完成函數的總調度，首先初始化塔的初始狀態，即所有盤子全部在A塔，調用show展示初始狀態的圖形，然后漢諾塔計算移動核心函數han('A', 'B' , layer),即完成了漢諾塔演示系統的演示。

3 動畫展示模塊的效果

漢諾塔動畫演示系統的效果如圖1所示，（a）圖展示從A塔到B塔的移動效果,圖（b）~（f）展示從A塔到C塔移動一個盤的動態效果,動畫展示了移動的中間路徑的若干個離散的狀態，在移動過程中跨越了中間的B塔，移動的路徑是先升后降。每張圖的右邊文字顯示的是移動信息。

參考文獻

[1]李健.漢諾塔算法演示系統的設計與實現[J].現代計算機月刊,2011(10):76-80.

[2]孫玉霞.C語言程序設計中若干問題的探討[J].沈陽航空工業學院學報,2004(03).

[3]張宏梅，魯邦定.“漢諾塔”問題的算法分析及JAVA實現[J].電腦知識與技術:學術交流,2007,1(01):179-179.

作者簡介

杜海龍 (1986-)，男，碩士研究生學歷。現為無錫太湖學院物聯網工程學院助教。主要研究方向為人工智能與模式識別。

作者單位

無錫太湖學院物聯網工程學院 江蘇省無錫市 214000