用二級(jí)VB編寫Hanoi塔問題動(dòng)態(tài)演示程序的演示

　　1 引言

　　在計(jì)算機(jī)算法設(shè)計(jì)中，使用遞歸技術(shù)往往使函數(shù)的定義和算法的描述簡捷且易于理解。有些數(shù)據(jù)結(jié)構(gòu)如二叉樹等由于其本身固有的遞歸特性，特別適合用遞歸的形式來描述。還有一些問題，雖然其本身并沒有明顯的遞歸結(jié)構(gòu)，但用遞歸技術(shù)來求解使設(shè)計(jì)出的算法簡潔、易懂。因此深入掌握遞歸技術(shù)在算法設(shè)計(jì)過程中可以設(shè)計(jì)出更加有效的算法。

　　簡單地說，遞歸就是用自己定義自己。使用遞歸方法構(gòu)造算法的基本思路是：當(dāng)求解規(guī)模為n的問題時(shí)，先將其分解成若干個(gè)規(guī)模較小的與原問題具有相同特征的子問題，并找出子問題與原問題之間的組合關(guān)系，最后根據(jù)具體問題構(gòu)造出遞歸算法。

　　遞歸算法的執(zhí)行過程分“遞推”和“回歸”兩個(gè)階段。在遞推階段，把較復(fù)雜問題(如：規(guī)模為n)的求解推理至較原問題簡單一些的問題(如規(guī)模為n-1)的求解;在回歸階段，把遞推結(jié)束時(shí)所得到的解，逐級(jí)返回，依次得到稍復(fù)雜問題的解，最終得到原問題的解。

　　Hanoi塔問題是一個(gè)典型的適合于利用遞歸技術(shù)得到簡潔算法的例子。Hanoi塔問題源自約19世紀(jì)末在歐洲出現(xiàn)的一種游戲，游戲中首先在一塊銅板上放置三根柱子，在第一根柱子上自上而下、由小到大順序串著64個(gè)盤子。游戲的目標(biāo)是最后將所有盤子從第一根柱子上移到第三根柱子上，移動(dòng)過程中可以用第二根柱子過渡。游戲規(guī)定一次只能移動(dòng)一個(gè)盤子，并且任何時(shí)刻不允許大盤放在小盤的上面。

　　現(xiàn)在就給出關(guān)于Hanoi塔問題的程序，讓其將Hanoi塔問題的執(zhí)行過程動(dòng)態(tài)演示出來，以幫助讀者加深理解遞歸技術(shù)。

　　2 算法設(shè)計(jì)

　　我們先利用遞歸技術(shù)對(duì)該問題進(jìn)行算法設(shè)計(jì)。我們將三根柱子分別標(biāo)號(hào)為A、B、C，目標(biāo)是要將n個(gè)盤子從A柱子移動(dòng)到C柱子。該問題可以設(shè)計(jì)如下的遞歸算法：

　　第一步 將A柱子上n-1個(gè)盤子借助C柱子移動(dòng)到B柱子上;

　　第二步 將A柱子上剩余的第n個(gè)盤子移動(dòng)到C柱子上;

　　第三步 將B柱子上的n-1個(gè)盤子借助A柱子移動(dòng)到C柱子上。

　　對(duì)于第一步和第三步，我們又可以利用類似的方法繼續(xù)將其求解過程設(shè)計(jì)為一個(gè)規(guī)模為n-1的Hanoi塔遞歸算法。

　　3 遞歸算法動(dòng)態(tài)演示過程的程序?qū)崿F(xiàn)

　　對(duì)于該算法的程序?qū)崿F(xiàn)有兩個(gè)關(guān)鍵的難點(diǎn)，其一是初始化部分如何將三根柱子和n個(gè)盤子按照問題要求在屏幕上繪制出來;其二是盤子移動(dòng)過程的圖形實(shí)現(xiàn)。

　　3.1 form窗體設(shè)計(jì)及程序初始化

　　首先在form窗體中添加三個(gè)命令按鈕。

　　在開始執(zhí)行Hanoi塔問題求解過程之前，需要將三根柱子繪制在屏幕上，還需要接收用戶指定的盤子數(shù)及將盤子正確顯示至A柱子上。在本程序中接收盤子數(shù)是利用InputBox函數(shù)接收保存至全局變量number中，用實(shí)心矩形代表盤子。