漢諾塔問題實驗報告

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

2、60;對于漢諾塔問題的求解，可以通過以下三個步驟實現(xiàn)：    (1)將塔A上的n-1個碟子借助塔C先移到塔B上。    (2)把塔A上剩下的一個碟子移到塔C上。    (3)將n-1個碟子從塔B借助于塔A移到塔C上。4.實驗步驟：1. 用c+ 或c語言設(shè)計實現(xiàn)漢諾塔游戲；2. 讓盤子數(shù)從2 開始到7進行實驗，記錄程序運行時間和遞歸調(diào)用次數(shù)；3. 畫出盤子數(shù)n和運行時間t 、遞歸調(diào)用次數(shù)m的關(guān)系圖，并進行分析。5.代碼設(shè)計：Hanio.cpp#include "std

3、afx.h"#include <stdlib.h> #include <stdio.h> #include <iostream>void hanoi(int n,char x,char y,char z) if(n=1) printf("從%c->搬到%cn",x,z); else hanoi(n-1,x,z,y);printf("從%c->%c搬到n",x,z);hanoi(n-1,y,x,z); void main() int m ; printf("input the number

4、 of diskes:"); scanf("%d",&m); printf("The step to moving %3d diskes:",m); hanoi(m,'a','b','c');自定義頭文件：#pragma once#include "targetver.h"#include <stdio.h>#include <tchar.h>結(jié)果如下： 6.遞歸應(yīng)用中的Hanoi塔問題分析1）Hanoi塔問題中函數(shù)調(diào)用時系統(tǒng)所做工作一個函數(shù)在運

5、行期調(diào)用另一個函數(shù)時，在運行被調(diào)用函數(shù)之前，系統(tǒng)先完成3件事：將所有的實參、返回地址等信息傳遞給被調(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)用函數(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)用先返回”的原則（LIFO），上述函數(shù)之間的信息傳遞和控制轉(zhuǎn)移必須通過“?！眮韺崿F(xiàn)，即系統(tǒng)將整個程序運行時所需的數(shù)據(jù)空間安排在一個棧中，每當(dāng)調(diào)用一個函數(shù)時，就為其在棧頂分配一個存儲區(qū)，每當(dāng)從一個函數(shù)退出時，就釋放其存儲區(qū)，因此當(dāng)前運行函數(shù)的數(shù)

6、據(jù)區(qū)必在棧頂。堆棧特點：LIFO，除非轉(zhuǎn)移或中斷，堆棧內(nèi)容的存或取表現(xiàn)出線性表列的性質(zhì)。正是如此，程序不要求跟蹤當(dāng)前進入堆棧的真實單元，而只要用一個具有自動遞增或自動遞減功能的堆棧計數(shù)器，便可正確指出最后一次信息在堆棧中存放的地址。一個遞歸函數(shù)的運行過程類型于多個函數(shù)的嵌套調(diào)用，只是調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)。因此，和每次調(diào)用相關(guān)的一個重要的概念是遞歸函數(shù)運行的“層次”。假設(shè)調(diào)用該遞歸函數(shù)的主函數(shù)為第0層，則從主函數(shù)調(diào)用遞歸函數(shù)為進入第1層；從第i層遞歸調(diào)用本函數(shù)為進入下一層，即i1層。反之，退出第i層遞歸應(yīng)返回至上一層，即i1層。為了保證遞歸函數(shù)正確執(zhí)行，系統(tǒng)需設(shè)立一個“遞歸工作?！?，

7、作為整個遞歸函數(shù)運行期間使用的數(shù)據(jù)存儲區(qū)。每一層遞歸所需信息構(gòu)成一個“工作記錄”，其中包括所有實參、所有局部變量以及上一層的返回地址。每進入一層遞歸，就產(chǎn)生一個新的工作記錄壓入棧頂。每退出一層遞歸，就從棧頂彈出一個工作記錄，則當(dāng)前執(zhí)行層的工作記錄必是遞歸工作棧棧頂?shù)墓ぷ饔涗洠Q這個記錄為“活動記錄”，并稱指示活動記錄的棧頂指針為“當(dāng)前環(huán)境指針”。2）Hanoi塔問題遞歸程序的復(fù)雜度分析 運行hanoi程序的時間程序 hanoi.c 在硬件環(huán)境為賽揚 400MHz、內(nèi)存128M的計算平臺（不同機器運行時間有一定差別）運行，可得出如下時間結(jié)果：盤子數(shù)    

8、   時間結(jié)果<=12個        <=1秒14個          2秒16個         13秒20個        204秒 時間復(fù)雜度程序所花時間正比于所輸出的信息行數(shù)目，而信息行的數(shù)目則等價于盤子的移動次數(shù)?？疾斐绦?，設(shè)盤子移動次數(shù)為mov

9、es（n），則：moves(n)=            用迭代方法計算公式，得到結(jié)果moves(n)=2n-1。因此，hanoi函數(shù)的時間復(fù)雜度為O(2 n) 。 空間復(fù)雜度       從每個塔上移走盤子時是按照LIFO進行，因此可以把每個塔表示成一個堆棧。3座塔在任何時候總共擁有的盤子都是n個。如果使用鏈表形式的堆棧，只需申請n個元素所需要的空間。如果使用的是基于公式化描述的堆棧，塔1和塔2的容量都必須是n，而塔3的容量是n1，因

10、此所需要的空間總數(shù)為3n1。Hanoi塔問題的復(fù)雜性是以n為指數(shù)的函數(shù)，因此在可以接受的范圍內(nèi)，只能解決n值比較?。╪<=30）的hanoi問題。對于這個較小的n值，堆棧在空間需求上的差別相當(dāng)小，可以隨意使用。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)資源（包括堆棧、軟中斷和存貯空間等），并消耗大量處理時間。因此，可以考慮采用