衛(wèi)洪春

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

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

圖1 漢諾塔Fig.1 Hanoi towe

1 提出問題

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

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

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

圖2 初始狀態(tài)Fig.2 Initial state

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

}

當執(zhí)行 Hannoi（‘A’，‘B’，‘C’，3）；語句后，結(jié)果如下：

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

該問題的求解在控制臺模式下的運算結(jié)果不直觀。本文是在控制臺遞歸算法的基礎(chǔ)上，研究了圖形模式下的算法。在圖形模式下演示漢諾塔的移動過程，關(guān)鍵是將控制臺下的輸出語句轉(zhuǎn)變?yōu)閳D形繪制，以達到演示效果。下面分析該問題在圖形模式下的求解過程。

2 設(shè)計圓盤類

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

表1 圓盤類Cdisk的結(jié)構(gòu)Tab.1 Structure of class CDisk

實現(xiàn)圓盤類：

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

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

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

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

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

3 繪圖過程

3.1 分析求解過程

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

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

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

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

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

3.2 設(shè)計視圖類

在系統(tǒng)生成的視圖類中添加以下成員：

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

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

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（）；//初始化添加的數(shù)據(jù)成員

afx_msg void OnMoveHanoi（）； //響應(yīng)菜單消息

3.3 實現(xiàn)演示過程

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

void CHanoiDemoView::InitData（）{

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

初始化圓盤的高度為固定值diskH=20；圓盤總數(shù)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--）{

根據(jù)第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）在視圖類的構(gòu)造函數(shù)初始化數(shù)據(jù)成員

CHanoiDemoView::CHanoiDemoView（）{InitData（）；/* 初始化數(shù)據(jù)成員*/}//構(gòu)造函數(shù)

3）在OnDraw（）函數(shù)是繪制漢諾塔的初始狀態(tài)

void CHanoiDemoView::OnDraw（CDC*pDC）{

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

InitData（）； //初始化添加的數(shù)據(jù)成員

循環(huán)繪制a_Role所指向的A針上的所有圓盤

}

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

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

4）設(shè)置菜單及其響應(yīng)函數(shù)OnMoveHanoi（）

在OnMoveHanoi（）中調(diào)用漢諾塔演示遞歸函數(shù)。

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

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

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

ReleaseDC（pDC）； //釋放設(shè)備上下文

}

5）漢諾塔演示遞歸函數(shù)HanoiMove（）

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

int i；

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

HanoiMove（A，C，B，n-1，pDC）； //遞歸調(diào)用

//開始

pDC-＞SetROP2 （R2_WHITE）；//設(shè) 置 ROP 方 式 為R2_WHITE

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

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

若從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）{//判斷此時將圓盤移到何針，并在下次繪制時該圓盤應(yīng)繪制

若向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針上當前應(yīng)繪制的圓盤數(shù)ma=mb=mc=0

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

若a_Role[i].m_bLive真，則A針上應(yīng)繪制的圓盤數(shù)ma++；

若b_Role[i].m_bLive真，則B針上應(yīng)繪制的圓盤數(shù)mb++；

若c_Role[i].m_bLive真，則C針上應(yīng)繪制的圓盤數(shù)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）； //設(shè)置 ROP 方式為 R2_BLACK

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

Sleep（sleepTime）； //暫停

//結(jié)束

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

}

調(diào)用HanoiMove（）函數(shù)后，結(jié)果如圖5所示。

圖5 移動后的結(jié)果Fig.5 Result after moving

4 結(jié)束語

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

[1]姚云霞.對漢諾塔（Hanoi）問題的算法探索與研究[J].物聯(lián)網(wǎng)技術(shù)，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語言演示程序的實現(xiàn)[J].電腦知識與技術(shù)，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].河北北方學(xué)院學(xué)報：自然科學(xué)版，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]俞哲明，樊艷芬.漢諾塔問題的算法設(shè)計及C++語言實現(xiàn)[J].福建電腦，2012（9）:138-150.YU Zhe-ming，F(xiàn)AN Yan-fen. Algorithm design and implementation on hanoi tower based on C++ [J].Fujian Computer，2012（9）:138，150.

[5]馬苗，田紅鵬.“面向?qū)ο蟪绦蛟O(shè)計與C++”教學(xué)中的問題與思考[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]衛(wèi)洪春.COCH圖形的遞歸與非遞歸算法研究[J].計算機與信息技術(shù)，2011（12）:42-46.WEI Hong-chun.Recursive and non-recursive algorithm research on COCH graphics[J].Computer&Information Technology，2011（12）:42-46.