[精品]漢諾塔問題實(shí)驗(yàn)報告

《[精品]漢諾塔問題實(shí)驗(yàn)報告》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、1?實(shí)驗(yàn)?zāi)康模和ㄟ^本實(shí)驗(yàn)，掌握復(fù)雜性問題的分析方法，了解漢諾塔游戲的時間復(fù)雜性和空間復(fù)雜性。2.問題描述：漢諾塔問題來自一個古老的傳說：在世界剛被創(chuàng)建的吋候有一座鉆石寶塔(塔A),其上有64個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個鉆石寶塔(塔B和塔C)o從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動到塔C上去，其間借助于塔B的幫助。每次只能移動一個碟子，任何時候都不能把一個碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時，世界末日也就到了。3.算法設(shè)計思想：對于漢諾塔問題的求解，可以通過以下三個步驟實(shí)現(xiàn)：(

2、1)將塔A上的ml個碟子借助塔C先移到塔B上。(2)把塔A上剩下的一個碟子移到塔C上。(3)將n-1個碟子從塔B借助于塔A移到塔C上。4.實(shí)驗(yàn)步驟：1.用C++或c語言設(shè)計實(shí)現(xiàn)漢諾塔游戲；2.讓盤子數(shù)從2開始到7進(jìn)行實(shí)驗(yàn)，記錄程序運(yùn)行時間和遞歸調(diào)用次數(shù)；3.畫出盤子數(shù)n和運(yùn)行吋間t、遞歸調(diào)用次數(shù)m的關(guān)系圖,并進(jìn)行分析。5.代碼設(shè)計：Hanio.cpp#ir)elude"stdafx?h"^include#include#ineludevoidhanoi(inin,charx,chary,cha

3、rz)(if(n==l){printf("從%c?〉搬到%c，，>x,z);elsehanoi(nT,x,z,y);printfC從％c->%c搬到",x,z);hanoi(r>T,y,x,z);voidmainO{intm;printf("inputthenumberofdiskes:");scanf(”%d",&m);prinl￡("Thesteptomoving%3ddiskes:z，,m);hanoi(叫'「'b','c');自定義頭文件:^pragmaonce^include^targetver.h"#include

4、>^include結(jié)果如下:inputthenumberofdiskes：2rhesteptomouing2diskes：從a->搬到b趴a-兀搬到從b-〉槨至lieinputthenumberofdiskes：3Thesteptomouing3disk巳s：丿』、3一>搬￥[

5、c》、a->b搬到從c->搬到b畑-〉c搬到->搬弧從b->c搬到換2->搬孤^.nputthenunberofdiskes：4u->搬到￡”c->搬到從">搬到b'Aa->c搬到-〉搬或c”c->搬到從">搬到b'Aa->c搬到從、b->搬弧[Theste

6、ptomoving4diskes二從a->搬到b、a->c搬到Z.T~~■M一：pva->b搬到肛-〉搬到a從">b搬到從a->樓玉I.b''Aa->c搬到從b->搬孤從b->a搬到如-兀搬到辰-〉搬列b''Aa->c搬到6?遞歸應(yīng)用中的Hanoi塔問題分析1）Hanoi塔問題中函數(shù)調(diào)用吋系統(tǒng)所做工作一個函數(shù)在運(yùn)行期調(diào)用另一個函數(shù)時，在運(yùn)行被調(diào)用函數(shù)Z前，系統(tǒng)先完成3件事：①將所有的實(shí)參、返回地址等信息傳遞給被調(diào)用函數(shù)保存。②為被調(diào)用函數(shù)的局部變量分配存儲區(qū)；③將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。從被調(diào)用函數(shù)返回調(diào)用函數(shù)前，系統(tǒng)也應(yīng)完成3件事：①保存被調(diào)用

7、函數(shù)的結(jié)果；②釋放被調(diào)用函數(shù)的數(shù)據(jù)區(qū)；③依照被調(diào)用函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。當(dāng)有多個函數(shù)構(gòu)成嵌套調(diào)用時，按照“后調(diào)用先返回”的原則（L1FO）,上述函數(shù)之間的信息傳遞和控制轉(zhuǎn)移必須通過“棧”來實(shí)現(xiàn)，即系統(tǒng)將整個程序運(yùn)行時所需的數(shù)據(jù)空間安排在一個棧中，每當(dāng)調(diào)用一個函數(shù)時，就為其在棧頂分配一個存儲區(qū)，每當(dāng)從一個函數(shù)退出時，就釋放其存儲區(qū)，因此當(dāng)前運(yùn)行函數(shù)的數(shù)據(jù)區(qū)必在棧頂。堆棧特點(diǎn)：L1F0,除非轉(zhuǎn)移或中斷，堆棧內(nèi)容的存或取表現(xiàn)出線性表列的性質(zhì)。正是如此，程序不要求跟蹤當(dāng)前進(jìn)入堆棧的真實(shí)單元，而只要用一個具有自動遞增或自動遞減功能的堆棧計數(shù)器

8、，便可正確指出最后一次信息在堆棧中存放的地址。一個遞歸函數(shù)的運(yùn)行過程類型于多個函數(shù)的嵌套調(diào)用，只是調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)。因此，和每次調(diào)用相關(guān)的一個重要的概念是遞歸函數(shù)運(yùn)行的“層次”。假設(shè)調(diào)用該遞歸函數(shù)的主函數(shù)為第0層，則從主函數(shù)調(diào)用遞歸函數(shù)為進(jìn)入第1層；從第i層遞歸調(diào)用本函數(shù)為進(jìn)入下一層，即i+1層。反之，退出第i層遞歸應(yīng)返回至上一層，即i—1層。為了保證遞歸函數(shù)止確執(zhí)行，系統(tǒng)需設(shè)立一個“遞歸工作?！?，作為整個遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù)存儲區(qū)。每一層遞歸所需信息構(gòu)成一個“工作記錄”，其中包括所有實(shí)參、所有局部變量以及上一層的返冋地址。每進(jìn)

9、入一層遞歸，就產(chǎn)生一個新的工作記錄壓入棧頂。每退出一層遞歸，就從棧頂彈出一個工作記錄，則當(dāng)前執(zhí)行層的工作記錄