２０１１年第６期
福
建 電
腦
３７
漢諾塔問題的可視化教學演示軟件的設計與實現
洪
歧 ．魏凡哲
（１、陜西理工學院
陜西漢中
７２３００１ ２、華為電子有限責任公司
廣東深圳
５１８０００）
【摘
要】：漢諾塔問題是大學計算機專業《數據結構》課程的必講內容，在教學中用來幫助學生理解程
序的遞歸調用。本文利用非遞歸算法實現了該問題的的可視化教學演示，以圖形形式形象、直觀表現問題
解決過程。
【關鍵詞】：可視化；非遞歸算法；ｇｕｉ圖形對象；時間控件；堆棧
引言
漢諾塔問題是大學計算機專業《數據結構》課程的
必講內容．在教學中用來幫助學生理解程序的遞歸調
用【
ｎ。但是在教學中用到的方法一般都是字符式的輸
出。鮮有圖形化的形象表示，學生理解起來比較困難。
對該問題進行可視化教學演示能夠幫助學生更快的理
解遞歸的實質，利于計算機教學。在以往的資料和教材
中，曾經有人斷言“漢諾塔問題的解決只有兩種方式，
一
種是遞歸．一種是棧消解?！蹦_本文為了降低可視化的
難度．嘗試著采用了第三種算法解決此問題…
一非遞
歸算法。該算法在國內各種論文期刊上都沒有介紹過。
本文詳細討論此算法并敘述在此算法上的可視化。編
程環境Ｍｉ
ｃｒｏｓｏｆｔ
Ｖｉ
ｓｕａｌ
Ｃ＋＋，采用ｍｆｃ庫、ｗｉ
ｎｄｏｗｓ ＧＵＩ
對象以及時間控件實現。
１．
設計簡介
最終設計的軟件運行界面如圖１所示：
圖
１軟件運行界面
程序上邊的文本框只能輸入數字．在里面輸入需
要演示的盤子數。緊靠文本框的是按鈕用來確定輸入
的的數字。確定后程序就會顯示出盤子的初始情況。接
著是移動按鈕。點此按鈕程序開始自動演示盤子的移
動，速度定為每秒移動１個盤子。接下來是高速按鈕，
點此按鈕后程演示的速度加快。停止按鈕可以停止演
示方便教師穿插講解。在理論上該程序可以演示計算
基金項目：
陜西理工學院科研基金（
ＳＬＧＱＤｏ９ｏ３）
機整形數據范圍內任意個數的盤子的移動情況。但是
限于屏幕高度的問題．目前只能夠正常顯示３１個盤子
以下的情況。以后可以做成自適應盤子數量。
２．
主要模塊及關系
程序分為三大模塊：運算模塊、數據模塊、輸出模
塊。運算模塊通過數據模塊和輸出模塊緊密相連。運算
模塊每次從數據模塊讀取數據．根據讀取的數據運算
完后寫回數據模塊，同時告訴輸出模塊運算完畢。輸出
模塊收到運算模塊消息后．從數據模塊中讀取數據在
屏幕上輸出
模塊相關關系如圖２所示：
圖２模塊相關關系圖
這個過程在點擊按鈕“移動”后由操作系統定時調
用，也就是每隔一段時間就調用一次。直到盤子被全部
移動完畢。由運算模塊讀取數據模塊數據．判斷移動完
所有盤子后終止系統的調用。在這里，系統調用的具體
手段就是時間控件。下面詳細介紹各個模塊。
數據模塊
通過３個棧來記錄盤子在柱子上的狀態。具體實
現如下：
聲明：
ｉ
ｎｔ
ａｒｒ
ａｙ
＿
ｏｆ ｔ
ｅｍｐ；
初始化：
ａｒ
ｒａｙ￣ｏｆ
＿
．
ｔ
ｅｍｐ＝ｎｅｗ ｉ
ｎｔ
【３１；
ａｒｒａｙ．
＿ｏｆ
＿
ｔｅｍｐ［
Ｏ］
－
ｎｅｗ ｉ
ｎｔ
［
ｎｏ＋１］；
ａｒ
ｒａｙ＿ｏｆ
＿
ｔ
ｅｍｐ［１］＝ｎｅｗ ｉｎｔ［
ｎｏ＋１］
；
福
建
電
腦
２０１１年第６期
ａｒｒ
ａｙ＿ｏｆ
＿
ｔ
ｅｍｐ［２］＝ｎｅｗ Ｊ
ｕｔ
［ｎｏ＋Ｉｊ
；
…
一
些循環操作．初始化棧
對這三個棧的操作通過一個“指針的指針”完成。
這種方法的好處在于控制簡單。內存空間利用是整塊
的。不會因內存忘記釋放而產生內存碎片。增強程序的
健壯性。同時可以動態的控制堆棧的大小。堆棧的大小
由一個全局變量ｎｏ來控制。而ｒ
ｉ
ｏ變量的值又從用戶
的輸入中得到。
設置
２個整形變量
ｓｔ
ｅｐ＿ｏｆ
＿ｏｄｄＮｕｍｂｅｒ ｐｌ
ａｔ
ｅ．
ｓｔｅｐ＿ｏｆ
＿
＿
ｅ￣ｅｎＮｕｍｂｅｒ
＿
ｐｌ
ａｔ
ｅ來記錄是第偶數次移動還是
奇數次移動。
設置２個整形變量ｆ
ｒ
ｏｍ
＿
ｐｉ
ｌ
ｌ
ａｒ．ｔｏ
＿
ｐｉ
ｌ
ｌａ
ｒ來記錄下
次移動的開始位置和目標位置
輸出模塊
該模塊包括靜態輸出及從數據模塊后讀取數據后
直接在屏幕上相應的位置顯示等內容。具體實現的方
法是通過ｗｉ
ｎｄｏｗｓ的ＧＵＩ控件在屏幕相應的坐標畫矩
形用來表示盤子。畫粗直線，用來表示柱子。通過循環
遍歷堆棧，屏幕輸出圖形。核心代碼如下：
，
，畫盤予
ｆ
ｏｒ
（ｉ
ｎｔｉ
－ｏ；ｉ
＜３；ｉ＋＋）
ｆ
ｏｒ
（ｉ
ｎｔ
ｊ＝１；ｊ＜＝ｎｕｍｂｅｒ
＿ｏｆ ｐｌ
ａｔ
ｅ；ｊ＋＋）
（
ｉ
ｆ（ａｒｒ
ａｙ．
＿ｏｆ
＿
．
ｐｉ
ｌ
ｌａｒ［
ｉ
］
［
ｊ】?。剑铮?/p>
ｌ
ＤＣ．
Ｓｅｌ
ｅｅｔ
Ｏｂｊｅｅｔ
（
＆ｂｒｕｓｈ１）
；
ＤＣ．
Ｒｅｃｔ
ａｆ
ｌｇｌ
ｅ（
１
ｅｆ
Ｉ＋ｄｉ
ｓｔ
ａｎｃｅ ｉ—ａｒ
ｒａｙ＿ｏｆ ｐｉ
ｌ
ｌ
ａｒ
【
訂ｍ ２０，
【
０ｐ一（
ｉ
）書ｌ５，
ｌｅｆ
ｔ＋ｄｉ
ｓｔ
ａｎｃｅ
ｉ＋ｏｒ
－
ｒａｙ＿ｏＬｐｉ
ｌ
ａｒ［
ｉ
］
［
ｊ１
２０，
ｔ
Ｃ
ｐ—Ｇ—１
）
１
，
５
）；
１
）
ＤＣ．
Ｒｅｃｔ
ａｎｇｌ
ｅ０用來輸出矩形。ｌ
ｅｆ
ｔ、ｄｉ
ｓｔ
ａｎｃｅ、ｔ
ｏｐ等
是宏．
用來定義顯示的位置。
運算模塊
運算模塊是所有模塊中最關鍵部分。如采用通常
的遞歸算法來解決這個問題．在遞歸的過程中顯示動
畫時間很難控制．只有用一些耗費ｃｐｕ資源的方式減
慢系統的運算速度。這樣的程序在運行期間系統資源
占用很嚴重．程序效率很低而且容易崩潰。如果使用雙
線程來解決這個問題．即把運算模塊和顯示模塊作為
兩個線程同時運行．運算模塊遞歸一次后就休眠，然后
由顯示模塊顯示．顯示完后再激活運算模塊繼續遞歸。
但是到兩個線程的配合是一種高階的編程技巧，目前
駕御的難度太大。而采用非遞歸算法配合時間控件的
方法來解決動畫顯示的問題．可大大提高程序的效率。
非遞歸算法
非遞歸算法的是根據盤子在不同狀態的移動規律
得出的。漢諾塔問題具體到每一步可以抽象為：
１）從哪個柱子移動？
２）移動到哪個柱子？
解決問題
１無非是從３個柱子中找出一個合適
的。解決問題２則是從剩下的兩個柱子里選擇一個合
適的進行移動。經過觀察和總結我們發現了柱子每次
移動的規律?？偨Y如下：
設盤子的總數為Ｎ。
把盤子從上到下進行．編號為
ｌ—Ｎ。
如果Ｎ為偶數，奇數號盤每次移動ｌ步：
偶數號盤
每次移動２步。
如果Ｎ為奇數，奇數號盤每次移動２步：偶數號盤
每次移動ｌ步。
經過程序的觀察．發現在目前的可測試范圍內該
算法完全正確。
調用流程
由系統隨時間的流逝進行上述非遞歸調用。調用
的時間間隔可以由程序員設定。目前程序設定的是每
隔一秒調用一次。也就是說運算模塊每隔一秒計算一
次下一個盤子的移動位置．并將刷新后的位置寫回數
據模塊
３．
演示結果及結論
圖３—５給出了五個盤子的移動演示結果：
圖３五十盤子的扔始狀態
圖４中闊結果一
圉５五個盤子移動成功狀態一
采用非遞歸算法明顯地提高了整個程序的效率．
同時也避免了復雜的程序設計。是一種成功的算法應
用．采用該算法利用圖形動態演示漢諾塔問題解決過
程有利于提高教學效果。
參考文獻：
【
１】
嚴慰敏等編著．
數據結構．
北京：清華大學出版社，
２００８．
【
２】
譚浩強編著．
ｃ程序設計語言．北京：清華大學出版社，
２００８．
ｐ】
任哲編著．
ＭＦＣ
Ｗｉ
ｎｄｏｗｓ應用程序設計（
２版）．
北京：清華大學
出版社．
２００７．
９．