漢諾塔課程設(shè)計(jì)--漢諾塔演示程序設(shè)計(jì)

1、<p><b>　　課程設(shè)計(jì)</b></p><p>　　題 目： 漢諾塔演示程序設(shè)計(jì) </p><p>　　院 （系）： </p><p>　　年級(jí)專業(yè)： </p><p>　　姓 名：

2、 </p><p>　　學(xué) 號(hào)： </p><p>　　指導(dǎo)教師： </p><p>　　本科學(xué)生課程設(shè)計(jì)任務(wù)書</p><p>　　注：任務(wù)書由指導(dǎo)教師填寫。</p><p><b

3、>　　摘 要</b></p><p>　　漢諾塔（又稱河內(nèi)塔）問題是一個(gè)古典的數(shù)學(xué)問題，是一個(gè)用遞歸方法解題的典型例子。問題是這樣的：開天辟地的神勃拉瑪在一個(gè)廟里留下了三根金剛石的棒，第一根上面套著64個(gè)圓的金片，最大的一個(gè)在底下，其余一個(gè)比一個(gè)小，依次疊上去，廟里的眾僧不倦地把它們一個(gè)個(gè)地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個(gè)，而且大的不能放在小的上面。 B

4、2Awdw3=g  </p><p>　　利用計(jì)算機(jī)圖形學(xué)進(jìn)行漢諾塔演示程序設(shè)計(jì),是利用C語言繪圖函數(shù)實(shí)現(xiàn)漢諾塔的遞歸算法圖形界面演示過程。通過C語言實(shí)現(xiàn)圖形學(xué)的繪圖，程序控制，以及區(qū)域填充，并根據(jù)漢諾塔的算法原理實(shí)現(xiàn)大小不同的盤子移動(dòng)的全過程演示。</p><p>　　關(guān)鍵詞 漢諾塔，變換矩陣，種子填充算法，遞歸調(diào)用</p><p><b>

5、;　　目 錄</b></p><p><b>　　摘 要I</b></p><p><b>　　1 需求分析1</b></p><p>　　1.1 需求概述1</p><p>　　1.2 需求環(huán)境1</p><p>　　1.3 功能描述2</

6、p><p><b>　　2 概要設(shè)計(jì)3</b></p><p>　　2.1 程序功能模塊3</p><p>　　2.2 程序流程圖3</p><p>　　2.3 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)4</p><p><b>　　3 詳細(xì)設(shè)計(jì)5</b></p><p>

7、;　　3.1 程序初始化5</p><p>　　3.1.1 代碼功能5</p><p>　　3.1.2 功能實(shí)現(xiàn)代碼5</p><p>　　3.2 盤塊的移動(dòng)過程5</p><p>　　3.2.1代碼功能5</p><p>　　3.2.2 功能實(shí)現(xiàn)代碼5</p><p>　　3.3

8、遞歸函數(shù)6</p><p>　　3.3.1 流程圖6</p><p>　　3.3.2 功能實(shí)現(xiàn)代碼7</p><p><b>　　4 測(cè)試與運(yùn)行8</b></p><p><b>　　結(jié)束語9</b></p><p><b>　　參考文獻(xiàn)10</b

9、></p><p><b>　　1 需求分析</b></p><p><b>　　1.1 需求概述</b></p><p>　　漢諾塔演示程序設(shè)計(jì)是計(jì)算機(jī)圖形學(xué)中圖形變換的內(nèi)容之一。而圖形學(xué)中的圖形變換的概念是由簡(jiǎn)單圖形生成復(fù)雜圖形，可用二維圖形表示三維形體，甚至可以對(duì)靜態(tài)圖形經(jīng)過快速變換而獲得圖形的動(dòng)態(tài)顯示效果。

10、其任務(wù)是研究各點(diǎn)坐標(biāo)之間的變化規(guī)律。而本次課程設(shè)計(jì)就是利用C語言以及圖形函數(shù)實(shí)現(xiàn)漢諾塔的遞歸算法來進(jìn)行其盤塊移動(dòng)的全過程顯示。在TC環(huán)境中要實(shí)現(xiàn)這樣的功能，就要牽涉到圖形設(shè)備接口的知識(shí)。Windows圖形設(shè)備接口是為與設(shè)備無關(guān)的圖形設(shè)計(jì)的，是Windows系統(tǒng)的重要組成部分,負(fù)責(zé)系統(tǒng)與用戶或繪圖程序之間的信息交換,并控制在輸出設(shè)備上顯示圖形或文字。應(yīng)用程序必須通知圖形設(shè)備接口來加載特定的設(shè)備驅(qū)動(dòng)，一旦驅(qū)動(dòng)得以加載，就可以準(zhǔn)備應(yīng)用設(shè)備進(jìn)行

11、相關(guān)的操作這些任務(wù)都要通過創(chuàng)建和維護(hù)設(shè)備描述表來完成。在實(shí)現(xiàn)漢諾塔演示程序設(shè)計(jì)時(shí)，是利用坐標(biāo)系統(tǒng)而得到的，而在Windows應(yīng)用程序中有兩種坐標(biāo)系統(tǒng)：設(shè)備坐標(biāo)系統(tǒng)和邏輯坐標(biāo)系統(tǒng)。其中設(shè)備坐標(biāo)系統(tǒng)中又有三種相互獨(dú)立的坐標(biāo)系統(tǒng)：屏幕坐標(biāo)系統(tǒng)、窗口坐標(biāo)系統(tǒng)和用戶區(qū)坐標(biāo)系統(tǒng)。這些坐標(biāo)系統(tǒng)均以像素點(diǎn)來表示度量的單位。屏幕坐標(biāo)系統(tǒng)使用整個(gè)屏幕作為坐標(biāo)區(qū)域，原點(diǎn)為屏幕原點(diǎn)。窗口坐標(biāo)系</p><p>　　在計(jì)算機(jī)機(jī)圖形學(xué)中窗口

12、的定義是指在用戶坐標(biāo)系中定義的確定顯示內(nèi)容的一個(gè)矩形區(qū)域，只有在這個(gè)區(qū)域內(nèi)的圖形才能在設(shè)備坐標(biāo)系下輸出，而窗口外的部分則被截掉。視區(qū)是在設(shè)備坐標(biāo)中定義的一個(gè)區(qū)域，用于輸出窗口中的圖形。視區(qū)決定了窗口中的圖形要顯示于屏幕上的位置的大小。</p><p><b>　　1.2 需求環(huán)境</b></p><p>　　本課程設(shè)計(jì)需要的設(shè)備為硬件要求和軟件配置要求具體要求如下：&

13、lt;/p><p>　　①硬件要求：一臺(tái)計(jì)算機(jī)。</p><p>　?、谲浖渲茫篧INDOWS、C/VC++6.0。</p><p><b>　　1.3 功能描述</b></p><p>　　本課程設(shè)計(jì)是利用圖形學(xué)的相關(guān)知識(shí)在TC或Visual C++環(huán)境下利用遞歸算法實(shí)現(xiàn)漢諾塔演示的全過程，其基本的功能描述如下:<

14、/p><p><b>　　繪制三個(gè)塔座。</b></p><p>　　在第一個(gè)塔座上繪制一個(gè)矩形（一個(gè)矩形代表一個(gè)盤子），棧的高度遞增，則矩形的大小遞減。</p><p>　　為矩形填充顏色，盤子的顏色代碼為棧頂盤子代號(hào)加1。</p><p>　　通過鼠標(biāo)或者鍵盤控制移動(dòng)矩形，將所有的矩形借助第二個(gè)塔座從第一個(gè)塔移到第三個(gè)塔

15、，并顯示每次移動(dòng)盤子的步驟。</p><p><b>　　2 概要設(shè)計(jì)</b></p><p>　　2.1 程序功能模塊</p><p>　　由需求分析知，本次課程設(shè)計(jì)是用遞歸算法實(shí)現(xiàn)漢諾塔演示程序，故其功能模塊分為：程序初始化模塊，盤塊移動(dòng)模塊，遞歸調(diào)用模塊三個(gè)模塊。</p><p>　　（可以把功能模塊用圖畫出來）

16、</p><p><b>　　2.2 程序流程圖</b></p><p>　　圖2.1 程序流程圖</p><p>　　2.3 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)</p><p>　　根據(jù)需求分析將用遞歸算法實(shí)現(xiàn)漢諾塔演示過程的數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)如下：</p><p>　　用一個(gè)結(jié)構(gòu)體數(shù)組struct M { int

17、data[15]; int top; }num[3];來定義三個(gè)塔座的高度，以及每個(gè)塔座存放每個(gè)盤塊的代號(hào)。</p><p>　　定義兩個(gè)變量cx,cy來分別表示程序演示步驟的橫坐標(biāo)和縱坐標(biāo)的變化。</p><p>　　用函數(shù)void move(char x,char y,struct M num[3]);來表示盤塊移動(dòng)的具體過程；并在move函數(shù)中調(diào)用函數(shù)void hanoi(char

18、x,char y,char z,int n,struct M num[3]);來表示遞歸調(diào)用的過程；最后用一個(gè)初始化函數(shù)void Init(void)來對(duì)整個(gè)程序進(jìn)行初始化，并調(diào)用move函數(shù)。</p><p><b>　　3 詳細(xì)設(shè)計(jì)</b></p><p><b>　　3.1 程序初始化</b></p><p><

19、;b>　　3.1.1代碼功能</b></p><p>　　在初始化程序中，主要實(shí)現(xiàn)的是繪制塔座標(biāo)志，繪制盤塊，設(shè)置塔座標(biāo)志顏色,以及填充盤塊顏色等。</p><p>　　3.1.2 功能實(shí)現(xiàn)代碼</p><p>　　①繪制塔座的代碼如下：</p><p>　　setcolor(GREEN);/*設(shè)置塔座標(biāo)志顏色*/</

20、p><p>　　outtextxy(180,450,"press any key to continue");</p><p>　　settextstyle(0,0,2);</p><p>　　outtextxy(90,420,"A"); /*塔座標(biāo)志*/</p><p>　　outtextxy(240,4

21、20,"B");</p><p>　　outtextxy(390,420,"C");</p><p>　　②繪制矩形的代碼如下：</p><p>　　setfillstyle(SOLID_FILL,color);/*設(shè)置填充顏色*/</p><p>　　bar(100-(33-3*num[0].data

22、[num[0].top]),400-20*i-8,100+</p><p>　　(33-3*num[0].data[num[0].top]),400-20*i+8); /*畫矩形*/</p><p>　　3.2 盤塊的移動(dòng)過程</p><p><b>　　3.2.1代碼功能</b></p><p>　　盤塊的移動(dòng)實(shí)際上是

23、一個(gè)出棧和入棧的過程，盤塊出棧后便將原來的地方涂黑，本塊代碼主要是實(shí)現(xiàn)顯示漢諾塔的具體移動(dòng)的演示過程及移動(dòng)步驟。</p><p>　　3.2.2 功能實(shí)現(xiàn)代碼</p><p>　　void move(char x,char y,struct M num[3])/*移動(dòng)的具體過程*/</p><p><b>　　{</b></p>

24、<p><b>　　int i;</b></p><p>　　char num1[3],num2[3];</p><p>　　sprintf(num1,"%c",x-32);/*將小寫變成大寫，并轉(zhuǎn)換成字符串輸出*/</p><p>　　sprintf(num2,"%c",y-32);</

25、p><p>　　setfillstyle(SOLID_FILL,BLACK);/*把原來的地方移去涂黑*/</p><p>　　setcolor(YELLOW);</p><p>　　outtextxy(20+cx,30+cy,num1);/*輸出移動(dòng)過程，每次移動(dòng)后縱坐標(biāo)加30*/</p><p>　　outtextxy(62+cx,30+cy

26、,"-->");</p><p>　　outtextxy(130+cx,30+cy,num2);</p><p><b>　　cy+=30;</b></p><p>　　if(cy>210) /*橫坐標(biāo)換行后另起一列*/</p><p>　　{ cx+=145;</p>&

27、lt;p>　　cy=0;/*縱坐標(biāo)重新回到頂部開始顯示下一列的演示步驟 */</p><p><b>　　}</b></p><p>　　settextstyle(0,0,2);</p><p>　　setfillstyle(SOLID_FILL,BLACK);/*把原來的地方移去涂黑*/</p><p>　　ba

28、r(100+150*(x-97)-(33-3*num[x-97].data[num[x-97].top]),400-20*num</p><p>　　[x-97].top-8,100+150*(x-97)+(33-3*</p><p>　　num[x-97].data[num[x-97].top]),400-20*num[x-97].top+8);num[y-97].top++;/*入棧，

29、目標(biāo)點(diǎn)的top加1*/</p><p>　　num[y-97].data[num[y-97].top]=num[x-97].data[num[x-97].top];/*在目標(biāo)點(diǎn)盤子的代號(hào)與源點(diǎn)盤子的代號(hào)相同*/</p><p>　　num[x-97].top--;/*出棧，原來地方的top減1*/</p><p>　　setfillstyle(SOLID_FILL,

30、num[y-97].data[num[y-97].top]+1);/*盤子顏色代碼是棧頂盤子代號(hào)加1*/</p><p>　　bar(100+150*(y-97)-(33-3*num[y-97].data[num[y-97].top]),400-20*</p><p>　　num[y-97].top-8,100+150*(y-97)+(33-3*num[y-97].data[num[y-9

31、7].top]),</p><p>　　400-20*num[y-97].top+8);</p><p>　　getch( );/*自己按鍵盤來進(jìn)行手動(dòng)控制*/</p><p><b>　　3.3 遞歸函數(shù)</b></p><p><b>　　3.3.1 流程圖</b></p><

32、;p>　　根據(jù)概要設(shè)計(jì)中的實(shí)現(xiàn)遞歸函數(shù)過程的流程圖設(shè)計(jì)如圖3.3所示：</p><p>　　圖3.1 遞歸函數(shù)</p><p>　　3.3.2 功能實(shí)現(xiàn)代碼</p><p>　　漢諾塔演示程序設(shè)計(jì)主要是利用遞歸調(diào)用函數(shù)實(shí)現(xiàn)。函數(shù)調(diào)用hanoi( one,two,three,n,num)表示將n個(gè)盤塊從A座移到C座的過程，函數(shù)調(diào)用move(one,three,

33、num)是將1個(gè)盤塊從A座移到C座的過程。其具體代碼實(shí)現(xiàn)如下：</p><p><b>　　if(n==1)</b></p><p>　　move(one,three,num);/*如果盤子為1，將這個(gè)盤子從塔座A移動(dòng)到塔座C*/</p><p><b>　　else</b></p><p><

34、;b>　　{</b></p><p>　　hanoi(one,three,two,n-1,num);/*將塔座A的前n-1個(gè)盤子移到塔座B*/</p><p>　　move(one,three,num);/*將塔座A的第n個(gè)盤子移到塔座C*/</p><p>　　hanoi(two,one,three,n-1,num); /*將塔座B的n-1個(gè)盤子

35、移到塔座C*/</p><p><b>　　}</b></p><p><b>　　4 測(cè)試與運(yùn)行</b></p><p>　　由需求分析可知，漢諾塔演示程序設(shè)計(jì)是在TC環(huán)境下利用遞歸算法實(shí)現(xiàn)大小不同的盤子移動(dòng)的全過程演示。本程序已調(diào)試成功并實(shí)現(xiàn)了其功能，當(dāng)移動(dòng)盤塊數(shù)為3時(shí),其運(yùn)行結(jié)果如下：</p><

36、p>　　圖4.1 盤塊移動(dòng)前</p><p>　　圖4.2 盤塊移動(dòng)中</p><p>　　圖4.3 盤塊移動(dòng)后</p><p><b>　　結(jié)束語</b></p><p>　　在這次課程設(shè)計(jì)中，我基本上完成了任務(wù)，通過遞歸調(diào)用算法實(shí)現(xiàn)了漢諾塔的演示過程,以及盤塊移動(dòng)的具體步驟的顯示,基本上達(dá)到了此次課程設(shè)計(jì)的要求

37、。但是它的不足也是顯而易見的，在盤塊移動(dòng)的過程中用方向鍵移動(dòng)時(shí)會(huì)一次顯示兩個(gè)步驟,這給用戶的實(shí)際操作帶來了一定的困難，所以這是值得改進(jìn)的地方，整個(gè)程序的功能有待進(jìn)一步完善，讓更多的方法能得以實(shí)現(xiàn)。</p><p>　　雖然在這次的課程設(shè)計(jì)中有很多的不足，但是我也有很多的收獲。上網(wǎng)查找資料，找到了一個(gè)基于TC對(duì)話框而實(shí)現(xiàn)的漢諾塔演示程序設(shè)計(jì)，于是我們就開始研究它的算法，如何畫三個(gè)塔座，如何填充盤塊的顏色，如何實(shí)現(xiàn)盤

38、塊的移動(dòng)。再運(yùn)用這些知識(shí)在TC中實(shí)現(xiàn)這次課程設(shè)計(jì)所要完成的任務(wù)。這讓我不僅對(duì)TC開發(fā)環(huán)境有了更多的認(rèn)識(shí)和了解，對(duì)其圖形設(shè)備接口的知識(shí)也有了很好的掌握，而且讓我對(duì)圖形學(xué)的知識(shí)有了更好的運(yùn)用，拓展了對(duì)圖形學(xué)的知識(shí)了解的視野，讓我的理論知識(shí)和算法有了更多的實(shí)踐。作為一個(gè)大的項(xiàng)目，我更體會(huì)到了團(tuán)隊(duì)合作精神的重要性，雖然我的設(shè)計(jì)是一個(gè)人一組的,但我深刻地認(rèn)識(shí)到只有大家一起努力地學(xué)習(xí)并研究相關(guān)的知識(shí)，才能提高做事的效率，也才能更好更快地完成任務(wù)。所

39、以這將在我以后的學(xué)習(xí)和生活中有很在的引導(dǎo)作用。在以后的學(xué)習(xí)中，我也將加倍地學(xué)習(xí)圖形學(xué)的有關(guān)知識(shí)，以同樣的方法學(xué)習(xí)其他的知識(shí)，不斷地豐富自己，充實(shí)自己，提高自己的能力。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] Hearn(赫恩)Baker 著.計(jì)算機(jī)圖形學(xué)== Computer Graphics:C語言版. 清華大學(xué)出版社,2004&

40、lt;/p><p>　　[2] 陳桂芳. 微型計(jì)算機(jī)圖形學(xué). 北京理工大學(xué)出版社. 1989</p><p>　　[3] 陳元琰編著．計(jì)算機(jī)圖形學(xué)實(shí)用技術(shù)．科學(xué)出版社.2000</p><p>　　[4] 柳朝陽,周曉平.計(jì)算機(jī)圖形學(xué):圖形的計(jì)算與顯示原理. 西安電子科技大學(xué)出版社 .2005</p><p>　　[5] 陸潤(rùn)