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

2、60;對于漢諾塔問題的求解，可以通過以下三個步驟實現：    (1)將塔A上的n-1個碟子借助塔C先移到塔B上。    (2)把塔A上剩下的一個碟子移到塔C上。    (3)將n-1個碟子從塔B借助于塔A移到塔C上。4.實驗步驟：1. 用c+ 或c語言設計實現漢諾塔游戲；2. 讓盤子數從2 開始到7進行實驗，記錄程序運行時間和遞歸調用次數；3. 畫出盤子數n和運行時間t 、遞歸調用次數m的關系圖，并進行分析。5.代碼設計：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>結果如下： 6.遞歸應用中的Hanoi塔問題分析1）Hanoi塔問題中函數調用時系統所做工作一個函數在運

5、行期調用另一個函數時，在運行被調用函數之前，系統先完成3件事：將所有的實參、返回地址等信息傳遞給被調用函數保存。為被調用函數的局部變量分配存儲區；將控制轉移到被調用函數的入口。從被調用函數返回調用函數前，系統也應完成3件事：保存被調用函數的結果；釋放被調用函數的數據區；依照被調用函數保存的返回地址將控制轉移到調用函數。當有多個函數構成嵌套調用時，按照“后調用先返回”的原則（LIFO），上述函數之間的信息傳遞和控制轉移必須通過“棧”來實現，即系統將整個程序運行時所需的數據空間安排在一個棧中，每當調用一個函數時，就為其在棧頂分配一個存儲區，每當從一個函數退出時，就釋放其存儲區，因此當前運行函數的數

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

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

8、   時間結果<=12個        <=1秒14個          2秒16個         13秒20個        204秒 時間復雜度程序所花時間正比于所輸出的信息行數目，而信息行的數目則等價于盤子的移動次數。考察程序，設盤子移動次數為mov

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

10、此所需要的空間總數為3n1。Hanoi塔問題的復雜性是以n為指數的函數，因此在可以接受的范圍內，只能解決n值比較小（n<=30）的hanoi問題。對于這個較小的n值，堆棧在空間需求上的差別相當小，可以隨意使用。7、結論通過對上述遞歸在Hanoi塔問題上的應用分析，我們可以得出如下結論：1、遞歸調用過程中，在程序執行之前無法知道控制這種調用棧的規模，因為這一規模取決于遞歸調用的次序。在這種情況下，程序的地址空間可能動態變化；2、遞歸應用于程序設計時，結構清晰、程序易讀，編制和調試程序很方便，不需要用戶自行管理遞歸工作棧。但遞歸應用于計算機時需要占用大量系統資源（包括堆棧、軟中斷和存貯空間等），并消耗大量處理時間。因此，可以考慮采用