漢諾塔實驗報告

實驗報告課程名稱數(shù)據(jù)結(jié)構(gòu)實驗名稱漢諾塔實驗類型驗證性實驗實驗地點計304機房實驗日期指導(dǎo)教師魏海平專業(yè)計算機科學(xué)與技術(shù)班級計算機1002學(xué)號20姓名張森遼寧石油化工大學(xué)計算機與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實驗報告評分表項目要求分?jǐn)?shù)有無項目（√）得分預(yù)習(xí)報告（30分）實驗?zāi)康拿鞔_5實驗內(nèi)容理解透徹5實驗方案設(shè)計完整合理程序總體框架設(shè)計完整10完成相關(guān)輔助代碼5測試方案合理5實驗過程（30分）發(fā)現(xiàn)問題5問題的分析15問題的解決方法10實驗報告（20分）內(nèi)容翔實無缺漏5如實記錄實驗過程10撰寫規(guī)整5實驗總結(jié)（10分）實驗結(jié)果的分析5按照結(jié)果對原實驗方案的改進(jìn)意見5實驗體會（10分）實驗的收獲5實驗內(nèi)容的發(fā)散考慮5總分1.實驗?zāi)康模和ㄟ^本實驗，掌握復(fù)雜性問題的分析方法，了解漢諾塔游戲的時間復(fù)雜性和空間復(fù)雜性。2.問題描述：

漢諾塔問題來自一個古老的傳說：在世界剛被創(chuàng)建的時候有一座鉆石寶塔（塔A),其上有64個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個鉆石寶塔（塔B和塔C）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動到塔C上去，其間借助于塔B的幫助。每次只能移動一個碟子，任何時候都不能把一個碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時，世界末日也就到了。3.算法設(shè)計思想：

對于漢諾塔問題的求解，可以通過以下三個步驟實現(xiàn)：

(1)將塔A上的n-1個碟子借助塔C先移到塔B上。

(2)把塔A上剩下的一個碟子移到塔C上。

(3)將n-1個碟子從塔B借助于塔A移到塔C上。4.實驗步驟：用c++或c語言設(shè)計實現(xiàn)漢諾塔游戲；讓盤子數(shù)從2開始到7進(jìn)行實驗，記錄程序運行時間和遞歸調(diào)用次數(shù)；畫出盤子數(shù)n和運行時間t、遞歸調(diào)用次數(shù)m的關(guān)系圖，并進(jìn)行分析。實驗內(nèi)容及實驗結(jié)果請寫出具體的實驗步驟，并給出相應(yīng)的實驗結(jié)果，附上編寫的程序及其運行結(jié)果截圖!!#include<stdio.h>voidhanio(intn,charA,charB,charC){if(n==1)printf("Movediskfrom%cto%c\n",A,B);else{hanio(n-1,A,C,B);printf("Movediskfrom%cto%c\n",A,B);hanio(n-1,C,B,A);}}voidmain(){intn;printf("inputthenumberofdisk:");scanf("%d",&n);printf("thestepsfor%ddiskare:\n",n);hanio(n,'A','B','C');}運行結(jié)果：7、結(jié)論通過對上述遞歸在Hanoi塔問題上的應(yīng)用分析，我們可以得出如下結(jié)論：1、遞歸調(diào)用過程中，在程序執(zhí)行之前無法知道控制這種調(diào)用棧的規(guī)模，因為這一規(guī)模取決于遞歸調(diào)用的次序。在這種情況下，程序的地址空間可能動態(tài)變化；2、遞歸應(yīng)用于程序設(shè)計時，結(jié)構(gòu)清晰、程序易讀，編制和調(diào)試程序很方便，不需要用戶自行管理遞歸工作棧。但遞歸應(yīng)用于計算機時需要占用大量系統(tǒng)資源（包括堆棧、軟中斷和存貯空間等），并消耗大量處理時間。因此，可以考慮采用并行計算進(jìn)行處理，但緩存大小3、遞歸是串行的，其第n步運算依賴于第n-1步運算，所以在計算機軟件理論上不存在遞歸問題并行計算的可能性。實際上是否