數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)國(guó)王與騎士

1、合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告20102011 學(xué)年第二學(xué)期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)題目名稱國(guó)王與騎士問題學(xué)生姓名余洋學(xué)號(hào)0904013015專業(yè)班級(jí)09計(jì)本（3）指導(dǎo)教師王昆侖、張貫虹2011 年 6 月一、課程設(shè)計(jì)名稱及內(nèi)容名稱：國(guó)王和騎士問題內(nèi)容：初始狀態(tài)：一個(gè)國(guó)王和N個(gè)騎士分布在8*8的棋盤上0 <= N <= 63目標(biāo)狀態(tài)：國(guó)王和所有的騎士走到同一個(gè)格子里 游戲規(guī)則：在一次移動(dòng)中，國(guó)王可以走到相鄰的八個(gè)格子里；騎士可以走八個(gè)方向的“日”字；國(guó)王和某個(gè)騎士相遇后，可以由騎士帶著移動(dòng)。要求：編寫算法解決問題，用最少的總移動(dòng)步數(shù)達(dá)到目標(biāo)狀態(tài)。二、問題分析本程序要求實(shí)

2、現(xiàn)最短步數(shù)的計(jì)算，首先需要考慮8×8的棋盤的存儲(chǔ)方式，以及各點(diǎn)的國(guó)王或騎士的表示方法，然后考慮最少步數(shù)的計(jì)算方法，最后通過各功能函數(shù)的調(diào)用解決問題。設(shè)計(jì)程序所能達(dá)到的功能：對(duì)一個(gè)國(guó)王與n個(gè)騎士會(huì)合在同一點(diǎn)的最少步數(shù)的計(jì)算。1、數(shù)據(jù)的輸入：（1）需要輸入的數(shù)據(jù)：國(guó)王的坐標(biāo)，騎士的個(gè)數(shù)，每個(gè)騎士的坐標(biāo)；（2）數(shù)據(jù)的類型與范圍：坐標(biāo)均為2個(gè)字符，橫坐標(biāo)為AH中任意字符，縱坐標(biāo)為18中任意字符，騎士個(gè)數(shù)須在0與64之間（不包括0、64）。2、數(shù)據(jù)的輸出：輸出騎士與國(guó)王會(huì)合的最少步數(shù)、3、測(cè)試數(shù)據(jù)：（1）國(guó)王坐標(biāo)：D4 騎士個(gè)數(shù)：4 每個(gè)騎士坐標(biāo)：A3 A8 H1 H8 預(yù)計(jì)結(jié)果：最短步數(shù)為

3、10（2）國(guó)王坐標(biāo)：G1 騎士個(gè)數(shù)：3 每個(gè)騎士坐標(biāo)：C3 A7 A5 預(yù)計(jì)結(jié)果：最短步數(shù)為 7（3）國(guó)王坐標(biāo)：F3 騎士個(gè)數(shù)：5 每個(gè)騎士坐標(biāo)：A3 A5 B2 C5 D3 預(yù)計(jì)結(jié)果：最短步數(shù)為 9三、概要設(shè)計(jì)1、為了實(shí)現(xiàn)上述設(shè)計(jì)：需要：（1）定義結(jié)點(diǎn)類型，分別表示棋盤上每個(gè)點(diǎn)的x，y坐標(biāo)；（2）設(shè)計(jì)遍歷算法，因?yàn)閲?guó)王與騎士最終可能在任意一點(diǎn)相遇，所以要求其最少步數(shù)，必須遍歷棋盤上每一點(diǎn)，分別求出國(guó)王和騎士到每一點(diǎn)的步數(shù)，再進(jìn)一步比較出其最小值；（3）使用恰當(dāng)搜索算法，由于騎士以“日”字型在棋盤上走動(dòng)，要求其到達(dá)某一點(diǎn)的最短路徑必須使用搜索算法，考慮遍歷結(jié)點(diǎn)較多，采用廣度優(yōu)先搜索（BFS算法

4、）；（4）判斷國(guó)王與騎士相遇及步數(shù)，由于一旦國(guó)王與騎士相遇，騎士便可以帶著國(guó)王行動(dòng)，所以必須比較在相遇與不相遇兩種情況下的最少步數(shù)，得出最終答案；2、本程序包含4個(gè)函數(shù)：（1）主函數(shù)：main()（2）解題函數(shù)：solve()（3）計(jì)算所有點(diǎn)騎士最少步數(shù)的函數(shù)：knightmindis()（4）計(jì)算某兩點(diǎn)間出發(fā)到某點(diǎn)騎士的最少步數(shù)的函數(shù)（包含BFS算法）：BFS()各函數(shù)之間關(guān)系如下 ：main()solve()knightmindis()BFS()四、算法思想 國(guó)王與騎士位置均用坐標(biāo)表示，因?yàn)橹挥幸粋€(gè)國(guó)王，首先遍歷國(guó)王至棋盤上每一點(diǎn)的最短路徑；又有n個(gè)騎士，分別遍歷每個(gè)騎士至每一點(diǎn)的最短路徑

5、，并求它們的最短路徑之和，同樣要求最短，求國(guó)王與所有騎士的最短路徑之和org。又由于存在情況騎士帶著國(guó)王前進(jìn)，故還要考慮國(guó)王與騎士相遇時(shí)的情況，便利騎士經(jīng)過棋盤中每一點(diǎn)到另外每一點(diǎn)的步數(shù)，計(jì)算相遇時(shí)騎士帶著國(guó)王前進(jìn)的最短距離change，最后比較得到最終答案。五、詳細(xì)設(shè)計(jì)實(shí)現(xiàn)概要設(shè)計(jì)中定義的數(shù)據(jù)類型，并對(duì)每個(gè)函數(shù)操作給出流程圖、偽代碼。1、結(jié)點(diǎn)類型與定義struct Pos /定義數(shù)據(jù)類型int x,y; /x、y分別表示橫縱坐標(biāo);2、定義全局變量struct Pos king,knight63; /定義國(guó)王，騎士int mindistance8888; /任意兩點(diǎn)之間騎士的最少步數(shù)int k

6、nights; /騎士個(gè)數(shù)int mindist=32767; /最少步數(shù)3、流程圖YN開始輸入國(guó)王坐標(biāo)輸入騎士個(gè)數(shù)坐標(biāo)處理輸入次數(shù)<=騎士個(gè)數(shù)？輸入騎士坐標(biāo)坐標(biāo)處理調(diào)用解題函數(shù)solve結(jié)束 (主函數(shù))YNNY開始調(diào)用函數(shù)求所有騎士最短路徑knighmindissolve遍歷所有點(diǎn)至所有點(diǎn)，完成？計(jì)算國(guó)王最短路徑國(guó)王與騎士最短路徑之和國(guó)王與騎士重合時(shí)走過的最少步數(shù)國(guó)王與騎士不重合時(shí)走過的最少步數(shù)判斷得出最終答案結(jié)束調(diào)用廣度優(yōu)先搜索判斷每個(gè)騎士最短路徑遍歷所有騎士，完成？N存入數(shù)組mindistance（騎士最短路徑計(jì)算函數(shù)）（解題函數(shù)）4、各函數(shù)設(shè)計(jì)思想及偽代碼（1）主函數(shù)：對(duì)需要數(shù)據(jù)

7、進(jìn)行輸入，處理int main() 輸入國(guó)王坐標(biāo)； 處理坐標(biāo)； /數(shù)組下標(biāo)與實(shí)際坐標(biāo)相差一位ASC碼； 輸入騎士個(gè)數(shù); for（int i=0;i<騎士數(shù);i+） 輸入騎士坐標(biāo)； 處理坐標(biāo)； 調(diào)用解題函數(shù)solve；（2）解題函數(shù)：已知騎士路徑，分別判斷國(guó)王與騎士重合時(shí)路徑和不重合時(shí)路徑，找出最少步數(shù)void solve() 定義i，j，k，l； /分別代表起始點(diǎn)坐標(biāo)和目標(biāo)點(diǎn)坐標(biāo) 調(diào)用計(jì)算騎士最少步數(shù)的函數(shù)knightmindis； 遍歷所有點(diǎn)至所有點(diǎn)，找出國(guó)王與騎士最少步數(shù)之和； 計(jì)算在國(guó)王與騎士在不重合情況下的最少步數(shù)； 計(jì)算國(guó)王與騎士在重合情況下的最少步數(shù)； 比較上面兩種情況的結(jié)果

8、，得出答案；（3）計(jì)算所有點(diǎn)騎士最少步數(shù)的函數(shù)：所有騎士最少步數(shù)之和void knightmindis() 定義i，j，k，l； /分別代表起始點(diǎn)坐標(biāo)和目標(biāo)點(diǎn)坐標(biāo) 初始化數(shù)組mindistance8888； 遍歷所有點(diǎn)，調(diào)用騎士最小步數(shù)計(jì)算函數(shù)BFS（4）計(jì)算某兩點(diǎn)間出發(fā)到某點(diǎn)騎士的最少步數(shù)的函數(shù)：使用廣度優(yōu)先搜索找尋起始點(diǎn)與目標(biāo)點(diǎn)之間的最短路徑void BFS(int x,int y) struct Pos queue1000; /存放騎士移動(dòng)后坐標(biāo) int moveway82=1,2,2,1,1,-2,2,-1,-1,2,-1,-2,-2,1,-2,-1; /騎士移動(dòng)路徑 參考書本上廣度優(yōu)

9、先搜索算法設(shè)計(jì)算法，找出最短路徑；六、上機(jī)調(diào)試情況及分析1、設(shè)計(jì)騎士最短路徑計(jì)算函數(shù)時(shí)的問題由于每個(gè)點(diǎn)可以有8個(gè)不同方向的走法（超出棋盤范圍忽略），要找其最短路徑必須分布搜索，首先考慮了弗洛伊的算法求解最短路徑，但因結(jié)點(diǎn)數(shù)較多，算法時(shí)間復(fù)雜度較大，經(jīng)過驗(yàn)證比較，最終采用廣度優(yōu)先搜索BFS算法。該算法主要根據(jù)圖的廣度優(yōu)先搜索進(jìn)行改寫，使用循環(huán)隊(duì)列存儲(chǔ)數(shù)據(jù)。設(shè)計(jì)廣度優(yōu)先算法時(shí)，雖然理論上每個(gè)結(jié)點(diǎn)有8中不同的移動(dòng)方式，但考慮到棋盤范圍有限，必須在移動(dòng)式作出判斷，防止越界。 for(i=0;i<8;i+) fx=nx+movewayi0; fy=ny+movewayi1; if(fx<8

10、&& fx>=0 && fy<8 && fy>=0) /判斷，防止越界，離開棋盤 if(mindistancexyfxfy>steps) mindistancexyfxfy=steps; queuefront.x=fx+steps*100; queuefront.y=fy; front+; 2、輸入坐標(biāo)以字符形式輸入，由于回車鍵也被識(shí)別為一個(gè)字符，故輸入算法中應(yīng)該增加一位吸收回車鍵，否則輸入錯(cuò)誤 for(i=0;i<knights;i+)printf("請(qǐng)輸入第%d個(gè)騎士的坐標(biāo)：",i+1);sc

11、anf("%c%c",&inputknightj,&inputknightj+1); getchar(); /吸收回車字符 knighti.x=inputknightj-'A' /輸入數(shù)據(jù)處理 knighti.y=inputknightj+1-'1' j=j+2;3、設(shè)計(jì)算法，比較國(guó)王與騎士如果有重合時(shí)的最短路徑和不重合時(shí)的最短路徑之間的差別，用差值法可以減少算法的時(shí)間復(fù)雜度 for(m=0;m<knights;m+) /org是國(guó)王與騎士不重合時(shí)的步數(shù) org=abs(king.x-i)+abs(king.y-j)+m

12、indistanceknightm.xknightm.yij; changed=abs(king.x-k)+abs(king.y-l)+mindistanceknightm.xknightm.ykl + mindistanceklij; /changed表示重合時(shí)需要的步數(shù) if(org-changed>subsmax) subsmax=org-changed; /org-changed表示可以減少的步數(shù)七、測(cè)試用例、結(jié)果及其算法性能分析1、測(cè)試用例及結(jié)果2、算法性能分析（1）空間性能分析struct Pos int x,y; ;struct Pos king,knight63; int

13、 mindistance8888; int knights; int mindist=32767; Pos類型的數(shù)據(jù)，每個(gè)元素包含2個(gè)int型變量，每個(gè)int類型元素占2個(gè)字節(jié)，所以以上定義所占用總空間為：2*2+63*2*2+8*8*8*8*2+2+2=8 452字節(jié)另外，處理數(shù)據(jù)過程中，還設(shè)置了一些臨時(shí)變量，由于可以重復(fù)使用，使用結(jié)束時(shí)可以釋放，在此不做計(jì)算。（2）時(shí)間性能分析： 設(shè)騎士個(gè)數(shù)knights = n，則： 主函數(shù)中輸入騎士坐標(biāo)時(shí)有循環(huán)語句： for(i=0;i<knights;i+) printf("請(qǐng)輸入第%d個(gè)騎士的坐標(biāo)：",i+1); scan

14、f("%c%c",&inputknightj,&inputknightj+1); getchar(); /吸收回車字符 knighti.x=inputknightj-'A' /輸入數(shù)據(jù)處理 knighti.y=inputknightj+1-'1' j=j+2; 時(shí)間復(fù)雜度O（n）= n ； 解題函數(shù)中由于便利循環(huán)的循環(huán)次數(shù)固定，故不計(jì)入時(shí)間復(fù)雜度計(jì)算，經(jīng)計(jì)算如下語句：for(m=0;m<knights;m+) /至每一點(diǎn)騎士最短步數(shù) nowdist+=mindistanceknightm.xknightm.yij; su

15、bsmax=0; or(m=0;m<knights;m+) org=abs(king.x-i)+abs(king.y-j)+mindistanceknightm.xknightm.yij; changed=abs(king.x-k)+abs(king.y-l)+mindistanceknightm.xknightm.ykl +mindistanceklij; if(org-changed>subsmax) subsmax=org-changed; 時(shí)間復(fù)雜度O（n）= n ； 騎士最短路徑計(jì)算函數(shù)中，主要參考了書本上有關(guān)廣度優(yōu)先搜索的算法，循環(huán)語句如下； while(front!=

16、rear) steps=queuerear.x/100; nx=queuerear.x%100; ny=queuerear.y; rear+; steps+; for(i=0;i<8;i+) fx=nx+movewayi0; fy=ny+movewayi1; if(fx<8 && fx>=0 && fy<8 && fy>=0) if(mindistancexyfxfy>steps) mindistancexyfxfy=steps; queuefront.x=fx+steps*100; queuefront.y=

17、fy; front+; 時(shí)間復(fù)雜度等同于廣度優(yōu)先，O（n）= n2 。八、用戶使用說明1、打開程序，運(yùn)行cpp.exe；2、輸入國(guó)王坐標(biāo)，兩個(gè)字符，橫坐標(biāo)為AH，縱坐標(biāo)為18；3、輸入騎士個(gè)數(shù)；4、分別輸入每個(gè)騎士的坐標(biāo)；5、回車確認(rèn)，得出答案。九、參考文獻(xiàn)1 王昆侖、李紅，數(shù)據(jù)結(jié)構(gòu)與算法，北京，中國(guó)鐵道出版社，20102 何欽銘、顏輝，C語言程序設(shè)計(jì)，北京，高等教育出版社，20093 鄭莉、董淵、張瑞豐，C+語言程序設(shè)計(jì)，北京，清華大學(xué)出版社,，20044 m/p-25225716.html5 附錄（完整源程序）#include<stdio.h>#include<math.

18、h>struct Pos /定義數(shù)據(jù)類型int x,y; /x、y分別表示橫縱坐標(biāo);struct Pos king,knight63; /定義國(guó)王，騎士int mindistance8888; /任意兩點(diǎn)之間騎士的最少步數(shù)int knights; /騎士個(gè)數(shù)int mindist=32767; /最少步數(shù)/計(jì)算從 (x,y) 出發(fā)到某點(diǎn)騎士的最少步數(shù)/廣度優(yōu)先搜索BFS算法void BFS(int x,int y) struct Pos queue1000; /存放騎士移動(dòng)后坐標(biāo) int moveway82=1,2,2,1,1,-2,2,-1,-1,2,-1,-2,-2,1,-2,-1;

19、/騎士移動(dòng)路徑 int i,front=0,rear=0,nx,ny,steps=0,fx,fy; /廣度優(yōu)先搜索 mindistancexyxy=steps; queuefront.x=x+steps*100,queuefront.y=y,front+; while(front!=rear) steps=queuerear.x/100; nx=queuerear.x%100; ny=queuerear.y; rear+; steps+; for(i=0;i<8;i+) fx=nx+movewayi0; fy=ny+movewayi1; if(fx<8 && fx&

20、gt;=0 && fy<8 && fy>=0) /防止走出棋盤 if(mindistancexyfxfy>steps) mindistancexyfxfy=steps; queuefront.x=fx+steps*100; /入隊(duì) queuefront.y=fy; front+; /計(jì)算所有點(diǎn)騎士最少步數(shù)void knightmindis() int i,j,k,l; for(i=0;i<8;i+) /初始化數(shù)組 for(j=0;j<8;j+) for(k=0;k<8;k+) for(l=0;l<8;l+) mindis

21、tanceijkl=50; for(i=0;i<8;i+) for(j=0;j<8;j+) BFS(i,j);/i,j表示起始點(diǎn)/k,l表示某一騎士與國(guó)王會(huì)合時(shí)位置/nowdis表示目前的步數(shù)/subsmax為可以減少的步數(shù)中的最大值void solve() int i,j,k,l,m; int nowdist,subsmax; int org,changed; knightmindis(); for(i=0;i<8;i+) /遍歷所有點(diǎn)至所有點(diǎn) for(j=0;j<8;j+) for(k=0;k<8;k+) for(l=0;l<8;l+) nowdist=

22、abs(king.x-i)+abs(king.y-j); /至每一點(diǎn)國(guó)王最短步數(shù) for(m=0;m<knights;m+) /至每一點(diǎn)騎士最短步數(shù) nowdist+=mindistanceknightm.xknightm.yij; subsmax=0; for(m=0;m<knights;m+) /org是國(guó)王與騎士不重合時(shí)的步數(shù) org=abs(king.x-i)+abs(king.y-j)+mindistanceknightm.xknightm.yij; changed=abs(king.x-k)+abs(king.y-l)+mindistanceknightm.xknightm.ykl +mindistanceklij; /changed表示重合時(shí)需要的步數(shù) if(org-changed>subsmax) /判斷最大值 subsmax=org-changed; nowdist-=subsmax; /nowdist-subsmax代表從（i，j）到（k，l）的最短距離 if