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

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

2、　　同組人姓名： </p><p>　　起 迄 日 期: 　　　　 　　　　　　　　　 </p><p>　　課程設(shè)計(jì)地點(diǎn): 　　　　　　　　　　　　　　 </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 漢諾威塔問(wèn)題

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

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

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

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

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

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

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

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

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

13、t;p>　　假設(shè)有兩個(gè)盤(pán)子，要把兩個(gè)盤(pán)子從A搬到C，即(2,A,B,C),就必須先把第1個(gè)盤(pán)子從A搬到B，即((1),A,B),再把第2個(gè)盤(pán)子從A直接搬到C，即((2),A,C),最后把第1個(gè)盤(pán)子從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)為左右孩子的二叉樹(shù)的中序遍歷序列(訪問(wèn)結(jié)點(diǎn)時(shí)，去掉過(guò)渡位置，盤(pán)子數(shù)

14、加括號(hào))(見(jiàn)圖1)，其中雙親結(jié)點(diǎn)與左孩子的關(guān)系是，盤(pán)子個(gè)數(shù)減1，過(guò)渡位置和終止位置交換，與右孩子的關(guān)系是，盤(pán)子個(gè)數(shù)減1，起始位置和過(guò)渡位置交換。</p><p>　　假如有n個(gè)盤(pán)子時(shí)，結(jié)論成立。現(xiàn)在假設(shè)有n+1個(gè)盤(pán)子。要把n+1個(gè)盤(pán)子從A搬到C，即(n+1,A,B,C)，必須先把前n個(gè)盤(pán)子從A搬到C，即((n+1),A,C)，最后把前n個(gè)盤(pá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)為左右孩子的二叉樹(shù)的中序遍歷順序(中序遍歷左子樹(shù)，訪問(wèn)根結(jié)點(diǎn)，中序遍歷右子樹(shù))(見(jiàn)圖2)。而左右子樹(shù)都是n階漢諾威塔問(wèn)題，結(jié)論也成立。到此證明完畢。</p><p>　　如下所示：圖（a）漢諾威塔問(wèn)題狀態(tài)圖 </p><p>　　圖（b）n階和3階漢諾威塔問(wèn)題狀態(tài)圖</p>

16、<p><b>　　三、 總體設(shè)計(jì)</b></p><p><b>　　首先建立一個(gè)程序。</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、使整個(gè)程序能運(yùn)行。</p><p>　　解決圖3.1從而達(dá)到圖3.2所示畫(huà)面即我們這個(gè)程序所要完成的功能。</p><p>　　圖3.1 漢諾威塔游戲開(kāi)始界面</p><p>　　圖3.2 漢諾威塔游戲結(jié)束界面</p><p><b>　　四、 詳細(xì)設(shè)計(jì)</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) ;//移動(dòng)函明</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) //定義移動(dòng)函數(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<<"移動(dòng)塔層 "<<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<<"請(qǐng)輸入你想要輸入的漢諾威塔的層數(shù)："<<endl;</p><p><b>　　cin>>a;</b></p><p>　　cout<<"塔層數(shù)從上至下編號(hào)為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)實(shí)現(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>　　通過(guò)這次課程設(shè)計(jì)，讓我對(duì)數(shù)據(jù)結(jié)構(gòu)有了新一層的了

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

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

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

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