漢諾塔hanoi問題

1、實驗題目：棧的應用實驗內(nèi)容：Hanoi塔問題。（要求4個盤子移動，輸出中間結果）實驗目的：（1）掌握棧的特點及其存儲方法；（2）掌握棧的常見算法以及程序實現(xiàn)；（3）了解遞歸的工作過程。設計分析：Hanoi塔問題要求實現(xiàn)將一定數(shù)目n的直徑各不相同的盤子從A塔移動到C塔，盤子事先在A中已經(jīng)按直徑大小從小到大層疊好了，越往底層直徑越大，規(guī)定每次只能移動一個盤子，且不能出現(xiàn)小盤子上面有大盤子的情況?？梢杂眠f歸的方法實現(xiàn)。先考慮最簡單的情況，假設

2、n=1，即只有一個盤子，此時便可直接將其從A移動到C；n=2時，小盤在上，大盤再下，此時可以借用中間的B塔來運輸，即先將小盤從A移至B，再將大盤從A移至C，最后將小盤從B移至C，這樣便不會出現(xiàn)小盤在下，大盤在上的情況；然而當n越來越大時，移動的次數(shù)就會越來越多，看起來好像很復雜，其實其中的基本思想很簡單：若A塔上有n個盤子，要將其全部移至C塔中，由于最底層盤的直徑最大，則就要將其上面的n1個盤子移至中間的B塔，再將最底層的盤子移至C塔上

3、，完成這個工作后，就會發(fā)現(xiàn)下一步就是將中間B塔上的n1個盤子移至C塔上，這就和第一步的工作類似了，只不過盤子少了一個，且所處的塔也發(fā)生了變化，此時可將A塔作為傳輸中介，將B塔上面的n2個盤子移至A塔，之后再將第n1個盤子移至C中，這樣重復進行下去就可以將它們?nèi)窟\輸過去。而對于第一步工作中將上面n1個盤子移至B，則又需要將其上n2個盤子移至此時視為傳輸中介的C，完成這一步又要將其上的n3個盤子移至B，像這樣層層遞歸進去，最終就會知道第一

4、個盤子及最上面直徑最小的盤子先移到何處，這即為遞歸出口，而后的盤子移動方案也都確定了，最終就可將所有的盤子按規(guī)則移至C塔，至此，Hanoi塔問題得以解決。源程序代碼：#includevoidMove(AB)printf(“%c%cn“AB)voidHanoi(intnABC)圖33當n=2時輸出移動過程如圖33所示，第一步A?B表示將A最上面的盤子（直徑小的）移至B，A?C則表示將A最上面的盤子（直徑大的）移至C，最后在將B最上面的盤子

5、移至C即可。圖34當n=3時輸出移動過程如圖34所示，此時需要7步完成整個過程，隨著n值的增大，移動的步數(shù)也隨之增多，總結可得移動步數(shù)S與n的關系為S=2n1。實驗總結：通過此次對Hanoi塔問題的探索與解決，我了解了遞歸算法的原理和功能，原本看起來很復雜的問題模型，用遞歸函數(shù)調(diào)用僅幾個簡單的程序語句就表達出來了，體現(xiàn)出遞歸算法的高效性，很多問題都可以用遞歸算法實現(xiàn)，簡單的如求階乘，通過調(diào)用自身程序代碼實現(xiàn)遞歸。今后我會嘗試著用遞歸算法