傳統(tǒng)的漢諾塔遞歸算法需要四個(gè)參數(shù)。改進(jìn)后的算法為三個(gè)參數(shù),使函數(shù)接口更簡(jiǎn)單易用。漢諾塔的動(dòng)畫演示系統(tǒng)采用了采取離散點(diǎn)的方式展示塔盤在移動(dòng)過程中動(dòng)畫。動(dòng)畫采取塔盤移動(dòng)中間路徑的有限個(gè)點(diǎn)進(jìn)行模擬動(dòng)畫移動(dòng)的過程，提高動(dòng)畫演示程序運(yùn)行的效率。移動(dòng)塔盤的過程中會(huì)遇到中間塔影響，應(yīng)當(dāng)移動(dòng)路徑應(yīng)當(dāng)跳過中間塔。一次移動(dòng)動(dòng)畫離散取點(diǎn)個(gè)數(shù)為10-15個(gè),可模擬出真實(shí)的移動(dòng)效果。

【關(guān)鍵詞】遞歸算法 Hanoi Tower動(dòng)畫演示系統(tǒng)

1 Hanoi Tower問題以及傳統(tǒng)的遞歸算法的解法

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

2 改進(jìn)后的漢諾塔問題遞歸算法

傳統(tǒng)的算法求解漢諾塔問題函數(shù)有四個(gè)參數(shù)，第三個(gè)參數(shù)即移動(dòng)途經(jīng)的Y塔。這個(gè)參數(shù)可以省略，因?yàn)榭偣灿腥齻€(gè)塔，比如塔的名字為甲塔，乙塔，丙塔，假設(shè)移動(dòng)的個(gè)數(shù)大于1，從甲塔移動(dòng)到乙塔必然可以推測(cè)出借助丙塔。塔的名字為X塔，Y塔，Z塔，假設(shè)移動(dòng)的個(gè)數(shù)大于1，從X塔移動(dòng)到Y(jié)塔必然可以推測(cè)出必借助Z塔 , 從X塔移動(dòng)到Z塔必然可以推測(cè)出必借助Y塔, 從Y塔移動(dòng)到X塔必然可以推測(cè)出借助必Z塔, 從Y塔移動(dòng)到Z塔必然可以推測(cè)出必借助X塔。從Z塔移動(dòng)到X塔必然可以推測(cè)出借助必Y塔, 從Z塔移動(dòng)到Y(jié)塔必然可以推測(cè)出必借助X塔。所以新的遞歸算法就是去掉變量char Y.通過X塔和Z塔可以計(jì)算出途徑過哪座塔.改進(jìn)后的漢諾塔函數(shù)聲明為void han (char x, char y ,inti);函數(shù)定義為:

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);

}

}

其中途徑的塔通過表達(dá)式3*'B'-x-y計(jì)算出來(lái)。用三個(gè)塔的字母之和減去已知的兩座塔字母和可以得到第三座塔的字母。因?yàn)閤,y,z三個(gè)參數(shù)的取值為字符A, B, C,他們的和是3倍的B所以途徑的塔通過表達(dá)式3*'B'-x-y計(jì)算出來(lái)。

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

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

定義全局整型數(shù)組Mtrix[3][MaxHigh+1]用于存儲(chǔ)三座塔(A塔,B塔,C塔)的從低到高各層盤子的大小.,其中一維數(shù)組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層上盤子的大小.但是三個(gè)一維數(shù)組的首元素不用來(lái)保存盤子的大小,而用來(lái)保存每個(gè)塔的最大有效高度,即每個(gè)塔上有盤子的層數(shù)。例如：Mtrix[0][0]表示A塔的盤子的層數(shù)，Mtrix[1][0]表示B塔的盤子的層數(shù),Mtrix[2][0]表示C塔的盤子的層數(shù)。盤子的層數(shù)小于等于全局常量MaxHigh。

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

函數(shù)int* find(char c)用來(lái)尋找字母所對(duì)應(yīng)塔的盤數(shù)數(shù)組的首指針。盤數(shù)數(shù)組保存了塔的各個(gè)層上盤子的大小信息.find函數(shù)把塔名和數(shù)組聯(lián)系在一起.find函數(shù)定義為:

int* find(char c)

{ intnum = c - 'A';

returnMtrix[num];

}

漢諾塔移動(dòng)時(shí)需要記載移走的盤子,需要修改盤數(shù)數(shù)組,首先調(diào)用find函數(shù)尋找盤數(shù)數(shù)組的首指針,然后找到最上層的盤子令其數(shù)據(jù)為0,表示盤子移走,最后讓記載盤子總數(shù)的a[0]減一,表示移走了一個(gè)盤子. find函數(shù)定義為:

voidpull( char c)

{ int *a = find(c);

a[a[0]] = 0 ;

a[0] --;

}

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

intreadtop(char x)

{ int *a = find(x);

return a[a[0]];

}

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

push( char c , int b)

{ int *a = find(c);

a[0]++;

a[a[0]]= b;

}

漢諾塔需要移動(dòng)光標(biāo)來(lái)畫像素點(diǎn)，進(jìn)而模擬塔盤的移動(dòng)，對(duì)于控制臺(tái)應(yīng)用程序來(lái)說需要一個(gè)移動(dòng)控制臺(tái)光標(biāo)到制定的坐標(biāo)(x,y)的函數(shù)，x表示垂直方向，y表示水平方向。其函數(shù)定義為：

void go(int x, int y)

{

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

COORD pos= {y, x};

SetConsoleCursorPosition(hOut,pos);

}

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

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

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

3 動(dòng)畫展示模塊的效果

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

參考文獻(xiàn)

[1]李健.漢諾塔算法演示系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].現(xiàn)代計(jì)算機(jī)月刊,2011(10):76-80.

[2]孫玉霞.C語(yǔ)言程序設(shè)計(jì)中若干問題的探討[J].沈陽(yáng)航空工業(yè)學(xué)院學(xué)報(bào),2004(03).

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

作者簡(jiǎn)介

杜海龍 (1986-)，男，碩士研究生學(xué)歷。現(xiàn)為無(wú)錫太湖學(xué)院物聯(lián)網(wǎng)工程學(xué)院助教。主要研究方向?yàn)槿斯ぶ悄芘c模式識(shí)別。

作者單位

無(wú)錫太湖學(xué)院物聯(lián)網(wǎng)工程學(xué)院 江蘇省無(wú)錫市 214000