漢諾威塔-數(shù)據(jù)結構課程設計

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

2、　　同組人姓名： </p><p>　　起 迄 日 期: 　　　　 　　　　　　　　　 </p><p>　　課程設計地點: 　　　　　　　　　　　　　　 </p><p>　　指導教師： </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>　　三、 總體設計</b></p><p><b>　　四、 詳細設計</b></p><p><b>　　五、 系統(tǒng)實現(xiàn)</b></p><p><b&g

5、t;　　六、 結論</b></p><p><b>　　結束語</b></p><p><b>　　參考文獻</b></p><p><b>　　附錄</b></p><p><b>　　前言</b></p><p>　

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

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

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

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

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>　　經過研究發(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>　　假設有兩個盤子，要把兩個盤子從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)為左右孩子的二叉樹的中序遍歷序列(訪問結點時，去掉過渡位置，盤子數(shù)

14、加括號)(見圖1)，其中雙親結點與左孩子的關系是，盤子個數(shù)減1，過渡位置和終止位置交換，與右孩子的關系是，盤子個數(shù)減1，起始位置和過渡位置交換。</p><p>　　假如有n個盤子時，結論成立?，F(xiàn)在假設有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)為左右孩子的二叉樹的中序遍歷順序(中序遍歷左子樹，訪問根結點，中序遍歷右子樹)(見圖2)。而左右子樹都是n階漢諾威塔問題，結論也成立。到此證明完畢。</p><p>　　如下所示：圖（a）漢諾威塔問題狀態(tài)圖 </p><p>　　圖（b）n階和3階漢諾威塔問題狀態(tài)圖</p>

16、<p><b>　　三、 總體設計</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>　　最后構建主函數(shù)，應用各種函數(shù)，

18、使整個程序能運行。</p><p>　　解決圖3.1從而達到圖3.2所示畫面即我們這個程序所要完成的功能。</p><p>　　圖3.1 漢諾威塔游戲開始界面</p><p>　　圖3.2 漢諾威塔游戲結束界面</p><p><b>　　四、 詳細設計</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>　　程序運行如下：</b></p><p>　　圖5.1 程序運行界面</p><p>　　圖5.2 4層漢諾威塔運行界面</p><p><b>　　六、結論</b></p><p>　　通過這次課程設計，讓我對數(shù)據(jù)結構有了新一層的了

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

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

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

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