2011年第6期
福
建 電
腦
37
漢諾塔問題的可視化教學演示軟件的設計與實現
洪
歧 .魏凡哲
(1、陜西理工學院
陜西漢中
723001 2、華為電子有限責任公司
廣東深圳
518000)
【摘
要】:漢諾塔問題是大學計算機專業《數據結構》課程的必講內容,在教學中用來幫助學生理解程
序的遞歸調用。本文利用非遞歸算法實現了該問題的的可視化教學演示,以圖形形式形象、直觀表現問題
解決過程。
【關鍵詞】:可視化;非遞歸算法;gui圖形對象;時間控件;堆棧
引言
漢諾塔問題是大學計算機專業《數據結構》課程的
必講內容.在教學中用來幫助學生理解程序的遞歸調
用【
n。但是在教學中用到的方法一般都是字符式的輸
出。鮮有圖形化的形象表示,學生理解起來比較困難。
對該問題進行可視化教學演示能夠幫助學生更快的理
解遞歸的實質,利于計算機教學。在以往的資料和教材
中,曾經有人斷言“漢諾塔問題的解決只有兩種方式,
一
種是遞歸.一種是棧消解?!蹦_本文為了降低可視化的
難度.嘗試著采用了第三種算法解決此問題…
一非遞
歸算法。該算法在國內各種論文期刊上都沒有介紹過。
本文詳細討論此算法并敘述在此算法上的可視化。編
程環境Mi
crosoft
Vi
sual
C++,采用mfc庫、wi
ndows GUI
對象以及時間控件實現。
1.
設計簡介
最終設計的軟件運行界面如圖1所示:
圖
1軟件運行界面
程序上邊的文本框只能輸入數字.在里面輸入需
要演示的盤子數。緊靠文本框的是按鈕用來確定輸入
的的數字。確定后程序就會顯示出盤子的初始情況。接
著是移動按鈕。點此按鈕程序開始自動演示盤子的移
動,速度定為每秒移動1個盤子。接下來是高速按鈕,
點此按鈕后程演示的速度加快。停止按鈕可以停止演
示方便教師穿插講解。在理論上該程序可以演示計算
基金項目:
陜西理工學院科研基金(
SLGQDo9o3)
機整形數據范圍內任意個數的盤子的移動情況。但是
限于屏幕高度的問題.目前只能夠正常顯示31個盤子
以下的情況。以后可以做成自適應盤子數量。
2.
主要模塊及關系
程序分為三大模塊:運算模塊、數據模塊、輸出模
塊。運算模塊通過數據模塊和輸出模塊緊密相連。運算
模塊每次從數據模塊讀取數據.根據讀取的數據運算
完后寫回數據模塊,同時告訴輸出模塊運算完畢。輸出
模塊收到運算模塊消息后.從數據模塊中讀取數據在
屏幕上輸出
模塊相關關系如圖2所示:
圖2模塊相關關系圖
這個過程在點擊按鈕“移動”后由操作系統定時調
用,也就是每隔一段時間就調用一次。直到盤子被全部
移動完畢。由運算模塊讀取數據模塊數據.判斷移動完
所有盤子后終止系統的調用。在這里,系統調用的具體
手段就是時間控件。下面詳細介紹各個模塊。
數據模塊
通過3個棧來記錄盤子在柱子上的狀態。具體實
現如下:
聲明:
i
nt
arr
ay
_
of t
emp;
初始化:
ar
ray ̄of
_
.
t
emp=new i
nt
【31;
array.
_of
_
temp[
O]
-
new i
nt
[
no+1];
ar
ray_of
_
t
emp[1]=new int[
no+1]
;
福
建
電
腦
2011年第6期
arr
ay_of
_
t
emp[2]=new J
ut
[no+Ij
;
…
一
些循環操作.初始化棧
對這三個棧的操作通過一個“指針的指針”完成。
這種方法的好處在于控制簡單。內存空間利用是整塊
的。不會因內存忘記釋放而產生內存碎片。增強程序的
健壯性。同時可以動態的控制堆棧的大小。堆棧的大小
由一個全局變量no來控制。而r
i
o變量的值又從用戶
的輸入中得到。
設置
2個整形變量
st
ep_of
_oddNumber pl
at
e.
step_of
_
_
e ̄enNumber
_
pl
at
e來記錄是第偶數次移動還是
奇數次移動。
設置2個整形變量f
r
om
_
pi
l
l
ar.to
_
pi
l
la
r來記錄下
次移動的開始位置和目標位置
輸出模塊
該模塊包括靜態輸出及從數據模塊后讀取數據后
直接在屏幕上相應的位置顯示等內容。具體實現的方
法是通過wi
ndows的GUI控件在屏幕相應的坐標畫矩
形用來表示盤子。畫粗直線,用來表示柱子。通過循環
遍歷堆棧,屏幕輸出圖形。核心代碼如下:
,
,畫盤予
f
or
(i
nti
-o;i
<3;i++)
f
or
(i
nt
j=1;j<=number
_of pl
at
e;j++)
(
i
f(arr
ay.
_of
_
.
pi
l
lar[
i
]
[
j】?。剑铮?/p>
l
DC.
Sel
eet
Objeet
(
&brush1)
;
DC.
Rect
af
lgl
e(
1
ef
I+di
st
ance i—ar
ray_of pi
l
l
ar
【
訂m 20,
【
0p一(
i
)書l5,
lef
t+di
st
ance
i+or
-
ray_oLpi
l
ar[
i
]
[
j1
20,
t
C
p—G—1
)
1
,
5
);
1
)
DC.
Rect
angl
e0用來輸出矩形。l
ef
t、di
st
ance、t
op等
是宏.
用來定義顯示的位置。
運算模塊
運算模塊是所有模塊中最關鍵部分。如采用通常
的遞歸算法來解決這個問題.在遞歸的過程中顯示動
畫時間很難控制.只有用一些耗費cpu資源的方式減
慢系統的運算速度。這樣的程序在運行期間系統資源
占用很嚴重.程序效率很低而且容易崩潰。如果使用雙
線程來解決這個問題.即把運算模塊和顯示模塊作為
兩個線程同時運行.運算模塊遞歸一次后就休眠,然后
由顯示模塊顯示.顯示完后再激活運算模塊繼續遞歸。
但是到兩個線程的配合是一種高階的編程技巧,目前
駕御的難度太大。而采用非遞歸算法配合時間控件的
方法來解決動畫顯示的問題.可大大提高程序的效率。
非遞歸算法
非遞歸算法的是根據盤子在不同狀態的移動規律
得出的。漢諾塔問題具體到每一步可以抽象為:
1)從哪個柱子移動?
2)移動到哪個柱子?
解決問題
1無非是從3個柱子中找出一個合適
的。解決問題2則是從剩下的兩個柱子里選擇一個合
適的進行移動。經過觀察和總結我們發現了柱子每次
移動的規律??偨Y如下:
設盤子的總數為N。
把盤子從上到下進行.編號為
l—N。
如果N為偶數,奇數號盤每次移動l步:
偶數號盤
每次移動2步。
如果N為奇數,奇數號盤每次移動2步:偶數號盤
每次移動l步。
經過程序的觀察.發現在目前的可測試范圍內該
算法完全正確。
調用流程
由系統隨時間的流逝進行上述非遞歸調用。調用
的時間間隔可以由程序員設定。目前程序設定的是每
隔一秒調用一次。也就是說運算模塊每隔一秒計算一
次下一個盤子的移動位置.并將刷新后的位置寫回數
據模塊
3.
演示結果及結論
圖3—5給出了五個盤子的移動演示結果:
圖3五十盤子的扔始狀態
圖4中闊結果一
圉5五個盤子移動成功狀態一
采用非遞歸算法明顯地提高了整個程序的效率.
同時也避免了復雜的程序設計。是一種成功的算法應
用.采用該算法利用圖形動態演示漢諾塔問題解決過
程有利于提高教學效果。
參考文獻:
【
1】
嚴慰敏等編著.
數據結構.
北京:清華大學出版社,
2008.
【
2】
譚浩強編著.
c程序設計語言.北京:清華大學出版社,
2008.
p】
任哲編著.
MFC
Wi
ndows應用程序設計(
2版).
北京:清華大學
出版社.
2007.
9.