漢諾威塔課程設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題 目： 漢諾威塔 班 級(jí)： 姓 名： 學(xué) 號(hào)： 同組人姓名： 起 迄 日 期: 課程設(shè)計(jì)地點(diǎn): 指導(dǎo)教師： 評(píng)閱意見(jiàn)：成績(jī)?cè)u(píng)定：評(píng)閱人： 日期：目 錄目錄一、 前言 二、 系統(tǒng)功能分析 2.1 漢諾威塔問(wèn)題 2.2 解析漢諾威塔問(wèn)題 三、 總體設(shè)計(jì)四、 詳細(xì)設(shè)計(jì)五、 系統(tǒng)實(shí)現(xiàn)六、 結(jié)論結(jié)束語(yǔ)參考文獻(xiàn)附錄一、 前言漢諾威塔是一款集娛樂(lè)與運(yùn)算的智力游戲，它不僅能使人在休閑的時(shí)候放松心情，而且還能在玩的過(guò)程中不斷的提高你的思維能力。本設(shè)計(jì)著手于怎么運(yùn)算出n層漢諾威塔的解決方案，然而經(jīng)過(guò)不斷的調(diào)試以及自己的在做的過(guò)程中也不斷的去嘗試著怎么自己能過(guò)漢諾威塔多少層，經(jīng)過(guò)幾個(gè)星期的努力，以

2、及不斷的調(diào)試，我發(fā)現(xiàn)我能把7層的漢諾威塔玩過(guò)已經(jīng)是很不錯(cuò)了。如想玩下去的，只要你能記得那些步驟，那么這漢諾威塔也不是什么難的了。本設(shè)計(jì)如有差錯(cuò)，望各位諒解，在此我誠(chéng)懇的希望大家能提出意見(jiàn)，以便我能及時(shí)修改。后來(lái)，這個(gè)傳說(shuō)就演變?yōu)闈h諾塔游戲。二、 系統(tǒng)功能分析 科技獎(jiǎng)勵(lì)工作是推動(dòng)科學(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ì)生活。本設(shè)計(jì)可以實(shí)現(xiàn)從2到n層的漢諾威塔以供玩家思考和了解其運(yùn)行過(guò)程。本設(shè)計(jì)通過(guò)一系列的實(shí)踐證明了前九層漢諾威塔的

3、準(zhǔn)確性，根據(jù)本人推論，以后的每一層的準(zhǔn)度應(yīng)該與事實(shí)相符，鑒于工作量實(shí)在太大，故而敬請(qǐng)各為原諒！2.1漢諾威塔問(wèn)題n階漢諾威塔問(wèn)題：有三根桿子A,B,C。A桿上有n個(gè)碟子 每次移動(dòng)一塊碟子,小的只能疊在大的上面 把所有碟子從A桿全部移到C桿上經(jīng)過(guò)研究發(fā)現(xiàn)，漢諾塔的破解很簡(jiǎn)單，就是按照移動(dòng)規(guī)則向一個(gè)方向移動(dòng)金片：如3階漢諾塔的移動(dòng)：AC,AB,CB,AC,BA,BC,AC2.2解析漢諾威塔問(wèn)題下面用歸納法證明n階漢諾威塔問(wèn)題，可以用n層二叉樹(shù)描述，而且它的解就是該二叉樹(shù)的中序遍歷序列。用一個(gè)四元組(n,A,B,C)表示把n個(gè)盤(pán)子從A搬到C,中間可以借助B的n階漢諾威塔問(wèn)題。其中A、B、C的地位是相

4、對(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。假設(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í)，去

5、掉過(guò)渡位置，盤(pán)子數(shù)加括號(hào))(見(jiàn)圖1)，其中雙親結(jié)點(diǎn)與左孩子的關(guān)系是，盤(pán)子個(gè)數(shù)減1，過(guò)渡位置和終止位置交換，與右孩子的關(guān)系是，盤(pán)子個(gè)數(shù)減1，起始位置和過(guò)渡位置交換。假如有n個(gè)盤(pán)子時(shí)，結(jié)論成立?，F(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),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)

6、。而左右子樹(shù)都是n階漢諾威塔問(wèn)題，結(jié)論也成立。到此證明完畢。如下所示：圖（a）漢諾威塔問(wèn)題狀態(tài)圖 圖（b）n階和3階漢諾威塔問(wèn)題狀態(tài)圖 三、 總體設(shè)計(jì)首先建立一個(gè)程序。然后創(chuàng)建類Hanoi，將公有繼承和私有繼承分好類。其次建立各類函數(shù)：void Hanoi:move(int numDisk,string init,string desti,string templ)void Hanoi:moveOne(int numDisk,string init,string desti)void Hanoi:Solve ()最后構(gòu)建主函數(shù)，應(yīng)用各種函數(shù)，使整個(gè)程序能運(yùn)行。解決圖3.1從而達(dá)到圖3.2所示畫(huà)

7、面即我們這個(gè)程序所要完成的功能。圖3.1 漢諾威塔游戲開(kāi)始界面圖3.2 漢諾威塔游戲結(jié)束界面四、 詳細(xì)設(shè)計(jì)漢諾威塔程序代碼：#include "iostream"#include "string"using namespace std;class Hanoi /定義類Hanoipublic : /共有成員 hanoi(int disks) totalDisks=disks; void Solve();private : /私有成員 int totalDisks; void move(int numDisk,string init,string desti

8、,string templ) ;/移動(dòng)函明void moveOne(int numDisk ,string init,string desti) ; ; void hanoi:move(int numDisk,string init,string desti,string templ) /定義移動(dòng)函數(shù) if(numDisk=1) moveOne(numDisk,init,desti);elsemove(numDisk-1,init,templ,desti);moveOne(numDisk,init,desti);move(numDisk-1,templ,desti,init);void han

9、oi:moveOne(int numDisk,string init,string desti)cout<<"移動(dòng)塔層 "<<numDisk<<" from "<<init <<" to "<<desti<<endl;void hanoi:Solve ()string init="A",desti="C",templ="B"move(totalDisks,init,desti,templ);i

10、nt main(int argc, char* argv) /主函數(shù) int a;loop:cout<<"請(qǐng)輸入你想要輸入的漢諾威塔的層數(shù)："<<endl;cin>>a;cout<<"塔層數(shù)從上至下編號(hào)為1、2、3、4、5、6,"<<endl;hanoi hanoi(a);hanoi.Solve();goto loop;return 0;五、 系統(tǒng)實(shí)現(xiàn)程序運(yùn)行如下：圖5.1 程序運(yùn)行界面圖5.2 4層漢諾威塔運(yùn)行界面六、結(jié)論通過(guò)這次課程設(shè)計(jì)，讓我對(duì)數(shù)據(jù)結(jié)構(gòu)有了新一層的了解，讓我明白各種函數(shù)以及類

11、的應(yīng)用，明白了算法對(duì)程序的重要性。由于本次程序是解決一個(gè)游戲的過(guò)關(guān)問(wèn)題，所以必須親自玩那個(gè)游戲，從而推出程序的重要性。這玩游戲的過(guò)程讓我感覺(jué)到漢諾威塔的趣味性，這是一個(gè)集智益與娛樂(lè)于一體的游戲，很值得一玩。本程序運(yùn)行13層以下速度很快，13層以上則要等一段時(shí)間了。圖7.1結(jié) 束 語(yǔ)本次課程設(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)了可視化的漢諾威塔算法。程序設(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í)。 對(duì)我們計(jì)算機(jī)專業(yè)的本科生來(lái)說(shuō)，實(shí)際能力的培養(yǎng)至關(guān)重要，而這種實(shí)際能力的培養(yǎng)單靠課堂教學(xué)是遠(yuǎn)遠(yuǎn)不夠的，必須從課堂走