漢諾塔問題實驗報告

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

2、碟子借助塔C先移到塔B上。(2) 把塔A上剩下的一個碟子移到塔C上。(3) 將n-1個碟子從塔B借助于塔A移到塔C ±o4. 實驗步驟：1. 用c卄或c語言設計實現(xiàn)漢諾塔游戲；2. 讓盤子數(shù)從2開始到7進行實驗，記錄程序運行時間和遞 歸調用次數(shù)；3. 畫出盤子數(shù)n和運行時間t、遞歸調用次數(shù)m的關系圖, 并進行分析。5. 代碼設計： 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>結果如下:movincfHII2 dishes:從搬到bO t Jup eu p ninput the numbei' of diskes ：3The step to mouing 3 diskes "!扁-b攥到人C->搬到h 畑-兀搬到 叢b->搬至aAb->c搬到 從應-> 搬到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遞歸應用中的Hanoi塔問題分析1) Hanoi塔問題中函數(shù)調用時系統(tǒng)所做工作一個函數(shù)在運行期調用另一個函數(shù)時，在運行被調用函數(shù)之前，系 統(tǒng)先完成3件事： 將所有的實參、返回地址等信息傳遞給被調用函數(shù)保存。 為被調用函數(shù)的局部變量分配存儲區(qū)； 將控制轉移到被調用

6、函數(shù)的入口。從被調用函數(shù)返回調用函數(shù)前，系統(tǒng)也應完成3件事： 保存被調用函數(shù)的結果； 釋放被調用函數(shù)的數(shù)據(jù)區(qū)； 依照被調用函數(shù)保存的返回地址將控制轉移到調用函數(shù)。當有多個函數(shù)構成嵌套調用時，按照“后調用先返回”的原則(LIFO),上述函數(shù)之間的信息傳遞和控制轉移必須通過“?！眮?實現(xiàn)，即系統(tǒng)將整個程序運行時所需的數(shù)據(jù)空間安排在一個棧中， 每當調用一個函數(shù)時，就為其在棧頂分配一個存儲區(qū)，每當從一個 函數(shù)退出時，就釋放其存儲區(qū)，因此當前運行函數(shù)的數(shù)據(jù)區(qū)必在棧 頂。堆棧特點：LIFO,除非轉移或中斷，堆棧內(nèi)容的存或取表現(xiàn)出 線性表列的性質。正是如此，程序不要求跟蹤當前進入堆棧的真實 單元，而只要用一

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

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

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