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

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) o從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A 上的碟子移動(dòng)到塔C上去，其間借助于塔B的幫助。每次只能移 動(dòng)一個(gè)碟子，任何時(shí)候都不能把一個(gè)碟子放在比它小的碟子上面。 當(dāng)牧師們完成任務(wù)時(shí)，世界末日也就到了。3. 算法設(shè)計(jì)思想：對(duì)于漢諾塔問題的求解，可以通過以下三個(gè)步驟實(shí)現(xiàn)：(1) 將塔A上的ml個(gè)

2、碟子借助塔C先移到塔B上。(2) 把塔A上剩下的一個(gè)碟子移到塔C上。(3) 將n-1個(gè)碟子從塔B借助于塔A移到塔C ±o4. 實(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 ttinclude "stdafx. h" include <stdlib. h> include <stdio. h>include <iostream>void hanoi(i

3、nt n, char x,char y, char z)if(n=l)printf ("從搬到%cn*, x, z);elsehanoi(nl,x,z,y);printf (*從%c>%c搬到n", x, z);hanoi (n_l, y, x, z);void main()int m ;printf("input the number of diskes：");scanf&m);printf(*The step to moving %3d diskes:",m); hanoi (m. ' a' .' b&

4、#39;,' c');)自定義頭文件:pragma once#include "targetver h"井include <stdio. h>#include <tchar h>結(jié)果如下:movincfHII2 dishes:從搬到bO t Jup eu p ninput the numbei' of diskes ：3The step to mouing 3 diskes "!扁-b攥到人C->搬到h 畑-兀搬到 叢b->搬至aAb->c搬到 從應(yīng)-> 搬到Cinput the number

5、 of diskes:4The step to moving 4 disk&s二從搬到b 從a-c搬到搬到 從a-b搬釗 從c->b搬劉 從&->搬到b 從a->G搬到 從h->攢王ijc 從bf搬到 從c->搬到 從h->(:搬到 如->搬到b 如亠搬到 如-> 槻予k6遞歸應(yīng)用中的Hanoi塔問題分析1) Hanoi塔問題中函數(shù)調(diào)用時(shí)系統(tǒng)所做工作一個(gè)函數(shù)在運(yùn)行期調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行被調(diào)用函數(shù)之前，系 統(tǒng)先完成3件事： 將所有的實(shí)參、返回地址等信息傳遞給被調(diào)用函數(shù)保存。 為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)； 將控制轉(zhuǎn)移到被調(diào)用

6、函數(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è)存儲(chǔ)區(qū)，每當(dāng)從一個(gè) 函數(shù)退出時(shí)，就釋放其存儲(chǔ)區(qū)，因此當(dāng)前運(yùn)行函數(shù)的數(shù)據(jù)區(qū)必在棧 頂。堆棧特點(diǎn)：LIFO,除非轉(zhuǎn)移或中斷，堆棧內(nèi)容的存或取表現(xiàn)出 線性表列的性質(zhì)。正是如此，程序不要求跟蹤當(dāng)前進(jìn)入堆棧的真實(shí) 單元，而只要用一

7、個(gè)具有自動(dòng)遞增或自動(dòng)遞減功能的堆棧計(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)入下一層，即i + 1層。反之，退出第i層遞歸應(yīng) 返回至上一層，即i 1層。為了保證遞歸函數(shù)正確執(zhí)行，系統(tǒng)需 設(shè)立一個(gè)“遞歸工作?！保鳛檎麄€(gè)遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù) 存儲(chǔ)區(qū)。每一層遞歸所需信息構(gòu)成一個(gè)“工作記錄”，其中包括所 有實(shí)參、所有局部變量以及上一

8、層的返回地址。每進(jìn)入一層遞歸， 就產(chǎn)生一個(gè)新的工作記錄壓入棧頂。每退出一層遞歸，就從棧頂彈 出一個(gè)工作記錄，則當(dāng)前執(zhí)行層的工作記錄必是遞歸工作棧棧頂?shù)?工作記錄，稱這個(gè)記錄為“活動(dòng)記錄”，并稱指示活動(dòng)記錄的棧頂 指針為“當(dāng)前環(huán)境指針”。2） Hanoi塔問題遞歸程序的復(fù)雜度分析運(yùn)行hanoi程序的時(shí)間程序hanoi. c在硬件環(huán)境為賽揚(yáng)400MHz、內(nèi)存128M的汁算平臺(tái) （不同機(jī)器運(yùn)行時(shí)間有一定差別）運(yùn)行，可得出如下時(shí)間結(jié)果：盤子數(shù)時(shí)間結(jié)果<=12 個(gè)<=1秒14個(gè)2秒16個(gè)13秒20個(gè)204秒時(shí)間復(fù)雜度程序所花時(shí)間正比于所輸出的信息行數(shù)LI,而信息行的數(shù)目則等價(jià) 于盤子的移動(dòng)次

9、數(shù)?？疾斐绦?，設(shè)盤子移動(dòng)次數(shù)為moves (n),貝歸moves(n)二用迭代方法計(jì)算公式，得到結(jié)果moves (n)-2n-lo因 此，hanoi函數(shù)的時(shí)間復(fù)雜度為0(2 n)?？臻g復(fù)雜度從每個(gè)塔上移走盤子吋是按照LIFO進(jìn)行，因此可以 把每個(gè)塔表示成一個(gè)堆棧。3座塔在任何時(shí)候總共擁有的盤子都是 n個(gè)。如果使用鏈表形式的堆棧，只需申請(qǐng)n個(gè)元素所需要的空間 如果使用的是基于公式化描述的堆棧，塔1和塔2的容量都必須是 n,而塔3的容量是n1,因此所需要的空間總數(shù)為3n-loHanoi塔問題的復(fù)雜性是以n為指數(shù)的函數(shù)，因此在可以接受的范 圍內(nèi)，只能解決n值比較小(n<=30)的hanoi問題。對(duì)于這個(gè)較 小的n值，堆棧在空間需求上的差別相當(dāng)小，可以隨意使用。7、結(jié)論通過對(duì)上述遞歸在Hanoi塔問題上的應(yīng)用分析，我們可以得出如下 結(jié)論：1、遞歸調(diào)用過程中，在程序執(zhí)行之前無法知道控制這種調(diào)用棧的 規(guī)模，因?yàn)檫@一規(guī)模取決于遞歸調(diào)用的次序。在這種情況下，程序 的地址空間可能動(dòng)態(tài)變化；2、遞歸應(yīng)用于程序設(shè)計(jì)時(shí)，結(jié)構(gòu)清晰、程序易讀，編制和調(diào)試程 序很方便，不需要用戶自行管理遞歸工作棧。但遞歸應(yīng)用于計(jì)算機(jī) 時(shí)需要占用大量系統(tǒng)資源(包括堆棧、軟中斷和存貯空間等)，并 消耗大量處理時(shí)間。因此，可以考