數(shù)據(jù)結構課程設計-馬踏棋盤分解演示教學

1、學號：2012812044杭州師范大學課題目教學院專業(yè)班級姓名指導教師U十1兀程設計馬踏棋盤算法研究信息與機電工程分院計算機科學與技術計算機1201吳秋浩王李冬/BJrIf人2013年12月21日1 .概述32 .總體方案設計33 .詳名田設計44 .最終輸出6五課程設計總結10參考文獻13概述1 .課程設計的目的(1)課題描述設計一個國際象棋的馬踏遍棋盤的演示程序。(2)課題意義通過“馬踏棋盤”算法的研究，強化了個人對“?！睌?shù)據(jù)結構的定義和運用，同時也鍛煉了自身的C語言編程能力。另一方面，通過對“馬踏棋盤”算法的研究，個人對“迷宮”、“棋盤遍歷”一類的問題，有了深刻的認識，為今后解決以此問題

2、為基礎的相關的問題，打下了堅實的基礎。(3)解決問題的關鍵點說明解決問題的關鍵首先要熟練掌握C語言編程技術，同時能夠熟練運用“棧”數(shù)據(jù)結構。另外，態(tài)度也是非常重要的。在課程設計過程中，難免會遇到困難，但是不能輕易放棄，要肯花時間，能靜得下心，積極查閱相關資料，積極與指導老師溝通。2 .課程設計的要求(1)課題設計要求將馬隨機放在國際象棋的8X8棋盤Board0707的某個方格中，馬按走棋規(guī)則進行移動。要求每個方格只進入一次，走遍棋盤上全部64個方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1,2,，64依次填入一個8X8的方陣，輸出之。程序由回溯法和貪心法實現(xiàn)，比較兩種算法

3、的時間復雜度。(2)課題設計的思路首先，搞清楚馬每次在棋盤上有8個方向可走，定義兩個一位數(shù)組，來存儲馬下一著點的水平和縱向偏移量。程序再定義一個8*8二維數(shù)組，初始所有元素置0,起始點元素置1。若為回溯法,初始方向數(shù)據(jù)(一維數(shù)組下標)入棧。隨后，馬從起始點開始，每次首先尋找下一可行的著點，然后記下方向，方向數(shù)據(jù)入棧，把該位置元素置為合適的序列號，若無下一可行著點，則回溯，尋找下一方向位置著點，以此類推，直到64填入數(shù)組中，則輸出二維數(shù)組，即為馬可走的方案。若為貪婪法，選擇下一出口的貪婪標準是在那些允許走的位置中，選擇出口最少的那個位置。直到?jīng)]有下一著點位置，若此時已標記到64,則找到可行方案，

4、輸出之。反之，改變初始尋找方向繼續(xù)尋找，直到8種方向順序都試過，若還是沒有合適的方案，則說明以該起始點開始馬無法踏遍棋盤。二總體方案設計1 .回溯法算法思想按深度優(yōu)先策略，從一條路往前走，能進則進，不能進則退回來，換一條路再試，也就是說每當前進的路不通，我們總是返回到前一次的岔路口，選擇下一條新的路線。(1)函數(shù)頭文件定義和宏定義#include<stdio.h>#include<stdlib.h>#defineN8/便于改變棋盤大小(2)棧數(shù)據(jù)結構定義typedefstructintbN*N;/記錄每次走的方向inttop;/棧指針SqStack;(3)定義探尋路徑函

5、數(shù)BoardNN模擬N*N棋盤，填入1,2,364。x、y傳遞初始位置。boolHorsePath(intBoardN,intx,inty)/初始化棧/定義方向數(shù)組/intxx8=1,2,2,1,-1,-2,-2,-1;/intyy8=2,1,-1,-2,-2,-1,1,2;/初始方向下表入棧/回溯法開始尋找合適方案(詳見“詳細設計”)(4)定義主函數(shù)voidmain()/定義基本變量及BoardNN數(shù)組/輸入初始位置x0,y0/調(diào)用HorsePath(Board,x0,y0);/輸出方案2,貪心法算法思想從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某算法中的

6、某一步不能再繼續(xù)前進時，算法停止。該算法存在問題：1,不能保證求得的最后解是最佳的；2,不能用來求最大或最小解問題；3,只能求滿足某些約束條件的可行解的范圍。(1)函數(shù)頭文件定義和宏定義/便于改變棋盤大小控制馬能走的8個方向/初始棋盤所有位置可走/計算每個點的后續(xù)著點個數(shù)#include<stdio.h>#defineN8(2)程序要用到的一些全局變量的定義intxx8=1,2,2,1,-1,-2,-2,-1);intyy8=2,1,-1,-2,-2,-1.1.2);/intBoardNN=0;(3)定義FeassiblePathintFeassiblePath(intx,inty

7、,intstart)/函數(shù)體(詳見“詳細設計”)(4)定義NextPath/*找出一個著點的后續(xù)著點中可走方位最少的，把著點到后續(xù)點的方向記下返回主函數(shù)*/intNextPath(intx,inty,intstart)/函數(shù)體(詳見“詳細設計”)(5)定義主函數(shù)voidmain()/輸入初始位置x0,y0/定義變量整型變量start控制起始8種方向While(start<8)/循環(huán)調(diào)用NextPath(x0,y0,start)/找到方案，則輸出之start+;三詳細設計1.回溯法“馬踏棋盤”演示程序#include<stdio.h>#include<stdlib.h&g

8、t;#defineN8typedefstructintbN*N;inttop;SqStack;/記錄每次走的方向boolHorsePath(intBoardN,intx,inty)SqStack*s;s=(SqStack*)malloc(sizeof(SqStack);s->top=-1;intxx8=1,2,2,1,-1,-2,-2,-1;intyy8=2,1,-1,-2,-2,-1,1,2;intp=0;s->top+;s->bs->top=p;while(s->top>-1)Boardxy=s->top+1;/找到方案，則輸出之if(Boardx

9、y=N*N)returntrue;while(p<8)/初始化棧控制馬能走的8個方向/如果下一格可走且不超出棋盤范圍if(Boardx+xxpy+yyp=0&&(x+xxp)>=0&&(x+xxp)<N)&&(y+yyp)>=0&&(y+yyp)<N)x+=xxp;y+=yyp;s->top+;s->bs->top=p;p=0;break;p+；if(p=8)Boardxy=0;x-=xxs->bs->top;y-=yys->bs->top;p=s->b

10、s->top+1;s->top-;)returnfalse;循環(huán)結束，未找到合適方案)voidmain()boolflag;intx0,y0,i,j;intBoardNN=0;/設置開始每一格都可走printf("請輸入馬的起始位置x,yn注：(0=<x<%d,0=<y<%d)",N,N);while(scanf("%d,%d",&x0,&y0)if(x0<0|x0>=N|y0<0|y0>=N)printf("位置輸入有誤，請重新輸入：");elsebreak

11、;flag=HorsePath(Board,x0,y0);if(flag=false)printf("無法遍歷！n");elseprintf("一種可行的方案為：n");for(i=0;i<N;i+)for(j=0;j<N;j+)printf("t%d",Boardij);printf("nn");z2 .貪心法“馬踏棋盤”演示程序#include<stdio.h>#defineN8intxx8=1,2,2,1,-1,-2,-2,-1;intyy8=2,1,-1,-2,-2,-1,1,2;i

12、ntBoardNN=0;/控制馬能走的8個方向/初始棋盤所有位置可走/計算每個點的后續(xù)著點個數(shù)intFeassiblePath(intx,inty,intstart)intcount=0,i=0,p,k;k=start;while(i<8)/若下一著點可走且沒有超出邊界if(Boardx+xxk%8y+yyk%8=0&&(x+xxk%8>=0&&x+xxk%8卜N)&&(y+yyk%8>=0&&y+yyk%8卜N)count+;k+;i+;returncount;/找出一個著點的后續(xù)著點中可走方位最少的，把著點到

13、后續(xù)著點的方向記下返回主函數(shù)intNextPath(intx,inty,intstart)intmin=9,i=0,num,p,k,f;k=start;while(i<8)/若下一著點可走且沒有超出邊界if(Boardx+xxk%8y+yyk%8=0&&(x+xxk%8>=0&&x+xxk%8卜N)&&(y+yyk%8>=0&&y+yyk%8卜N)num=FeassiblePath(x+xxk%8,y+yyk%8,start);if(min>num)min=num;f=k%8;k+;i+;if(min=9)

14、return-1;returnf;/后續(xù)著點的方向記下返回主函數(shù)voidmain()inti,j,x0,y0,start=0,flag,sign=0;printf("請輸入馬的起始位置x,yn注：(0=<x<%d,0=<y<%d)",N,N);while(scanf("%d,%d",&x0,&y0)if(x0<0|x0>=N|y0<0|y0>=N)printf("位置輸入有誤，請重新輸入：");elsebreak;)Boardx0y0=1;while(start<8

15、)/如果一種起始方位無法遍歷，改變方位，再次尋找i=x0;j=y0;for(intstep=2;step<=N*N;step+)flag=NextPath(i,j,start);if(flag!=-1)i+=xxflag;j+=yyflag;Boardij=step;)elsebreak;/若找到一種方案，則輸出之if(step=N*N+1)sign=1;printf("一種可行的方案為：n");for(i=0;i<N;i+)printf("t");for(j=0;j<N;j+)printf("%dt",Boardi

16、j);printf("nn");if(sign=1)break;start+;if(sign=0)printf("此起始點下無法遍歷，或許方案根本不存在！n試改變起始點尋找方案！n");四最終輸由1.回溯法(1)程序正確輸入下運行結果(2)回溯法求解的時間復雜度分析設問題的規(guī)模為n,即棋盤的的大小為n*n。則棋盤初始化的時間復雜度為O(M2),程序運行過程中，還有一個while(s->top>-1)循環(huán)，同時這個循環(huán)內(nèi)部還有一個while(p<8)的循環(huán)，由回溯算法的思想，我們可知這個外循環(huán)的時間復雜度相當大，故整個程序的時間復雜度也很

17、大，如果n個數(shù)比較小的時候或許能夠較快地顯示結果，但隨著問題規(guī)模的增大，當n=8時，T(n)簡直可以用天文數(shù)字來形容，在windows操作系統(tǒng)下，有時候要等幾十分鐘，甚至更久才能出結果。顯然，我們得追尋更優(yōu)化的算法。2,貪心法(1)程序正確輸入下運行結果continue請輸入馬的起站位置黃注：(0=<x<8,0=<y<8>：(2)貪心法求解的時間復雜度分析設問題的規(guī)模為n,即棋盤的的大小為n*n。由貪婪算法可知選擇下一出口的貪婪標準是在那些允許走的位置中，選擇出口最少的那個位置。顯然，影響程序運行時間的基本運算是在尋找出口最少的位置。由程序我們可知T(n)=O(n

18、A2)。顯然貪心算法的時間復雜度小多了，即使棋盤的大小是8*8,想要搜索任意起始點下的可行方案，一秒鐘內(nèi)就可以輸出結果。(3)回溯法和貪心法的比較回溯法求解馬踏棋盤，思想簡單易懂，能夠一次性得到所有可能的情況，但是算法時間復雜度過大，在棋盤大小過大時，不推薦采用。貪心法，思想也是比較容易讓人理解的，同時，算法的時間復雜度為O(nA2),能夠較快地找出一種復合要就的方案，但是利用貪心法不便于得到所有的可行方案。五課程設計總結此次數(shù)據(jù)結構課程設計的課題是設計一個國際象棋的馬踏遍棋盤的演示程序。在剛開始選課題時，我就被“馬踏棋盤”這幾個字深深地吸引了，雖然那是我第一次聽說這個名詞，但我還是選擇了“馬踏棋盤”。于是我便開始在網(wǎng)上搜集關于“馬踏棋盤”的內(nèi)容，然后我知道了“馬踏棋盤”算法的要求。由于在數(shù)據(jù)結構課上學習過利用棧來求解迷宮問題，所以第一時間我就想到了利用棧來求解這個問題，也就是利用回溯法求解。雖然很快我寫出了，回溯法求解的源程序，可是當我運行程序時，出現(xiàn)的現(xiàn)象使我很驚訝，對于一個8*8的棋盤，輸入不同的起始點，得到結果的時間不同，例如輸入（0,0）較快的得到了結果，但是輸入（1,1）我等了幾十分鐘，依舊沒有等到實驗結果的出現(xiàn)。這時，我開始思考，一定有更優(yōu)化的算法存在，為