摘要:該文對經典的“漢諾塔”問題進行了詳細的分析,并用C語言實現。通過問題的具體實現,使學習者了解問題的全過程,推廣到一般。

關鍵詞:漢諾塔;遞歸;C語言

中圖分類號:TP301.6文獻標識碼:A文章編號:1009-3044(2010)09-2130-02

Algorithm Analysis and C Realization of Hanio Issue

BAI Hui-bo1,GAO Rui-ping2

(1.Qinhuangdao Branch of Daqing Petroleum Institute, Qinhuangdao 066004, China;2.Hebei Normal University of Science and Technology, Qinhuangdao 06600, China)

Abstract: This text carries on detailed analysis about classical Hanio issue and provides realization of algorithm in C.Through concrete realization of the problem,can make learners observe the whole course which solves this issue and Extend to the general.

Key words: hanio; recursive; the C programming language

1 問題描述

漢諾塔是一個經典的數學問題,其具體描述如下:有三根相鄰的塔子,標號為A,B,C,A塔子上從下到上按金字塔狀疊放著n個不同大小的圓盤,現在把所有盤子借助于A,B,C三個塔子一個一個移動到塔子C上,并且每次移動在同一根塔子上都不能出現大盤子在小盤子上方.根據問題描述得到以下規則:

1)圓盤必須一個一個的移動;

2)大的圓盤必須在小圓盤的下方或單一圓盤;

3)滿足規則2)的序列可以出現在A,B,C任意一根塔子上。

C語言演示程序規則:

1)輸入一個盤子的個數n(時間可接受范圍內的值0

2)用C語言演示盤子在塔A,B,C間的移動全過程。

2 算法分析

題目實現的是設計一個盤子移動的方案,使得A塔上的所有盤子借助于B塔按照原來的次序移動到C塔上,并且給出完整的最佳的盤子移動的方案。

從實際的具體的盤子的移動過程來分析,找出問題內在的規律。當n=1時,問題比較簡單,只要將塔A上的編號為1盤子直接移動到塔C即可;當n>1時,需利用塔B作為輔助塔,若能設法將壓在編號為n的盤子之上的n-1個盤子從塔A(依據移動規則)移至塔B上,則可將編號為n的盤子從塔A移至塔C,然后再將塔B上的n-1個盤子(依據移動規則)移至塔C;經分析可知,在移動的過程中, 將始終會出現這樣的狀態情況: (n-1)個盤子將會以從下到上、從大到小的次序疊置在B塔上,這時,A塔上第n個盤子就能被輕而易舉疊放到C塔上; 接著, 我們再把B塔上的共(n-1)個盤子移動到C塔上, 問題好像已經解決。

但B塔上(n-1)個盤子怎么移動到C塔上呢?同樣, 利用塔C作為輔助塔, 將會出現這樣的狀態情況:(n-2)個盤子將會以從上到下、從小到大的次序疊置在A塔上,這時,B塔上第(n-2)個盤子就能被輕而易舉放到C塔上;接著,把A塔上的共(n-2)個盤子移動到C塔上。

這明顯是一個遞歸的過程,不斷深入,不斷細小化,最終,將到達僅有一個盤的情形,這時, 遞歸也就終止了,問題也得到了解決。通過以上分析,遞歸的出口是當n=1時,能直接得到解。現在,嚴格按照遞歸算法來解決問題。先定義遞歸方法Hanio(int n,zarray * A, zarray *B, zarray *C),按如下步驟進行解題(設初始盤子個數為N):若A塔上僅僅只有一個盤子(n=1), 則直接從A移動到C,問題完全解決。若A塔上有一個以上的盤子(n>1),則需要考慮以下三個步驟。

第一步: 把(n-1)個盤子從A塔經過移動, 疊放到C塔上。在不違反規則情況下,所有(n-1)個盤子不能作為一個整體一起移動,而是要符合要求地從一個塔移到另一個塔上。用Hanio(n-1,A,C,B)調用遞歸方法,注意:這里是借助于C塔,將(n-1)個盤子從A塔移動到B塔, A是源塔, B是目標塔。

第二步: 將剩下的第n個盤子(也就是最底下的一個)直接從A塔疊放到空著的C塔上。

第三步: 用第一步的方法,再次將B塔上的所有盤子疊放到C塔上。同樣,這一步實際上也是由一系列更小的符合規則的移動盤子的操作組成的。用Hanio(n-1,B,A,C)調用遞歸方法, 注意:這里是借助于A塔,將(n-1)個盤子從B塔移動到C塔,B是源塔,C是目標塔。這個算法達到了預期的目標,即在C塔上按正確的次序疊放了所有的圓形盤子。

3 算法實現

定義結構體plate表示盤子:typedef struct

{ int x,y,xsize,ysize;/*盤子通過繪制橢圓實現,x,y,xsize,ysize確定橢圓的大小*/

int No;/*盤子的編號,編號為0的表示塔柱,大于零的是盤子*/

}plate;

定義一個堆棧zarray來表示塔:typedef struct

{plate p[INIT_SIZE];

int top;/*棧頂*/

int x,y,xof,yof; /*塔的繪制視區*/

}zarray;

用zarray的三個變量A、B、C分別表示三個塔,初始盤子在A塔,設置屏幕繪制區域并相對與繪制區域分別繪制A、B、C三塔、盤子,并在相應盤子的位置標明其編號(編號和盤子一起移動)調用hanoi()函數,并在move()函數中源塔和目標塔的盤子進行繪制。

程序的主要函數由:initZarray(),setLongth(),getplate(),pushplate(),popplate(), outNo(),toDraw(),toDrawZhu(),getn(),hanoi(),move()等組成。

initZarray()負責塔A,B,C數據的初始化, pushplate()負責將盤子壓入目標塔中,并對新壓入的盤子進行繪制,popplate()負責從源塔取下一個盤子,并對源塔進行重新繪制。

1)函數main()的算法

函數main()的算法如圖1,程序執行用戶根據提示輸入合法的n值,根據得到的n值初始化塔A,B,C和n個盤子的大小,設置繪圖視區在屏幕上繪制塔A,B,C和盤子,調用hanoi()函數。

2)函數hanoi()的算法

函數hanoi()的算法如圖1,當程序第一被調用時,源塔A有n個盤子,將塔C作為輔助塔,調用move()函數將源塔A上的n-1個盤子移至塔B上,將源塔A上的編號為n的盤子移到目標塔C,完成將最大盤子移至目標塔C,接下來,將塔B作為源塔有n-1個盤子,塔A作為輔助塔遞歸調用,每次都將源塔上的最大盤子移至目標塔,直到遞歸結束。

3)函數move()的算法

函數move()的算法如圖2,函數的作用就是調用popplate()函數,將源塔出棧重繪,再將出棧的盤子p調用pushplate()函數壓入目標塔,重新繪制。popplate()函數和pushplate()見圖2。

4 結束語

本文深入分析了用遞歸實現漢諾塔的問題,并用圖形仿真程序顯示的盤子的移動過程,對漢諾塔的本質進行了新的剖析,對數據結構的教學有一定的好處。

參考文獻:

[1] 嚴蔚敏,吳偉民.數據結構[M].北京:清華大學出版社,1996.

[2] 王強如.C語言繪圖與計算機仿真技術[M].北京:北京航空航天大學出版社,1995.