馬踏棋盤課程設計

《馬踏棋盤課程設計》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、學號：課程設計計算機科學與技術(shù)學院題目學院專業(yè)班級姓名指導教師馬踏棋盤2013年7月4日課程設計任務書學生姓名：專業(yè)班級：指導教師：工作單位：物聯(lián)網(wǎng)工程系題目：馬踏棋盤初始條件：設計一個國際象棋的馬踏遍棋盤的演示程序。將馬隨機放在國際彖棋的8X8棋盤Board[8][8]的某個方格中，馬按走棋規(guī)則（見題集p98）進行移動。耍求每個方格只進入一次，走邊棋盤上全部64個方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1,2,3,-,64依次填入一個8X8的方陣，輸出之。測試用例見題集p98。要

2、求完成的主要任務：（包括課程設計工作量及其技術(shù)要求，以及說明帖撰寫等具體要求）課程設計報告按學校規(guī)定格式用A4紙打?。〞鴮懀?，并應包含如下內(nèi)容：1、問題描述簡述題H要解決的問題是什么。2、設計存儲結(jié)構(gòu)設計、主要算法設計（用類C語言或用框圖描述）、測試用例設計；3、調(diào)試報告調(diào)試過程中遇到的問題是如何解決的；對設計和編碼的討論和分析。4、經(jīng)驗和體會（包括對算法改進的設想）5、附源程序淸?單和運行結(jié)果。源程序耍加注釋。如果題忖規(guī)定了測試數(shù)據(jù)，則運行結(jié)果耍包含這些測試數(shù)據(jù)和運行輸出，6、設計報告、程序不得相互抄襲和

3、拷貝；若有雷同，則所有雷同者成績均為0分。時間安排：1、第20周（7刀1H至7刀4H）完成。2、7月4日8：00到計算中心檢查程序、交課程設計報告、源程序（CD盤）。指導教師簽名：年月日系主任（或責任教師）簽名：年月日問題描述一、問題設計一個國際象棋的馬踏棋盤的演示程序。二基本要求將馬隨機放在國際象棋8*8的棋盤Board[8][8]的某個方格中，馬按走棋規(guī)則進行移動。要求每個方格只進入一次，走遍棋盤全部的64個方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1,2,3……?64—次填入一

4、個8*8的方陣輸出Z三、測試數(shù)據(jù)可自行指定一個馬的初始位置(i,j),0<=i,j<=7.o四、實現(xiàn)提示一般說來，當馬位于位置(i,j)時，可以走到下列8個位置之一(i-2,j+1),(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1),(i+1,j-2),(i-1,j-2),(i-2,j-1)但是，如果(i,j)靠近棋盤的邊緣，上述有些位置可能超出棋盤范圍，成為不允許的位置。8個可能位置可以用一維數(shù)組Htryl[0---7]和HTry2[0..7]來表示：-2-11221-1-2

5、Htry201234561221-1-2-2-1Htryl23401567位于(i,j)的馬可以走到新位置是在棋盤范圍內(nèi)的(i+Htryl[h],j+Htry2[h])，其中h=0,1,-.7五、選作內(nèi)容:(1)求岀從某一起點岀發(fā)的多條至全部行走路線。(2)探討每次選擇位置的“最佳策略”，以減少凹溯的次數(shù)。(3)演示尋找行走路線的回溯過程。設計一*問題分析馬踏棋盤的演示程序涉及一下兒個方面：1.棋盤的表示2.如何在只進入每個方格一次的情況下確定下一步位置3.當出現(xiàn)“死棋”時如何實現(xiàn)“回溯”(悔棋)4.如何判

6、定已經(jīng)走遍了棋盤上所有的方格5.如何實現(xiàn)整個行走路線的輸出6.效率優(yōu)化二問題的解決方案1.棋盤用二維數(shù)組board[8][8]表示，其中board[i][j]=0,表示第i行、第j列的方格尚未被訪問;board[i][j]=l,表示第i行、第j列的方格已經(jīng)被訪問過了。2.由提示知：當馬位于位置(i,j)時，可以走到下列8個位置乙一(i—2,j+1),(i—l,j+2),(i+1,j+2),(i+2,j+1),(i+2,j—l),(i+1,j—2),(i-1,j-2),(i-2,j-1)因此HTry[d]表示

7、下一步可能走位置。再由判定函數(shù)intcheck(intx,inty)和數(shù)組board[8][8]判定該位置是否合法(既在8*8的棋盤內(nèi)，而且未被訪問過)。3.利用?！昂筮M先出”的特點實現(xiàn)對每一步棋的記錄，當出現(xiàn)死棋時通過出棧操作實現(xiàn)“回溯”。4.用變量step實現(xiàn)對走棋次數(shù)的記錄，每走一步step++,當step二63(step初始值為0)時表示已經(jīng)走遍整個棋盤。5.由于每一步走棋都記錄在棧中，因此構(gòu)造數(shù)組c[8][8],將棧中數(shù)據(jù)的輸出次序逆向按自身存儲的i、j輸出到對應的c[i][j]中，再逐行輸出數(shù)組

8、c[8][8]的內(nèi)容，即可實現(xiàn)對整個行走路線的輸出。6.如果單純的按照以上方法編寫出的程序，在運行時需要花費極多的時間才能運行出結(jié)果，這在效率上產(chǎn)生了極大的浪費。因此，需要對算法進行優(yōu)化處理。通過杳找資料，決定采用貪婪算法對算法做出優(yōu)化。以下是關(guān)于貪婪法的介紹：貪焚算法是指,在對問題求解時，總是做出在當前看來是最好的選擇。也就是說,不從整體最優(yōu)上加以考慮,他所做出的僅是在某種意??義上的局部最優(yōu)解。那么我們在回溯