2Ol1年l2月
第31卷第6期
鄖陽師范高等??茖W校學報
Journal of Yunyang Teachers Col
l
ege
Dee.2Oll
Vo1.3l No.6
漢諾塔的動態演示程序
郭亞慶
(十堰職業技術學院 電子工程系,湖北 十堰
442000)
[摘
要]在程序設計中,遞歸算法一直是教學的難點.為幫助學生對遞歸調用有深刻的理解,特制作漢諾
塔動態演示程序。
從而把復雜的教學問題變為直觀,生動的動畫教學,以提高教學效果.
[關鍵詞]遞歸算法,
動態演示,集合,程序簡化
[doi
]lO.3969/j
.i
ssn。1008-
-
6072.2011.06.017
[中圖分類號]TP311
[文獻標識碼3A
[文章編號]1008-
-
6072【
2011)
06-
-
0067-
-
02
1
遞歸的基本思想
遞歸算法是算法設計的有力武器,它提供了
有限語句描述無限過程的可能性.許多看來相當
復雜的,
難以下手的問題,如果能把它歸納成帶遞
歸性的問題,處理起來就相當方便.簡單地說,遞
歸算法就是直接或間接的調用自己本身.它的基
本思路是:是把問題轉化為規??s小了的同類問
題的子問題,當求解規模為n的問題時,先將其分
解成若干個規模較小的與原問題具有相同特征的
子問題口.
1的Hanoi塔遞歸算法.
Pri
vate Sub HNT(N
,A As
Stri
ng,B As
Stri
ng,C As Stri
ng)
I
f
N
=
1
Then
YD
A,C
‘調用移動子程序
Else
Cal
l
HNT(N一
1,A,C,B)
YD
A,C
‘調用移動子程序
Can HNT(N一
1,B,A,C)
End If
End SUb
2
Hanoi塔問題的算法分析
3
集合的妙用
漢諾(Hanoi
)塔問題:在印度,傳說有一個梵
塔,塔內有三根柱子
A、B、C,A柱上有64個盤
子,盤子大小不等,大的在下,小的在上,有一個和
尚想把這64個盤子從A柱移到C柱,但每次只
能允許移動一個盤子,并且在移動過程中,要求3
個柱上的盤子始終保持大盤在下,小盤在上.
我們將三根柱子分別標號為A、B、C,目的是
要將n個盤子從A柱子移動到C柱子.該問題的
算法如下:
第一步將A柱子上n一1個盤子借助C柱
子移動到B柱子上;
第二步將A柱子上剩余的第n個盤子移動
到C柱子上;
第三步將B柱子上的n一1個盤子借助A
柱子移動到C柱子上.
對于第一步和第三步,我們又可以利用類似
的方法繼續將其求解過程設計為一個規模為n一
從上面的算法中我們知道,動態演示的關鍵
是移動(YD)子程序的設計,它有兩個形參,接收
來自調用程序的實參A,
C.A為即將移動園盤的
源柱號,C為園盤移動的目標柱號.進而要知道源
柱上的哪個盤.這就要求記錄每根柱子上的盤數
(即層數)及每層的盤號,移動一個園盤之后,起始
柱上的盤數(即層數)要減一,目標柱的盤數(即層
數)要加一,并要求記住該盤的盤號.為了簡化程
序設計,這里定義了一個集合類形的數據,Di
m
l
i
n(1
To 3)As
New Col
l
ecti
on,l
i
n的下標1到3
,
表示三根柱子的柱號.它的每個元素為集合類
形,集合類似于數組,但可以比數組更靈活、更有
效的方式處理集合中數據項,它可以保存VB中
各種不同類型的數據.巧妙的是集合的兩個方法
ADD、Remove即給集合增加和刪除一個項目正
好能模擬跟蹤每個柱子上園盤的增加和減少,而
集合的Count屬性則自動記錄了每個柱子上園
[收稿日期12011一l
O一21
[作者簡介]郭亞慶(1974-
-
),
女,陜西禮泉人,十堰職業技術學院電子工程系講師,主要從事計算機技術,
計算機信息管
理研究.
幾
—
YYS—
ZXB O/
郭亞慶:漢諾塔的動態演示程序
盤的個數.這種數據的組織形式,為簡化程序設計
提供了極為便利條件.
4
園盤移動程序的設計
1、form窗體設計:先將三根柱子繪制在屏幕
上,為了簡化程序,柱與柱之間必須保持等距離,
再繪制七個標簽框,三個命令按鈕.
2、初始化:
先輸人園盤個數N,利用循環在A
柱(即第一根柱子)上自動產生N個大小不等,顏
色不同的園盤,產生一個園盤后,隨之執行
l
i
n
(1).Add i
(i從l到N),給集合添加一個數據項i
(即存人一個園盤編號),該柱頂層的園盤號就存
放在li
n(1)(1
i
n(1).euont)中,因為移動一個園盤
必須取該柱頂層的園盤.
3、移動速度根據園盤的多少自己可輸入園盤
移動一次的延時時間,默認值為1000毫秒,若為
默認值,
則N個盤移動時間為2 一1秒
,程序執
行前后會自動顯示起始時間和終止時間,為了簡
化程序設計,延時直接調用API函數.
4、園盤移動子程序YD的設計:這是動態演
示程序的關鍵和難點,YD(ByVal
qs As Int
eger,
ByVal
MB As Int
eger)形參QS為源柱號,mb為
目標柱號,在移動前先取源柱上本次要移動的盤
號,而Li
n(qs)(1
i
n(qs).Count)則為源柱最上層
的盤號.園盤移動分三個步驟:
1.上移:上移時X坐標值不變,Y坐標值只
要高于柱子的高度.上移完后,執行
Li
n(qs).Remove l
i
n(qs).Count即在記錄源
柱盤數編號的集合中刪去一項,記錄源柱上的盤
數自動減1.
B.左右移動;Y坐標值不變,X坐標值移動
的距離為目標柱號減去源柱號的差值乘以柱與柱
之間的距離)而左右方向則取決于目標柱號減去
源柱號差值的符號
C.下移:這是難點,因為下移的距離的不能
是一個統一的高度,否則會造成園盤重迭或盤與
盤之間有一定的距離,這里采用下移一個Y坐標
的絕對值減去目標柱上的園盤數乘以園盤的高
度,下移后執行l
i
n(mb).Add i,讓記錄目標柱上
盤數的集合要加l,并記錄移動到目標柱上該盤
的所處的層數及盤號.
附園盤移動子程序如下:
Pri
vat
e Sub YD(ByVal
qs
As Integer,By—
Val
mb As Integer)
l—l
i
n(qs)(1
i
n(qs).Count)
‘取源柱上即
將移動的盤號
ShAP(1).Move S P(
I).Lef
t,500,
向上移動
l
i
n(qs).Remove
li
n(qs).Count
‘從記錄
源柱盤號的集合中刪去一項
Sl
eep SD/2
‘延時
ShAP(I).Move ShAP(I).Lef
t+
(mb—
qs)*5000,ShAP(I).Top左右移動
Sl
eep SD/2
ShAP(I).Move ShAP(1).Left,4800一
l
i
n
(mb).Count,*200 向下移動
l
i
n(mb).Add I
‘給記錄目標柱盤號的集
合中增加一項
End Sub
Private Sub Command3
一
Cl
i
ck()
End
End Sub
Sub HNT(N,A As Stri
ng,B As
Stri
ng,C
As String)
If N
=
1 Then
YD A。C
Else
CaU HNT(N一
1,A,C,B)
YD A。C
Cal
l
HNT(N一
1,B,A,C)
End If
End Sub[
Z3
5
結論
動態演示過程是教學史上的一大進步和創
舉,直觀的畫面圖像及聲音再現課堂,克服了傳統
教學過于抽象和難以理解的缺陷,有利于調動學
生學習的積極性,培養學生的思維能力和解決問
題的能力,本文利用集合類型的數據開發了一個
簡單的動態演示程序,但愿對一線程序設計教學
的教師有所幫助.
[參考文獻]
El3龔沛曾.VISUAL BASIC程序設計簡明教程[M].北京:高教
出版社,2001.
[2]劉炳文.精通VI
SUAL BASI
C6.0中文版[M].北京:電子工
業出版社,
2001.
【編校:胡軍?!?nbsp;
A Dynamic Demonstrati
on Program of
Hanoi Tower
GUO Ya—qi
ng
(Department of
Electri
c Engineering.Shiyan Techni
eal
Insti
tute.Shi
yan 442000,Chi
na)
Abstract:In program desi
gn,recursi
ve al
gorithm has al
ways been a teachi
ng dif
fi
culty.A dynamic demonstrati
on
program of Hanoi
Tower has been designed tO help students understand reeursive transfer as to make complex t
eachi
ng
direct
and vivi
d wi
th a purpose of i
mprovi
ng t
eachi
ng quali
ty.
Key words:recursive algori
thm;dynami
c demonstrati
on;set;program simpli
fyi
ng
n
—
YYS—
Z
XB b
2
=
;