【精品】漢諾塔論文

《【精品】漢諾塔論文》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、目錄1摘要2一、背景知識3二、問題重述3三、算法分析3四、流程及程序設(shè)計5⑴、流程圖5(2)、模塊及其功能介紹6五、調(diào)試與算法復(fù)雜度分析7(1)、運行結(jié)果7(2)、Hanoi塔問題復(fù)雜度分析9總結(jié)10參考文獻11附錄12漢諾威塔是一款集娛樂與運算的智力游戲，它不僅能使人在休閑的時候放松心情，而月?還能在玩的過程屮不斷的提高你的思維能力。有三個柱子A,B,C。A柱子上疊放有n個盤子，每個盤子都比它下面的盤子要小一點，可以從上到下用1,2,...,n編號。要求借助柱子C,把柱子A上的所有的盤子移動到柱子B上。移動條件為：1、一次只能移一個盤

2、子2、移動過程中大盤子不能放在小盤子上，只能小盤子放在大盤子上本文的主要算法是利用函數(shù)的遞歸調(diào)用算法。首先，想辦法將A座上的前n-1個盤借助C座移動到B座上，然后將A組上的第n個盤移動到C座上。然后再將B座上的n-1個盤借助A座移動到C座上，此次移動也和第一次移動一樣，重復(fù)遞歸，直到最后一個盤為止。關(guān)鍵詞：漢諾塔遞歸思想函數(shù)調(diào)用數(shù)組指針一、背景知識漢諾塔（又稱河內(nèi)塔）問題來自中東地區(qū)一個古老的傳說：在世界剛被創(chuàng)建的時候有一座鉆石寶塔（塔A）,其上有64個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個鉆石寶塔（塔B

3、和塔C）。從世界創(chuàng)始之口起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動到塔C上去，其間借助于塔B的幫助。每次只能移動一個碟子，任何時候都不能把一個碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時，世界末日也就到了。19世紀(jì)的法國大數(shù)學(xué)家魯卡曾經(jīng)研究過這個問題，他正確地指出，要完成這個任務(wù)，僧侶們搬動金盤的總次數(shù)（把1個金盤從某個塔柱轉(zhuǎn)移到另1個塔柱叫做1次）為:18,446,744,073,709,551,615次。假設(shè)僧侶們個個身強力壯，每天24小時不知疲倦地不停工作，而且動作敏捷快速，1秒鐘就能移動1個金盤，那么，完成這個任務(wù)也得花5

4、800億年！二、問題重述有三個柱子A,B,CoA柱子上疊放有n個盤子，每個盤子都比它下面的盤子要小一點，可以從上到下用l,2,...,n編號。要求借助柱子C,把柱子A上的所有的盤子移動到柱子B上。移動條件為：1、一次只能移一個盤子；2、移動過程中大盤了不能放在小盤了上，只能小盤了放在大盤了上。用計算機算法思想解決該問題，利用C++實現(xiàn)其動態(tài)演示。三、算法分析設(shè)A上有n個盤子。當(dāng)n=l時，則將圓盤從A直接移動到C。當(dāng)n大于等于2時，移動的過程可分解為三個步驟：第一步把A上的n-i個圓盤移到B上；第二步把A上的一個圓盤移到C上；第三步把B上

5、的n?i個圓盤移到C±；其屮第一步和第三步是類同的。為了更清楚地描述算法，用圖示法描述如下：將N個盤子從A桿上借助C桿移動到B桿上。這樣移動N個盤子的丁作就可以按照以下過程進行：①第一次調(diào)用遞歸n12…NLJ1N-1BC①將一個盤子從A移動到B上;②第二次調(diào)用遞歸r—2I

6、….N-1N「11BC重復(fù)以上過程，直到將全部的盤子移動到位時為止。由遞歸算法我們可以得到遞推關(guān)系：rM(n)=2M(n-l)+l當(dāng)n>l時[M(n)=l當(dāng)n=l時四、流程及程序設(shè)計⑴、流程圖有上述流程圖得岀實現(xiàn)遞歸函數(shù)過程的流程圖設(shè)計如下圖所示:(2)、模塊及其功能

7、介紹首先定義兩個類：Tower類(棧)Hanoi類(包含三個Tower類對象組成)，程序中大部份功能函數(shù)封裝在這兩個類中(包括：遞歸算法Hanoi::Move()>圖形顯示函數(shù)Hanoi::0utlin()>移動演示函數(shù)Hanoi::MoveShow()等)塔的盤子是字符串由(’二’)組成的另外述有一些函數(shù)：Push函數(shù)的功能是放入盤子，pop函數(shù)的功能是取出盤子重要函數(shù)的分析：voidMove(intn,intA,intB,intC)遞歸(這里的A,B,C是相對的,不等同外面定義的A塔，B塔，C塔){if(n==l)//遞歸的終止條件

8、{move(A,C);〃將A塔上的最后一個盤子盤子直接移動到C塔}else{Move(n-1,A,C,B);//將A塔上的n-1個盤子通過C塔移動到B塔move(A,C);//將A塔上的最后一個盤子盤子直接移動到C塔Move(n-1,B,A,C);//將B塔上的n-1個盤子通過A塔移動到C塔}五.調(diào)試與算法復(fù)雜度分析⑴、運行結(jié)果（以4層Hanoi塔為類）運行程序得到如下界面：程序主界面汁?建立漢諾塔2.算法思想3.結(jié)東

9、程序請嗚只忘禹扭和<1，2,3>,1請輸入層數(shù)<1-10>:4(](][](][](][][][](](][][](](](][](]游戲的初始狀態(tài)當(dāng)完成第一步時，A上第-?個盤就移動到B上這時按任意鍵繼續(xù)