圖形環境下的漢諾塔演示

衛洪春

（四川文理學院 計算機科學系，四川 達州 635000）

漢諾塔（Hanoi）是一個古老而經典的問題，自出現以來，就一直受到人們的關注。在當今信息時代，仍有很多人在研究它，包括研究該問題的規模、思想、算法、顯示方式、游戲、不同開發環境下的實現方式等。但相當部分仍是基于控制臺模式下的字符顯示方式，這使得該問題的解決很不直觀。本文擬探討基于MFC圖形環境下的漢諾塔遞歸移動的演示過程，以期能更好地顯示該問題本身。

圖1 漢諾塔Fig.1 Hanoi towe

1 提出問題

漢諾塔（Hanoi）問題描述：設有三根針 A，B，C，請將大小不同、依小到大放置在A針上的n個圓盤移動到C針上。要求：每次只移動一個圓盤；圓盤可以插到A，B，C中任一針上；任何時候不能將一個較大的圓盤壓在較小的圓盤之上，如圖1所示。

這是一個經典的遞歸求解問題[1-3]。在console模式下的C++語言代碼如下：

void Hannoi （char a，char b，char c，int n）{if （n==1）{cout＜＜a＜＜“---＞”＜＜c＜＜endl； return； }

圖2 初始狀態Fig.2 Initial state

Hannoi （ a， c， b， n-1）； cout＜＜a＜＜“---＞”＜＜c＜＜endl；Hannoi（ b， a， c， n-1）；

}

當執行 Hannoi（‘A’，‘B’，‘C’，3）；語句后，結果如下：

A---＞C A---＞B C---＞B A---＞C B---＞A B---＞C A---＞C

該問題的求解在控制臺模式下的運算結果不直觀。本文是在控制臺遞歸算法的基礎上，研究了圖形模式下的算法。在圖形模式下演示漢諾塔的移動過程，關鍵是將控制臺下的輸出語句轉變為圖形繪制，以達到演示效果。下面分析該問題在圖形模式下的求解過程。

2 設計圓盤類

A針上的n個圓盤具有相似性，可以設計一個圓盤類，每個圓盤是圓盤類的一個對象。分析繪制該圓盤的屬性，可抽象如下的數據成員：圓盤的左上角坐標，圓盤的寬度和高度，是否繪制圓盤的標識（TRUE，繪制圓盤；FALSE，不繪制圓盤）。設計成員函數：繪制圓盤、構造函數、拷貝構造函數、重載“=”運算符[4-5]。所有成員均設計成public，如表1所示。

表1 圓盤類Cdisk的結構Tab.1 Structure of class CDisk

實現圓盤類：

CDisk::CDisk（）{m_bLive=false； }

CDisk::CDisk （int leftx，int lefty，int width，int hight）{初始化數據成員；且m_bLive=true；}

CDisk::CDisk（CDisk&disk）{將 disk對象的數據成員分別賦給當前對象的數據成員}

CDisk&CDisk::operator=（CDisk&disk）{初始化當前對象的數據成員；return*this；}

void CDisk::DiskDraw（BOOL flag，CDC*pDC）{ if（flag）{繪制該圓盤，即畫一個矩形框}}

3 繪圖過程

3.1 分析求解過程

設A針上有n個盤子，首先在B針、C針上分別構建n個與A針完全相同的圓盤，并設B針、C針上的所有圓盤均不繪制，如圖2所示的虛線矩形框。在初始狀態時，由于圖2中B針、C針上的圓盤不可見，因此只繪制A針上的圓盤，如圖1所示。

假設位于A針上面的i-1個圓盤已從A針移走（例如移到了B針）后，此時應將A針上第i個圓盤移走，則設置A針上第i個圓盤不可見（FALSE）；假設A針上的第i個圓盤應移到C針，則設置C針上第i個圓盤可見。此時在A、B、C針上畫出的圓盤沒有在理想的位置，如圖3所示。此時可根據某針上可見的圓盤數修改可見圓盤的左上角的坐標分量y，但圓盤左上角的坐標分量x、寬度、高度（h）均不變。例如，圖3中，B針上現有m=i-1個可見圓盤，則B針上的1號圓盤離基準繪制線的高度是：m*h，2號圓盤離基準繪制線的高度是：（m-1）*h，依次類推。當分別修改 A、B、C針上所有可見圓盤的坐標分量y后，重畫A、B、C針上的可見圓盤，可實現圖形環境下圓盤移動過程的演示，如圖4所示。

圖3 移動中的狀態（沒有修改y）Fig.3 State during moving（y is not modified）

圖4 移動中的狀態（已修改y）Fig.4 State during moving（y has been modified）

在VC6.0環境下，新建基于單文檔的工程HanoiDemo[6]。為了實現圖形環境下的Hanoi問題的求解，經過分析，主要是在視圖類中完成求解過程。

3.2 設計視圖類

在系統生成的視圖類中添加以下成員：

CDisk *a_Role， *b_Role， *c_Role；//分別指向 A、B、C針上的圓盤

int m_diskNum，diskH；//圓盤總數及單個圓盤的高度int ma，mb，mc； //分別表示某時刻 A、B、C 針上的應繪制圓盤的數目

int basey，halfW； //放圓盤的基線位置及圓盤單位寬度的一半

int ax，bx，cx； //A針、B針、C針的x坐標

int hi，sleepTime； //針的高度及暫停時間

void HanoiMove （char A，char B，char C，int n，CDC*pDC）； //遞歸繪制

void InitData（）；//初始化添加的數據成員

afx_msg void OnMoveHanoi（）； //響應菜單消息

3.3 實現演示過程

1）在InitData（）函數中初始化視圖類中新添加的數據成員，詳細設計如下：

void CHanoiDemoView::InitData（）{

初始化 sleepTime、basey；A、B、C 針所在位置的鉛垂線的x坐標；

初始化圓盤的高度為固定值diskH=20；圓盤總數m_diskNum=5；

單位半寬halfW=100/m_diskNum，針的高度hi=（m_diskNum+1） *diskH；

分別為 a_Role、b_Role、c_Role分配 m_diskNum個 CDisk類大小的空間

for（int i=m_diskNum； i＞ 0 ； i--）{

根據第i個圓盤的左上角點的坐標及寬高分別新建三個圓盤類對象，

并分別賦給 a_Role[i-1]、b_Role[i-1]、c_Role[i-1]。

置b_Role[i-1].m_bLive、c_Role[i-1].m_bLive為不繪制FALSE。

}}

2）在視圖類的構造函數初始化數據成員

CHanoiDemoView::CHanoiDemoView（）{InitData（）；/* 初始化數據成員*/}//構造函數

3）在OnDraw（）函數是繪制漢諾塔的初始狀態

void CHanoiDemoView::OnDraw（CDC*pDC）{

若 a_Role、b_Role、c_Role 非空，則分別刪除

InitData（）； //初始化添加的數據成員

循環繪制a_Role所指向的A針上的所有圓盤

}

運行后，繪制漢諾塔的初始狀態，如圖1所示。

HH-6數型顯恒溫水浴鍋，上海國華公司產品；UV-1750型紫外可見分光光度計，島津儀器（蘇州）有限公司產品；BS210S型電子分析天平，北京賽多利斯儀器系統有限公司產品；MJ-250PP01B型榨汁機，廣東美的公司產品。

4）設置菜單及其響應函數OnMoveHanoi（）

在OnMoveHanoi（）中調用漢諾塔演示遞歸函數。

void CHanoiDemoView::OnMoveHanoi（）{RedrawWindow（）； /*重繪窗口*/

CDC*pDC=GetDC（）； //獲取設備上下文

HanoiMove （‘A’，‘B’，‘C’，m_diskNum，pDC）； //遞歸演示Hanoi塔的移動過程

ReleaseDC（pDC）； //釋放設備上下文

}

5）漢諾塔演示遞歸函數HanoiMove（）

void CHanoiDemoView::HanoiMove （char A，char B，char C，int n，CDC*pDC）{

int i；

if（n==1）{ 復制從“//開始”到“//結束”間的所有 代碼 ；return；}

HanoiMove（A，C，B，n-1，pDC）； //遞歸調用

//開始

pDC-＞SetROP2 （R2_WHITE）；//設 置 ROP 方 式 為R2_WHITE

for（i=0； i＜ m_diskNum； i++）{ 重繪，清除原來 A、B、C三個針上的所有圓盤 }

switch（A）{//判斷此時從何針移走圓盤，從而設置該針對應圓盤下次不繪制

若從A針向其它針移動，則a_Role[n-1].m_bLive=false

若從B針向其它針移動，則b_Role[n-1].m_bLive=false

若從C針向其它針移動，則c_Role[n-1].m_bLive=false

}

switch（C）{//判斷此時將圓盤移到何針，并在下次繪制時該圓盤應繪制

若向A針移動，則a_Role[n-1].m_bLive=true

若向B針移動，則b_Role[n-1].m_bLive=true

若向B針移動，則c_Role[n-1].m_bLive=true

}

重置A、B、C針上當前應繪制的圓盤數ma=mb=mc=0

for（i=0； i＜ m_diskNum；i++）{//對 ma、 mb、 mc計數

若a_Role[i].m_bLive真，則A針上應繪制的圓盤數ma++；

若b_Role[i].m_bLive真，則B針上應繪制的圓盤數mb++；

若c_Role[i].m_bLive真，則C針上應繪制的圓盤數mc++；

}

for （i=0； i＜ m_diskNum；i++）{//修改 A、B、C 針第 i個圓盤左上角的y坐標

if（a_Role[i].m_bLive）{a_Role[i].m_lefty=baseyma*diskH； ma--；}

if（b_Role[i].m_bLive）{b_Role[i].m_lefty=baseymb*diskH； mb--；}

if（c_Role[i].m_bLive）{c_Role[i].m_lefty=baseymc*diskH； mc--；}

}

pDC-＞SetROP2 （R2_BLACK）； //設置 ROP 方式為 R2_BLACK

for （i=0；i＜ m_diskNum；i++）{根據標識為 TRUE，重繪 A、B、C針上的圓盤 }

Sleep（sleepTime）； //暫停

//結束

HanoiMove（B，A，C，n-1，pDC）；//遞歸

}

調用HanoiMove（）函數后，結果如圖5所示。

圖5 移動后的結果Fig.5 Result after moving

4 結束語

文中討論并實現了圖形環境下，漢諾塔問題遞歸求解的過程。它將基于控制臺模式的單調、枯燥的顯示過程轉換為直觀的、圖形化的移動過程，對于更好地理解遞歸程序設計有較好的幫助。

[1]姚云霞.對漢諾塔（Hanoi）問題的算法探索與研究[J].物聯網技術，2013（7） :48-49.YAO Yun-xia.Exploration and research on the tower of hanoi algorithm[J].Internet of Things Technologies，2013（7）:48-49.

[2]白會波，高瑞平.漢諾塔問題的算法分析及C語言演示程序的實現[J].電腦知識與技術，2010（9）:2130-2131.BAIHui-bo，GAORui-ping.Algorithmanalysisand Crealization of Hanoi issue[J].Computer Knowledge and Technology，2010（9）:2130-2131.

[3]肖桂云，袁亞麗.用C語言解決漢諾塔問題的方法及過程分析[J].河北北方學院學報：自然科學版，2006（3）:71-73.XIAO Gui-yun，YUAN Ya-li.Methods and course analysis of solving hanoi problems with clanguage[J].Journal of Hebei North University：Natural Science Edition，2006（3）:71-73.

[4]俞哲明，樊艷芬.漢諾塔問題的算法設計及C++語言實現[J].福建電腦，2012（9）:138-150.YU Zhe-ming，FAN Yan-fen. Algorithm design and implementation on hanoi tower based on C++ [J].Fujian Computer，2012（9）:138，150.

[5]馬苗，田紅鵬.“面向對象程序設計與C++”教學中的問題與思考[J].計算機教育，2008（6）:81-82.MA Miao，TIAN Hong-peng.Problems and thoughts on the teaching of “Object-oriented programming with C++”[J].Computer Education，2008（6）:81-82.

[6]衛洪春.COCH圖形的遞歸與非遞歸算法研究[J].計算機與信息技術，2011（12）:42-46.WEI Hong-chun.Recursive and non-recursive algorithm research on COCH graphics[J].Computer&Information Technology，2011（12）:42-46.