湖南農業大學畢業論文設計

1、湖南農業大學畢業論文（設計）,,課 題 “移動十五”的實現 院 （系） 計算機與信息工程學院 年級專業 2000級 計算機科學與技術學生姓名 黎 陟 指導老師 彭 佳 紅,摘要,拼圖游戲是一類曾一度廣受歡迎的益智類游戲。數字拼圖就是其中的一種。拼圖游戲的基本規則就是將原來雜亂無章的圖片碎快或數字通過移動交換位置而拼成具有一定形狀的圖形或有序的

2、數字序列。 本次設計的目的就是通過“移動十五的實現”來模擬這一拼圖過程，找出其最優解，并試圖由這些最優解找出其中潛在的某些規律性。,,“移動十五”就是在一個4*4方陣中填入0-15這16個數（其中0代表空格），只有在0上下左右四個方位的數字才可與0交換（移入空格）。在如此規則之下移動方陣中的數字，以達到一定的目標狀態 本設計采用回溯法來實現找最優解,移動十五概述系統設計與實現程序演示總結,移動十五概述,“移動

3、十五”就是在一個4*4方陣中填入0-15這16個數（其中0代表空格），只有在0上下左右四個方位的數字才可與0交換（移入空格）。在如此規則之下移動方陣中的數字，以達到一定的目標狀態。下面圖1—1和圖1—2分別表示一個初始狀態和一個目標狀態。,圖1-1初態,圖1-2目標態,設計要求從給定的狀態找到達到給定的目標狀態的最優解，并演示此最優解。,系統設計與實現,1.設計思路 本程序從界面設計入手，結合界面來調用相關模塊以實現各相

4、應功能。 然后重點進行算法的實現。 首先構思出算法的主要思想，根據此思想給出算法的基本步驟。然后設計合適的數據結構，寫出算法的自然語言形式的代碼。最后結合程序將算法用動態效果體現出來。,,最后進行系統的完善，包括界面的完善，以及算法正確性的驗證。,界面的實現,程序首先設置一主窗口，通過下拉菜單來進行各項功能選擇：ＰＬＡＹ：用戶進入數字拼圖游戲，將一隨機產生的初始狀態通過移動變為從小到大排列的數字序

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

6、由初始態達到目標狀態的路徑（規定了最大路徑長度，即最大解深度）。,算法步驟,首先根據設定的規則進行移動，利用一個棧Stack將每一次移動后的狀態以棧頂結點形式保存。每次移動前都判斷移動后的狀態是否與棧中各結點狀態相同，若相同，則改變方向（即更改規則）進行移動。若此狀態下移動規則用完，則從棧中彈出頂點結點，即回溯一步。,如此繼續，直至找到一個解（即到達目標狀態的一條路徑），并保存。此時需回溯兩步，改變移動方向以繼續找更優解，因為回溯一步實

7、際上沒有意義。若不行，則再回溯一步，且更改移動方向，繼續找。若找到一個更優解，則將此更優解替換先前的最優解。直到棧中沒有結點，則此時的最優解即為所要求的最優解。,算法具體步驟如下：1. 讀取初始狀態start和目標狀態goal，判斷輸入的狀態是否合法，不合法退出。（合法性主要是指是否有重復的或是否越界）；2．初始狀態start是否與目標狀態goal完全相同以及初始狀態start是可達到目標狀態goal，完全相同或不能達到 就退出；

8、3．置初始解數為0,解深度為0；,4.初始狀態start作為當前結點infor的狀態infor->state，同時作為棧頂界點的狀態。置深度infor->deep=0;移動規則infor->rule=0; 5.將棧頂結點賦給infor. 6.判斷infor->rule是否大于等于4。若是，表示當前狀態已向各個方向進行過搜索，因此應回溯一步，即棧頂結點指針first減1，彈出一結點，同時棧頂結點的

9、rule值加1。此時繼續判斷first是否為-1，若是，表明?？?，跳至 15。否則返回5。 7.繼續判斷當前結點深度是否大于預測深度或當前最優解深度，若大于則回溯一步，同時棧頂結點規則加一，返回5。,（ 8.根據當前狀態的空格‘0’位置，根據移動規則獲得預移入空格的方格位置（x,y)。移動規則0，1，2，3分別對應‘0’的下，右，左，上四個相鄰位置，移入規則是可根據需要自定義的。9. 判斷當前預移入方格的位置是否越界。若越

10、界，則當前狀態結點的移動規則infor->rule+1,返回5；否則繼續。10. 預先判斷移動后的狀態是否與棧中某一結點狀態相同。若是，則當前結點移動規則加1，返回5。否則繼續。,11.交換方格（移入空格），當前結點狀態infor為移后的狀態，且infor->rule重置為0,infor->deep+1。12.infor入棧，若infor的狀態與目標態不同返回5，否則轉13。13.如果預測深度exp大于當前結點i

11、nfo的深度info->deep,去掉以前深度較大的結果,深度result[Rp].deep等于當前結點的深度info->deep14．保存結果，置有解標志，flag=1;轉5； 15. 顯示保存的結果，即最優解。16. 結束。,總結,用C語言設計界面的難處。要想成為一個優秀而純粹的程序員，數據結構的深入學習是必須的課程，對各種算法更應要有自己獨到而深刻的理解。在精通一門設計語言的情況下，如能對各種設計語言都有一定程

12、度的掌握，那么這樣的程序員才有更強的生命力，才能在社會立足和發展。,設計過程中的優缺點 1.優點：界面的設計；整個設計過程工 程化思想的運用；算法與界面的結合。 2. 缺點：對于無解這種情況采取了回避； 程序代碼仍顯凌亂，且冗余度仍較大； 對程序設計的整體規劃仍有所欠缺；在文擋及演示稿的編寫過程中，對所用到的辦公軟件不熟悉。,多謝各位答辯老師 指導