湖南農(nóng)業(yè)大學(xué)畢業(yè)論文設(shè)計(jì)

1、湖南農(nóng)業(yè)大學(xué)畢業(yè)論文（設(shè)計(jì)）,,課 題 “移動(dòng)十五”的實(shí)現(xiàn) 院 （系） 計(jì)算機(jī)與信息工程學(xué)院 年級(jí)專(zhuān)業(yè) 2000級(jí) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)生姓名 黎 陟 指導(dǎo)老師 彭 佳 紅,摘要,拼圖游戲是一類(lèi)曾一度廣受歡迎的益智類(lèi)游戲。數(shù)字拼圖就是其中的一種。拼圖游戲的基本規(guī)則就是將原來(lái)雜亂無(wú)章的圖片碎快或數(shù)字通過(guò)移動(dòng)交換位置而拼成具有一定形狀的圖形或有序的

2、數(shù)字序列。 本次設(shè)計(jì)的目的就是通過(guò)“移動(dòng)十五的實(shí)現(xiàn)”來(lái)模擬這一拼圖過(guò)程，找出其最優(yōu)解，并試圖由這些最優(yōu)解找出其中潛在的某些規(guī)律性。,,“移動(dòng)十五”就是在一個(gè)4*4方陣中填入0-15這16個(gè)數(shù)（其中0代表空格），只有在0上下左右四個(gè)方位的數(shù)字才可與0交換（移入空格）。在如此規(guī)則之下移動(dòng)方陣中的數(shù)字，以達(dá)到一定的目標(biāo)狀態(tài) 本設(shè)計(jì)采用回溯法來(lái)實(shí)現(xiàn)找最優(yōu)解,移動(dòng)十五概述系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)程序演示總結(jié),移動(dòng)十五概述,“移動(dòng)

3、十五”就是在一個(gè)4*4方陣中填入0-15這16個(gè)數(shù)（其中0代表空格），只有在0上下左右四個(gè)方位的數(shù)字才可與0交換（移入空格）。在如此規(guī)則之下移動(dòng)方陣中的數(shù)字，以達(dá)到一定的目標(biāo)狀態(tài)。下面圖1—1和圖1—2分別表示一個(gè)初始狀態(tài)和一個(gè)目標(biāo)狀態(tài)。,圖1-1初態(tài),圖1-2目標(biāo)態(tài),設(shè)計(jì)要求從給定的狀態(tài)找到達(dá)到給定的目標(biāo)狀態(tài)的最優(yōu)解，并演示此最優(yōu)解。,系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn),1.設(shè)計(jì)思路 本程序從界面設(shè)計(jì)入手，結(jié)合界面來(lái)調(diào)用相關(guān)模塊以實(shí)現(xiàn)各相

4、應(yīng)功能。 然后重點(diǎn)進(jìn)行算法的實(shí)現(xiàn)。 首先構(gòu)思出算法的主要思想，根據(jù)此思想給出算法的基本步驟。然后設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)，寫(xiě)出算法的自然語(yǔ)言形式的代碼。最后結(jié)合程序?qū)⑺惴ㄓ脛?dòng)態(tài)效果體現(xiàn)出來(lái)。,,最后進(jìn)行系統(tǒng)的完善，包括界面的完善，以及算法正確性的驗(yàn)證。,界面的實(shí)現(xiàn),程序首先設(shè)置一主窗口，通過(guò)下拉菜單來(lái)進(jìn)行各項(xiàng)功能選擇：ＰＬＡＹ：用戶(hù)進(jìn)入數(shù)字拼圖游戲，將一隨機(jī)產(chǎn)生的初始狀態(tài)通過(guò)移動(dòng)變?yōu)閺男〉酱笈帕械臄?shù)字序

5、列的終狀態(tài)。ＳＨＯＷ：給出一初始狀態(tài)，演示其達(dá)到目的狀態(tài)最優(yōu)路徑的過(guò)程。ＣＨＯＯＳＥ：進(jìn)行難度選擇（即選擇９格或１６格）。ＥＸＩＴ：退出程序。,,然后進(jìn)行每個(gè)模塊的界面設(shè)計(jì)，主要是數(shù)字方格的動(dòng)態(tài)演示過(guò)程的實(shí)現(xiàn)。 其中數(shù)字方格及移動(dòng)操作都設(shè)計(jì)為單個(gè)模塊，以便更方便地與算法所用的數(shù)據(jù)結(jié)構(gòu)結(jié)合。 最后是添加各種效果，如提示文字、按鈕效果等。,算法的設(shè)計(jì)與實(shí)現(xiàn),本設(shè)計(jì)核心算法采用回溯法，以回溯來(lái)窮搜舉所有可能

6、由初始態(tài)達(dá)到目標(biāo)狀態(tài)的路徑（規(guī)定了最大路徑長(zhǎng)度，即最大解深度）。,算法步驟,首先根據(jù)設(shè)定的規(guī)則進(jìn)行移動(dòng)，利用一個(gè)棧Stack將每一次移動(dòng)后的狀態(tài)以棧頂結(jié)點(diǎn)形式保存。每次移動(dòng)前都判斷移動(dòng)后的狀態(tài)是否與棧中各結(jié)點(diǎn)狀態(tài)相同，若相同，則改變方向（即更改規(guī)則）進(jìn)行移動(dòng)。若此狀態(tài)下移動(dòng)規(guī)則用完，則從棧中彈出頂點(diǎn)結(jié)點(diǎn)，即回溯一步。,如此繼續(xù)，直至找到一個(gè)解（即到達(dá)目標(biāo)狀態(tài)的一條路徑），并保存。此時(shí)需回溯兩步，改變移動(dòng)方向以繼續(xù)找更優(yōu)解，因?yàn)榛厮菀徊綄?shí)

7、際上沒(méi)有意義。若不行，則再回溯一步，且更改移動(dòng)方向，繼續(xù)找。若找到一個(gè)更優(yōu)解，則將此更優(yōu)解替換先前的最優(yōu)解。直到棧中沒(méi)有結(jié)點(diǎn)，則此時(shí)的最優(yōu)解即為所要求的最優(yōu)解。,算法具體步驟如下：1. 讀取初始狀態(tài)start和目標(biāo)狀態(tài)goal，判斷輸入的狀態(tài)是否合法，不合法退出。（合法性主要是指是否有重復(fù)的或是否越界）；2．初始狀態(tài)start是否與目標(biāo)狀態(tài)goal完全相同以及初始狀態(tài)start是可達(dá)到目標(biāo)狀態(tài)goal，完全相同或不能達(dá)到 就退出；

8、3．置初始解數(shù)為0,解深度為0；,4.初始狀態(tài)start作為當(dāng)前結(jié)點(diǎn)infor的狀態(tài)infor->state，同時(shí)作為棧頂界點(diǎn)的狀態(tài)。置深度infor->deep=0;移動(dòng)規(guī)則infor->rule=0; 5.將棧頂結(jié)點(diǎn)賦給infor. 6.判斷infor->rule是否大于等于4。若是，表示當(dāng)前狀態(tài)已向各個(gè)方向進(jìn)行過(guò)搜索，因此應(yīng)回溯一步，即棧頂結(jié)點(diǎn)指針first減1，彈出一結(jié)點(diǎn)，同時(shí)棧頂結(jié)點(diǎn)的

9、rule值加1。此時(shí)繼續(xù)判斷first是否為-1，若是，表明棧空，跳至 15。否則返回5。 7.繼續(xù)判斷當(dāng)前結(jié)點(diǎn)深度是否大于預(yù)測(cè)深度或當(dāng)前最優(yōu)解深度，若大于則回溯一步，同時(shí)棧頂結(jié)點(diǎn)規(guī)則加一，返回5。,（ 8.根據(jù)當(dāng)前狀態(tài)的空格‘0’位置，根據(jù)移動(dòng)規(guī)則獲得預(yù)移入空格的方格位置（x,y)。移動(dòng)規(guī)則0，1，2，3分別對(duì)應(yīng)‘0’的下，右，左，上四個(gè)相鄰位置，移入規(guī)則是可根據(jù)需要自定義的。9. 判斷當(dāng)前預(yù)移入方格的位置是否越界。若越

10、界，則當(dāng)前狀態(tài)結(jié)點(diǎn)的移動(dòng)規(guī)則infor->rule+1,返回5；否則繼續(xù)。10. 預(yù)先判斷移動(dòng)后的狀態(tài)是否與棧中某一結(jié)點(diǎn)狀態(tài)相同。若是，則當(dāng)前結(jié)點(diǎn)移動(dòng)規(guī)則加1，返回5。否則繼續(xù)。,11.交換方格（移入空格），當(dāng)前結(jié)點(diǎn)狀態(tài)infor為移后的狀態(tài)，且infor->rule重置為0,infor->deep+1。12.infor入棧，若infor的狀態(tài)與目標(biāo)態(tài)不同返回5，否則轉(zhuǎn)13。13.如果預(yù)測(cè)深度exp大于當(dāng)前結(jié)點(diǎn)i

11、nfo的深度info->deep,去掉以前深度較大的結(jié)果,深度result[Rp].deep等于當(dāng)前結(jié)點(diǎn)的深度info->deep14．保存結(jié)果，置有解標(biāo)志，flag=1;轉(zhuǎn)5； 15. 顯示保存的結(jié)果，即最優(yōu)解。16. 結(jié)束。,總結(jié),用C語(yǔ)言設(shè)計(jì)界面的難處。要想成為一個(gè)優(yōu)秀而純粹的程序員，數(shù)據(jù)結(jié)構(gòu)的深入學(xué)習(xí)是必須的課程，對(duì)各種算法更應(yīng)要有自己獨(dú)到而深刻的理解。在精通一門(mén)設(shè)計(jì)語(yǔ)言的情況下，如能對(duì)各種設(shè)計(jì)語(yǔ)言都有一定程

12、度的掌握，那么這樣的程序員才有更強(qiáng)的生命力，才能在社會(huì)立足和發(fā)展。,設(shè)計(jì)過(guò)程中的優(yōu)缺點(diǎn) 1.優(yōu)點(diǎn)：界面的設(shè)計(jì)；整個(gè)設(shè)計(jì)過(guò)程工 程化思想的運(yùn)用；算法與界面的結(jié)合。 2. 缺點(diǎn)：對(duì)于無(wú)解這種情況采取了回避； 程序代碼仍顯凌亂，且冗余度仍較大； 對(duì)程序設(shè)計(jì)的整體規(guī)劃仍有所欠缺；在文擋及演示稿的編寫(xiě)過(guò)程中，對(duì)所用到的辦公軟件不熟悉。,多謝各位答辯老師 指導(dǎo)