漢諾威塔-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</b></p><p>　　題 目： 漢諾威塔 </p><p>　　班 級： </p><p>　　姓 名： 學(xué) 號： </p><p>

2、　　同組人姓名： </p><p>　　起 迄 日 期: 　　　　 　　　　　　　　　 </p><p>　　課程設(shè)計地點: 　　　　　　　　　　　　　　 </p><p>　　指導(dǎo)教師： </p><p><b>　　目 </b&g

3、t;</p><p><b>　　錄</b></p><p><b>　　目錄</b></p><p><b>　　一、 前言 </b></p><p>　　二、 系統(tǒng)功能分析 </p><p>　　2.1 漢諾威塔問題

4、 </p><p>　　2.2 解析漢諾威塔問題 </p><p><b>　　三、 總體設(shè)計</b></p><p><b>　　四、 詳細(xì)設(shè)計</b></p><p><b>　　五、 系統(tǒng)實現(xiàn)</b></p><p><b&g

5、t;　　六、 結(jié)論</b></p><p><b>　　結(jié)束語</b></p><p><b>　　參考文獻(xiàn)</b></p><p><b>　　附錄</b></p><p><b>　　前言</b></p><p>　

6、　漢諾威塔是一款集娛樂與運(yùn)算的智力游戲，它不僅能使人在休閑的時候放松心情，而且還能在玩的過程中不斷的提高你的思維能力。</p><p>　　本設(shè)計著手于怎么運(yùn)算出n層漢諾威塔的解決方案，然而經(jīng)過不斷的調(diào)試以及自己的在做的過程中也不斷的去嘗試著怎么自己能過漢諾威塔多少層，經(jīng)過幾個星期的努力，以及不斷的調(diào)試，我發(fā)現(xiàn)我能把7層的漢諾威塔玩過已經(jīng)是很不錯了。如想玩下去的，只要你能記得那些步驟，那么這漢諾威塔也不是什么難的

7、了。</p><p>　　本設(shè)計如有差錯，望各位諒解，在此我誠懇的希望大家能提出意見，以便我能及時修改。</p><p>　　漢諾塔（又稱河內(nèi)塔）問題是印度的一個古老的傳說。開天辟地的神勃拉瑪在一個廟里留下了三根金剛石的棒，第一根上面套著64個圓的金片，最大的一個在底下，其余一個比一個小，依次疊上去，廟里的眾僧不倦地把它們一個個地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每

8、次只能搬一個，而且大的不能放在小的上面。解答結(jié)果請自己運(yùn)行計算，程序見尾部。面對龐大的數(shù)字(移動圓片的次數(shù))18446744073709551615，看來，眾僧們耗盡畢生精力也不可能完成金片的移動。</p><p>　　后來，這個傳說就演變?yōu)闈h諾塔游戲。</p><p><b>　　系統(tǒng)功能分析 </b></p><p>　　科技獎勵工作是推動

9、科學(xué)技術(shù)進(jìn)步的一項重要的激勵機(jī)制，對促進(jìn)國家和地方社會經(jīng)濟(jì)發(fā)展，調(diào)動廣大科研工作者的積極性具有重大作用。實踐證明，網(wǎng)絡(luò)技術(shù)的運(yùn)用有利于更快地促進(jìn)科技成果的利用，從而有利于發(fā)展科技生產(chǎn)力，繁榮國家和地方社會經(jīng)濟(jì)生活。</p><p>　　本設(shè)計可以實現(xiàn)從2到n層的漢諾威塔以供玩家思考和了解其運(yùn)行過程。本設(shè)計通過一系列的實踐證明了前九層漢諾威塔的準(zhǔn)確性，根據(jù)本人推論，以后的每一層的準(zhǔn)度應(yīng)該與事實相符，鑒于工作量實在太

10、大，故而敬請各為原諒！</p><p><b>　　2.1漢諾威塔問題</b></p><p><b>　　n階漢諾威塔問題：</b></p><p>　　有三根桿子A,B,C。A桿上有n個碟子 </p><p>　　每次移動一塊碟子,小的只能疊在大的上面 </p><p&g

11、t;　　把所有碟子從A桿全部移到C桿上</p><p>　　經(jīng)過研究發(fā)現(xiàn)，漢諾塔的破解很簡單，就是按照移動規(guī)則向一個方向移動金片：</p><p>　　如3階漢諾塔的移動：A→C,A→B,C→B,A→C,B→A,B→C,A→C</p><p>　　2.2解析漢諾威塔問題</p><p>　　下面用歸納法證明n階漢諾威塔問題，可以用n層二叉樹描

12、述，而且它的解就是該二叉樹的中序遍歷序列。</p><p>　　用一個四元組(n,A,B,C)表示把n個盤子從A搬到C,中間可以借助B的n階漢諾威塔問題。其中A、B、C的地位是相對的，第一個表示起始位置，最后一個表示終止位置，中間表示過渡位置。例如(n,A,B,C)表示把n個盤子從B搬到C，中間可以借助A的n階漢諾威塔問題。用一個三元組((n),A,B)表示把第n個盤子從A直接搬到B。</p>&l

13、t;p>　　假設(shè)有兩個盤子，要把兩個盤子從A搬到C，即(2,A,B,C),就必須先把第1個盤子從A搬到B，即((1),A,B),再把第2個盤子從A直接搬到C，即((2),A,C),最后把第1個盤子從B直接搬到C，即((1),B,C),序列((1),A,B),((2),A,C),((1),B,C)正好是以(2,A,B,C)為根，以(1,A,C,B)和(1,B,A,C)為左右孩子的二叉樹的中序遍歷序列(訪問結(jié)點時，去掉過渡位置，盤子數(shù)

14、加括號)(見圖1)，其中雙親結(jié)點與左孩子的關(guān)系是，盤子個數(shù)減1，過渡位置和終止位置交換，與右孩子的關(guān)系是，盤子個數(shù)減1，起始位置和過渡位置交換。</p><p>　　假如有n個盤子時，結(jié)論成立。現(xiàn)在假設(shè)有n+1個盤子。要把n+1個盤子從A搬到C，即(n+1,A,B,C)，必須先把前n個盤子從A搬到C，即((n+1),A,C)，最后把前n個盤子從B搬到C，即(n,A,B,C)。序列(n,A,C,B),((n+1),

15、A,C),(n,B,A,C)正好是以(n+1,A,B,C)為根，以(n,A,C,B)和(n,B,A,C)為左右孩子的二叉樹的中序遍歷順序(中序遍歷左子樹，訪問根結(jié)點，中序遍歷右子樹)(見圖2)。而左右子樹都是n階漢諾威塔問題，結(jié)論也成立。到此證明完畢。</p><p>　　如下所示：圖（a）漢諾威塔問題狀態(tài)圖 </p><p>　　圖（b）n階和3階漢諾威塔問題狀態(tài)圖</p>

16、<p><b>　　三、 總體設(shè)計</b></p><p><b>　　首先建立一個程序。</b></p><p>　　然后創(chuàng)建類Hanoi，將公有繼承和私有繼承分好類。</p><p><b>　　其次建立各類函數(shù)：</b></p><p>　　void Han

17、oi::move(int numDisk,string init,string desti,string templ)</p><p>　　void Hanoi::moveOne(int numDisk,string init,string desti)</p><p>　　void Hanoi::Solve ()</p><p>　　最后構(gòu)建主函數(shù)，應(yīng)用各種函數(shù)，

18、使整個程序能運(yùn)行。</p><p>　　解決圖3.1從而達(dá)到圖3.2所示畫面即我們這個程序所要完成的功能。</p><p>　　圖3.1 漢諾威塔游戲開始界面</p><p>　　圖3.2 漢諾威塔游戲結(jié)束界面</p><p><b>　　四、 詳細(xì)設(shè)計</b></p><p><b>

19、;　　漢諾威塔程序代碼：</b></p><p>　　#include "iostream"</p><p>　　#include "string"</p><p>　　using namespace std;</p><p>　　class Hanoi //定義類Hanoi<

20、/p><p><b>　　{</b></p><p>　　public : //共有成員</p><p>　　hanoi(int disks)</p><p><b>　　{</b></p><p>　　totalDisks=disks;</p>

21、<p><b>　　}</b></p><p>　　void Solve();</p><p>　　private : //私有成員</p><p>　　int totalDisks;</p><p>　　void move(int numDisk,string init,string desti

22、,string templ) ;//移動函明</p><p>　　void moveOne(int numDisk ,string init,string desti) ; </p><p>　　}; </p><

23、;p>　　void hanoi::move(int numDisk,string init,string desti,string templ) //定義移動函數(shù) </p><p><b>　　{</b></p><p>　　if(numDisk==1) moveOne(numDisk,init,desti);</p><p><

24、;b>　　else</b></p><p><b>　　{</b></p><p>　　move(numDisk-1,init,templ,desti);</p><p>　　moveOne(numDisk,init,desti);</p><p>　　move(numDisk-1,templ,dest

25、i,init);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void hanoi::moveOne(int numDisk,string init,string desti)</p><p><b>　　{</b><

26、;/p><p>　　cout<<"移動塔層 "<<numDisk<<" from "<<init <<" to "<<desti<<endl;</p><p><b>　　}</b></p><p>　　

27、void hanoi::Solve ()</p><p><b>　　{</b></p><p>　　string init="A",desti="C",templ="B";</p><p>　　move(totalDisks,init,desti,templ);</p>

28、<p><b>　　}</b></p><p>　　int main(int argc, char* argv[]) //主函數(shù)</p><p><b>　　{ </b></p><p><b>　　int a;</b></p><p>　　loop:co

29、ut<<"請輸入你想要輸入的漢諾威塔的層數(shù)："<<endl;</p><p><b>　　cin>>a;</b></p><p>　　cout<<"塔層數(shù)從上至下編號為1、2、3、4、5、6,……"<<endl;</p><p>　　hanoi

30、hanoi(a);</p><p>　　hanoi.Solve();</p><p>　　goto loop;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　五、 系統(tǒng)實現(xiàn)</b&g

31、t;</p><p><b>　　程序運(yùn)行如下：</b></p><p>　　圖5.1 程序運(yùn)行界面</p><p>　　圖5.2 4層漢諾威塔運(yùn)行界面</p><p><b>　　六、結(jié)論</b></p><p>　　通過這次課程設(shè)計，讓我對數(shù)據(jù)結(jié)構(gòu)有了新一層的了

32、解，讓我明白各種函數(shù)以及類的應(yīng)用，明白了算法對程序的重要性。由于本次程序是解決一個游戲的過關(guān)問題，所以必須親自玩那個游戲，從而推出程序的重要性。這玩游戲的過程讓我感覺到漢諾威塔的趣味性，這是一個集智益與娛樂于一體的游戲，很值得一玩。</p><p>　　本程序運(yùn)行13層以下速度很快，13層以上則要等一段時間了。</p><p><b>　　圖7.1</b></p

33、><p><b>　　結(jié) 束 語</b></p><p>　　本次課程設(shè)計，使我對從漢諾威塔設(shè)計方案到設(shè)計的基本過程的設(shè)計方法、步驟、思路、有一定的了解與認(rèn)識。在課程設(shè)計過程中，我基本能按照規(guī)定的程序進(jìn)行，先針對漢諾威塔設(shè)計收集、調(diào)查有關(guān)資料，其間，與同學(xué)之間對遞歸的算法討論、修改，再討論、再修改，最后定案。最終用c++語言實現(xiàn)了可視化的漢諾威塔算法。</p>

34、<p>　　程序設(shè)計達(dá)到了專業(yè)學(xué)習(xí)的預(yù)期目的。課程設(shè)計之后，我普遍感到不僅實際動手能力有所提高，更重要的是進(jìn)一步激發(fā)了我對專業(yè)知識的興趣，并能夠結(jié)合實際存在的問題在專業(yè)領(lǐng)域內(nèi)進(jìn)行更深入的學(xué)習(xí)。 </p><p>　　對我們計算機(jī)專業(yè)的本科生來說，實際能力的培養(yǎng)至關(guān)重要，而這種實際能力的培養(yǎng)單靠課堂教學(xué)是遠(yuǎn)遠(yuǎn)不夠的，必須從課堂走

35、向?qū)嵺`。通過課程設(shè)計，讓我找出自身狀況與實際需要的差距，并在以后的學(xué)習(xí)期間及時補(bǔ)充相關(guān)知識，為求職與正式工作做好充分的知識、能力準(zhǔn)備，從而縮短從校園走向社會的心理轉(zhuǎn)型。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]數(shù)據(jù)結(jié)構(gòu)（C語言版）作者：嚴(yán)蔚敏 吳偉民 出版社：清華大學(xué)出版社 時間：2006/10</p><p>