漢諾塔問題實(shí)驗(yàn)報(bào)告(共6頁)

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

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

3、nclude <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 of diskes:&q

4、uot;); 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)用時(shí)系統(tǒng)所做工作一個(gè)函數(shù)在運(yùn)行期調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)

5、行被調(diào)用函數(shù)之前，系統(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)用函數(shù)的結(jié)果；釋放被調(diào)用函數(shù)的數(shù)據(jù)區(qū)；依照被調(diào)用函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。當(dāng)有多個(gè)函數(shù)構(gòu)成嵌套調(diào)用時(shí)，按照“后調(diào)用先返回”的原則（LIFO），上述函數(shù)之間的信息傳遞和控制轉(zhuǎn)移必須通過“棧”來實(shí)現(xiàn)，即系統(tǒng)將整個(gè)程序運(yùn)行時(shí)所需的數(shù)據(jù)空間安排在一個(gè)棧中，每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，就為其在棧頂分配一個(gè)存儲區(qū)，每當(dāng)從一個(gè)函數(shù)退出時(shí)，就釋放其存儲區(qū)，因此當(dāng)前運(yùn)行函數(shù)的數(shù)據(jù)區(qū)必在棧頂。堆棧特點(diǎn)：L

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

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

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

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

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