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

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

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

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

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