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

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

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

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

4、2Awdw3=g  </p><p>　　利用計算機圖形學(xué)進行漢諾塔演示程序設(shè)計,是利用C語言繪圖函數(shù)實現(xiàn)漢諾塔的遞歸算法圖形界面演示過程。通過C語言實現(xiàn)圖形學(xué)的繪圖，程序控制，以及區(qū)域填充，并根據(jù)漢諾塔的算法原理實現(xiàn)大小不同的盤子移動的全過程演示。</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è)計3</b></p><p>　　2.1 程序功能模塊3</p><p>　　2.2 程序流程圖3</p><p>　　2.3 數(shù)據(jù)結(jié)構(gòu)的設(shè)計4</p><p><b>　　3 詳細設(shè)計5</b></p><p>

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

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

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

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

11、相關(guān)的操作這些任務(wù)都要通過創(chuàng)建和維護設(shè)備描述表來完成。在實現(xiàn)漢諾塔演示程序設(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)中又有三種相互獨立的坐標(biāo)系統(tǒng)：屏幕坐標(biāo)系統(tǒng)、窗口坐標(biāo)系統(tǒng)和用戶區(qū)坐標(biāo)系統(tǒng)。這些坐標(biāo)系統(tǒng)均以像素點來表示度量的單位。屏幕坐標(biāo)系統(tǒng)使用整個屏幕作為坐標(biāo)區(qū)域，原點為屏幕原點。窗口坐標(biāo)系</p><p>　　在計算機機圖形學(xué)中窗口

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

13、lt;/p><p>　?、儆布螅阂慌_計算機。</p><p>　?、谲浖渲茫篧INDOWS、C/VC++6.0。</p><p><b>　　1.3 功能描述</b></p><p>　　本課程設(shè)計是利用圖形學(xué)的相關(guān)知識在TC或Visual C++環(huán)境下利用遞歸算法實現(xiàn)漢諾塔演示的全過程，其基本的功能描述如下:<

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

15、，并顯示每次移動盤子的步驟。</p><p><b>　　2 概要設(shè)計</b></p><p>　　2.1 程序功能模塊</p><p>　　由需求分析知，本次課程設(shè)計是用遞歸算法實現(xiàn)漢諾塔演示程序，故其功能模塊分為：程序初始化模塊，盤塊移動模塊，遞歸調(diào)用模塊三個模塊。</p><p>　?。梢园压δ苣K用圖畫出來）

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

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

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

19、;b>　　3.1.1代碼功能</b></p><p>　　在初始化程序中，主要實現(xiàn)的是繪制塔座標(biāo)志，繪制盤塊，設(shè)置塔座標(biāo)志顏色,以及填充盤塊顏色等。</p><p>　　3.1.2 功能實現(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>　?、诶L制矩形的代碼如下：</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 盤塊的移動過程</p><p><b>　　3.2.1代碼功能</b></p><p>　　盤塊的移動實際上是

23、一個出棧和入棧的過程，盤塊出棧后便將原來的地方涂黑，本塊代碼主要是實現(xiàn)顯示漢諾塔的具體移動的演示過程及移動步驟。</p><p>　　3.2.2 功能實現(xiàn)代碼</p><p>　　void move(char x,char y,struct M num[3])/*移動的具體過程*/</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);/*輸出移動過程，每次移動后縱坐標(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)點的top加1*/</p><p>　　num[y-97].data[num[y-97].top]=num[x-97].data[num[x-97].top];/*在目標(biāo)點盤子的代號與源點盤子的代號相同*/</p><p>　　num[x-97].top--;/*出棧，原來地方的top減1*/</p><p>　　setfillstyle(SOLID_FILL,

30、num[y-97].data[num[y-97].top]+1);/*盤子顏色代碼是棧頂盤子代號加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( );/*自己按鍵盤來進行手動控制*/</p><p><b>　　3.3 遞歸函數(shù)</b></p><p><b>　　3.3.1 流程圖</b></p><

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

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

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

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

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

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

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

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

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