２Ｏｌ１年ｌ２月
第３１卷第６期
鄖陽師范高等?？茖W校學報
Ｊｏｕｒｎａｌ ｏｆ Ｙｕｎｙａｎｇ Ｔｅａｃｈｅｒｓ Ｃｏｌ
ｌ
ｅｇｅ
Ｄｅｅ．２Ｏｌｌ
Ｖｏ１．３ｌ Ｎｏ．６
漢諾塔的動態演示程序
郭亞慶
（十堰職業技術學院 電子工程系，湖北 十堰
４４２０００）
［摘
要］在程序設計中，遞歸算法一直是教學的難點．為幫助學生對遞歸調用有深刻的理解，特制作漢諾
塔動態演示程序。
從而把復雜的教學問題變為直觀，生動的動畫教學，以提高教學效果．
［關鍵詞］遞歸算法，
動態演示，集合，程序簡化
［ｄｏｉ
］ｌＯ．３９６９／ｊ
．ｉ
ｓｓｎ。１００８－
－
６０７２．２０１１．０６．０１７
［中圖分類號］ＴＰ３１１
［文獻標識碼３Ａ
［文章編號］１００８－
－
６０７２【
２０１１）
０６－
－
００６７－
－
０２
１
遞歸的基本思想
遞歸算法是算法設計的有力武器，它提供了
有限語句描述無限過程的可能性．許多看來相當
復雜的，
難以下手的問題，如果能把它歸納成帶遞
歸性的問題，處理起來就相當方便．簡單地說，遞
歸算法就是直接或間接的調用自己本身．它的基
本思路是：是把問題轉化為規?？s小了的同類問
題的子問題，當求解規模為ｎ的問題時，先將其分
解成若干個規模較小的與原問題具有相同特征的
子問題口．
１的Ｈａｎｏｉ塔遞歸算法．
Ｐｒｉ
ｖａｔｅ Ｓｕｂ ＨＮＴ（Ｎ
，Ａ Ａｓ
Ｓｔｒｉ
ｎｇ，Ｂ Ａｓ
Ｓｔｒｉ
ｎｇ，Ｃ Ａｓ Ｓｔｒｉ
ｎｇ）
Ｉ
ｆ
Ｎ
＝
１
Ｔｈｅｎ
ＹＤ
Ａ，Ｃ
‘調用移動子程序
Ｅｌｓｅ
Ｃａｌ
ｌ
ＨＮＴ（Ｎ一
１，Ａ，Ｃ，Ｂ）
ＹＤ
Ａ，Ｃ
‘調用移動子程序
Ｃａｎ ＨＮＴ（Ｎ一
１，Ｂ，Ａ，Ｃ）
Ｅｎｄ Ｉｆ
Ｅｎｄ ＳＵｂ
２
Ｈａｎｏｉ塔問題的算法分析
３
集合的妙用
漢諾（Ｈａｎｏｉ
）塔問題：在印度，傳說有一個梵
塔，塔內有三根柱子
Ａ、Ｂ、Ｃ，Ａ柱上有６４個盤
子，盤子大小不等，大的在下，小的在上，有一個和
尚想把這６４個盤子從Ａ柱移到Ｃ柱，但每次只
能允許移動一個盤子，并且在移動過程中，要求３
個柱上的盤子始終保持大盤在下，小盤在上．
我們將三根柱子分別標號為Ａ、Ｂ、Ｃ，目的是
要將ｎ個盤子從Ａ柱子移動到Ｃ柱子．該問題的
算法如下：
第一步將Ａ柱子上ｎ一１個盤子借助Ｃ柱
子移動到Ｂ柱子上；
第二步將Ａ柱子上剩余的第ｎ個盤子移動
到Ｃ柱子上；
第三步將Ｂ柱子上的ｎ一１個盤子借助Ａ
柱子移動到Ｃ柱子上．
對于第一步和第三步，我們又可以利用類似
的方法繼續將其求解過程設計為一個規模為ｎ一
從上面的算法中我們知道，動態演示的關鍵
是移動（ＹＤ）子程序的設計，它有兩個形參，接收
來自調用程序的實參Ａ，
Ｃ．Ａ為即將移動園盤的
源柱號，Ｃ為園盤移動的目標柱號．進而要知道源
柱上的哪個盤．這就要求記錄每根柱子上的盤數
（即層數）及每層的盤號，移動一個園盤之后，起始
柱上的盤數（即層數）要減一，目標柱的盤數（即層
數）要加一，并要求記住該盤的盤號．為了簡化程
序設計，這里定義了一個集合類形的數據，Ｄｉ
ｍ
ｌ
ｉ
ｎ（１
Ｔｏ ３）Ａｓ
Ｎｅｗ Ｃｏｌ
ｌ
ｅｃｔｉ
ｏｎ，ｌ
ｉ
ｎ的下標１到３
，
表示三根柱子的柱號．它的每個元素為集合類
形，集合類似于數組，但可以比數組更靈活、更有
效的方式處理集合中數據項，它可以保存ＶＢ中
各種不同類型的數據．巧妙的是集合的兩個方法
ＡＤＤ、Ｒｅｍｏｖｅ即給集合增加和刪除一個項目正
好能模擬跟蹤每個柱子上園盤的增加和減少，而
集合的Ｃｏｕｎｔ屬性則自動記錄了每個柱子上園
［收稿日期１２０１１一ｌ
Ｏ一２１
［作者簡介］郭亞慶（１９７４－
－
），
女，陜西禮泉人，十堰職業技術學院電子工程系講師，主要從事計算機技術，
計算機信息管
理研究．
幾
—
ＹＹＳ—
ＺＸＢ Ｏ／
郭亞慶：漢諾塔的動態演示程序
盤的個數．這種數據的組織形式，為簡化程序設計
提供了極為便利條件．
４
園盤移動程序的設計
１、ｆｏｒｍ窗體設計：先將三根柱子繪制在屏幕
上，為了簡化程序，柱與柱之間必須保持等距離，
再繪制七個標簽框，三個命令按鈕．
２、初始化：
先輸人園盤個數Ｎ，利用循環在Ａ
柱（即第一根柱子）上自動產生Ｎ個大小不等，顏
色不同的園盤，產生一個園盤后，隨之執行
ｌ
ｉ
ｎ
（１）．Ａｄｄ ｉ
（ｉ從ｌ到Ｎ），給集合添加一個數據項ｉ
（即存人一個園盤編號），該柱頂層的園盤號就存
放在ｌｉ
ｎ（１）（１
ｉ
ｎ（１）．ｅｕｏｎｔ）中，因為移動一個園盤
必須取該柱頂層的園盤．
３、移動速度根據園盤的多少自己可輸入園盤
移動一次的延時時間，默認值為１０００毫秒，若為
默認值，
則Ｎ個盤移動時間為２ 一１秒
，程序執
行前后會自動顯示起始時間和終止時間，為了簡
化程序設計，延時直接調用ＡＰＩ函數．
４、園盤移動子程序ＹＤ的設計：這是動態演
示程序的關鍵和難點，ＹＤ（ＢｙＶａｌ
ｑｓ Ａｓ Ｉｎｔ
ｅｇｅｒ，
ＢｙＶａｌ
ＭＢ Ａｓ Ｉｎｔ
ｅｇｅｒ）形參ＱＳ為源柱號，ｍｂ為
目標柱號，在移動前先取源柱上本次要移動的盤
號，而Ｌｉ
ｎ（ｑｓ）（１
ｉ
ｎ（ｑｓ）．Ｃｏｕｎｔ）則為源柱最上層
的盤號．園盤移動分三個步驟：
１．上移：上移時Ｘ坐標值不變，Ｙ坐標值只
要高于柱子的高度．上移完后，執行
Ｌｉ
ｎ（ｑｓ）．Ｒｅｍｏｖｅ ｌ
ｉ
ｎ（ｑｓ）．Ｃｏｕｎｔ即在記錄源
柱盤數編號的集合中刪去一項，記錄源柱上的盤
數自動減１．
Ｂ．左右移動；Ｙ坐標值不變，Ｘ坐標值移動
的距離為目標柱號減去源柱號的差值乘以柱與柱
之間的距離）而左右方向則取決于目標柱號減去
源柱號差值的符號
Ｃ．下移：這是難點，因為下移的距離的不能
是一個統一的高度，否則會造成園盤重迭或盤與
盤之間有一定的距離，這里采用下移一個Ｙ坐標
的絕對值減去目標柱上的園盤數乘以園盤的高
度，下移后執行ｌ
ｉ
ｎ（ｍｂ）．Ａｄｄ ｉ，讓記錄目標柱上
盤數的集合要加ｌ，并記錄移動到目標柱上該盤
的所處的層數及盤號．
附園盤移動子程序如下：
Ｐｒｉ
ｖａｔ
ｅ Ｓｕｂ ＹＤ（ＢｙＶａｌ
ｑｓ
Ａｓ Ｉｎｔｅｇｅｒ，Ｂｙ—
Ｖａｌ
ｍｂ Ａｓ Ｉｎｔｅｇｅｒ）
ｌ—ｌ
ｉ
ｎ（ｑｓ）（１
ｉ
ｎ（ｑｓ）．Ｃｏｕｎｔ）
‘取源柱上即
將移動的盤號
ＳｈＡＰ（１）．Ｍｏｖｅ Ｓ Ｐ（
Ｉ）．Ｌｅｆ
ｔ，５００，
向上移動
ｌ
ｉ
ｎ（ｑｓ）．Ｒｅｍｏｖｅ
ｌｉ
ｎ（ｑｓ）．Ｃｏｕｎｔ
‘從記錄
源柱盤號的集合中刪去一項
Ｓｌ
ｅｅｐ ＳＤ／２
‘延時
ＳｈＡＰ（Ｉ）．Ｍｏｖｅ ＳｈＡＰ（Ｉ）．Ｌｅｆ
ｔ＋
（ｍｂ—
ｑｓ）＊５０００，ＳｈＡＰ（Ｉ）．Ｔｏｐ左右移動
Ｓｌ
ｅｅｐ ＳＤ／２
ＳｈＡＰ（Ｉ）．Ｍｏｖｅ ＳｈＡＰ（１）．Ｌｅｆｔ，４８００一
ｌ
ｉ
ｎ
（ｍｂ）．Ｃｏｕｎｔ，＊２００ 向下移動
ｌ
ｉ
ｎ（ｍｂ）．Ａｄｄ Ｉ
‘給記錄目標柱盤號的集
合中增加一項
Ｅｎｄ Ｓｕｂ
Ｐｒｉｖａｔｅ Ｓｕｂ Ｃｏｍｍａｎｄ３
一
Ｃｌ
ｉ
ｃｋ（）
Ｅｎｄ
Ｅｎｄ Ｓｕｂ
Ｓｕｂ ＨＮＴ（Ｎ，Ａ Ａｓ Ｓｔｒｉ
ｎｇ，Ｂ Ａｓ
Ｓｔｒｉ
ｎｇ，Ｃ
Ａｓ Ｓｔｒｉｎｇ）
Ｉｆ Ｎ
＝
１ Ｔｈｅｎ
ＹＤ Ａ。Ｃ
Ｅｌｓｅ
ＣａＵ ＨＮＴ（Ｎ一
１，Ａ，Ｃ，Ｂ）
ＹＤ Ａ。Ｃ
Ｃａｌ
ｌ
ＨＮＴ（Ｎ一
１，Ｂ，Ａ，Ｃ）
Ｅｎｄ Ｉｆ
Ｅｎｄ Ｓｕｂ［
Ｚ３
５
結論
動態演示過程是教學史上的一大進步和創
舉，直觀的畫面圖像及聲音再現課堂，克服了傳統
教學過于抽象和難以理解的缺陷，有利于調動學
生學習的積極性，培養學生的思維能力和解決問
題的能力，本文利用集合類型的數據開發了一個
簡單的動態演示程序，但愿對一線程序設計教學
的教師有所幫助．
［參考文獻］
Ｅｌ３龔沛曾．ＶＩＳＵＡＬ ＢＡＳＩＣ程序設計簡明教程［Ｍ］．北京：高教
出版社，２００１．
［２］劉炳文．精通ＶＩ
ＳＵＡＬ ＢＡＳＩ
Ｃ６．０中文版［Ｍ］．北京：電子工
業出版社，
２００１．
【編校：胡軍?！?nbsp;
Ａ Ｄｙｎａｍｉｃ Ｄｅｍｏｎｓｔｒａｔｉ
ｏｎ Ｐｒｏｇｒａｍ ｏｆ
Ｈａｎｏｉ Ｔｏｗｅｒ
ＧＵＯ Ｙａ—ｑｉ
ｎｇ
（Ｄｅｐａｒｔｍｅｎｔ ｏｆ
Ｅｌｅｃｔｒｉ
ｃ Ｅｎｇｉｎｅｅｒｉｎｇ．Ｓｈｉｙａｎ Ｔｅｃｈｎｉ
ｅａｌ
Ｉｎｓｔｉ
ｔｕｔｅ．Ｓｈｉ
ｙａｎ ４４２０００，Ｃｈｉ
ｎａ）
Ａｂｓｔｒａｃｔ：Ｉｎ ｐｒｏｇｒａｍ ｄｅｓｉ
ｇｎ，ｒｅｃｕｒｓｉ
ｖｅ ａｌ
ｇｏｒｉｔｈｍ ｈａｓ ａｌ
ｗａｙｓ ｂｅｅｎ ａ ｔｅａｃｈｉ
ｎｇ ｄｉｆ
ｆｉ
ｃｕｌｔｙ．Ａ ｄｙｎａｍｉｃ ｄｅｍｏｎｓｔｒａｔｉ
ｏｎ
ｐｒｏｇｒａｍ ｏｆ Ｈａｎｏｉ
Ｔｏｗｅｒ ｈａｓ ｂｅｅｎ ｄｅｓｉｇｎｅｄ ｔＯ ｈｅｌｐ ｓｔｕｄｅｎｔｓ ｕｎｄｅｒｓｔａｎｄ ｒｅｅｕｒｓｉｖｅ ｔｒａｎｓｆｅｒ ａｓ ｔｏ ｍａｋｅ ｃｏｍｐｌｅｘ ｔ
ｅａｃｈｉ
ｎｇ
ｄｉｒｅｃｔ
ａｎｄ ｖｉｖｉ
ｄ ｗｉ
ｔｈ ａ ｐｕｒｐｏｓｅ ｏｆ ｉ
ｍｐｒｏｖｉ
ｎｇ ｔ
ｅａｃｈｉ
ｎｇ ｑｕａｌｉ
ｔｙ．
Ｋｅｙ ｗｏｒｄｓ：ｒｅｃｕｒｓｉｖｅ ａｌｇｏｒｉ
ｔｈｍ；ｄｙｎａｍｉ
ｃ ｄｅｍｏｎｓｔｒａｔｉ
ｏｎ；ｓｅｔ；ｐｒｏｇｒａｍ ｓｉｍｐｌｉ
ｆｙｉ
ｎｇ
ｎ
—
ＹＹＳ—
Ｚ
ＸＢ ｂ
２
＝
；