漢諾塔程序?qū)嶒瀳蟾?/h1>

《漢諾塔程序?qū)嶒瀳蟾妗酚蓵T上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、實驗題目：Hanoi塔問題一、問題描述：假設(shè)有三個分別命名為A,B和C的塔座，在塔座B上插有n個直徑大小各不相同、從小到大編號為1,2,…，n的圓盤。現(xiàn)要求將塔座B上的n個圓盤移至塔座A上并仍按同樣順序疊排，圓盤移動時必須遵守以下規(guī)則：(1)每次只能移動一個圓盤；(2)圓盤可以插在A,B和C中任一塔上；(3)任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上。要求：用程序模擬上述問題解決辦法，并輸出移動的總次數(shù)，圓盤的個數(shù)從鍵盤輸入；并想辦法計算出程序運行的時間。二、算法思路：1、建立數(shù)學模型：這個問題可用遞歸法解決，并用數(shù)學歸納法又個別

2、得出普遍解法：假設(shè)塔座B上有3個圓盤移動到塔座A±：(1)〃將塔座B上2個圓盤借助塔座A移動到塔座C上；(2)〃將塔座B上1個圓盤移動到塔座A上；(3)〃將塔座C上2個圓盤借助塔座B移動到塔座A上。其屮笫2步可以直接實現(xiàn)。笫1步又可用遞歸方法分解為：1.1〃將塔座B上1個圓盤從塔座X移動到塔座A；1.2〃將塔座B上1個圓盤從塔座X移動到塔座C；1.3〃將塔座A上1個圓盤從塔座Z移動到塔座Co第3步可以分解為：3.1將塔座C上1個圓盤從塔座Y移動到塔座B；3.2將塔座C上1個圓盤從塔座Y移動到塔座A；3.3將塔座B上1個圓盤從塔座X移動到

3、塔座Ao綜上所述：可得到移動3個圓盤的步驟為B->A,B->C,A->C,B->A,C->B,C->A,B->A,2、算法設(shè)計：將n個圓盤rflB依次移到A,C作為輔助塔座。當n二1時，可以直接完成。否則，將塔座B頂上的n-1個圓盤借助塔座A移動到塔座C上；然后將圓盤B上第n個圓盤移到塔座A上；最后將塔座C上的n-l個圓盤移到塔座A上，并用塔座B作為輔助塔座。三、原程序#include#include#includeinttimes=0;voidmove(chara,cha

4、rb){printf("%c---->%c",a,b);}voidhno(intn,chara,charb,charc)if(n==l)move(a,c);times++;}else{hno(n-l,a,c,b);move(a,c);times++;hno(n-l’bac);}}voidmain(){unsignedstart,finish;intN;printf("請輸入漢諾塔的層數(shù):");scanf(H%d",&N);start=GetTickCount();//hnoJN/BVC'/A*)；finish=GetTickCoun

5、t();floattime=(finish-start)/1000.0;printf("共移動了%d次！",times);coutvv”總共需要時間為:"?time?endl;}四：4cAAcBcAbbaBBcBBBccAc若又-冃吉->->事鷲舉腐霜務(wù)0-016^ressitnykeytocont;inue五.結(jié)論分析通過對上述遞歸在Hanoi塔問題上的應(yīng)用分析，可以得出如下結(jié)論：遞歸應(yīng)用中的Hanoi塔問題分析遞歸應(yīng)用中的1、Hanoi塔問題中函數(shù)調(diào)用時系統(tǒng)所做工作一個函數(shù)在運行期調(diào)用另一個函數(shù)時，在運行被調(diào)用函數(shù)之前，系統(tǒng)先完

6、成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ù)。當有多個函數(shù)構(gòu)成嵌套調(diào)用吋，按照“后調(diào)用先返回”的原則，上述函數(shù)之間的信息傳遞和控制轉(zhuǎn)移必須通過“?！眮韺崿F(xiàn)，即系統(tǒng)將整個程序運行時所需的數(shù)據(jù)空間安排在一個棧中，每當調(diào)用一個幣數(shù)時，就為其在棧頂分配一個存儲區(qū)，每當從一個函數(shù)退出時，就釋放其存儲區(qū)，因此當前運行函

7、數(shù)的數(shù)據(jù)區(qū)必在棧頂。2、遞歸調(diào)用過程中，在程序執(zhí)行之前無法知道控制這種調(diào)用棧的規(guī)模，因為這一規(guī)模取決于遞歸調(diào)用的次序。在這種情況下，程序的地址空間可能動態(tài)變化；3、遞歸應(yīng)用于程序設(shè)計時，結(jié)構(gòu)清晰、程序易讀，編制和調(diào)試程序很方便，不需要用戶口行管理遞歸工作棧。但遞歸應(yīng)用于計算機時需要占用大量系統(tǒng)資源（包括堆棧、軟中斷和存貯空間等），并消耗大量處理時間。因此，可以考慮采用并行計算進行處理，但4、遞歸是串行的，其第n步運算依賴于第步運算，所以在計算機軟件理論上不存在遞歸問題并行計算的可能性。實際上是否存在并行遞歸計算有待進一步探討。