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

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

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

4、輸出之。反之，改變初始尋找方向繼續(xù)尋找，直到8種方向順序都試過，若還是沒有合適的方案，則說明以該起始點(diǎn)開始馬無法踏遍棋盤。二總體方案設(shè)計(jì)1 .回溯法算法思想按深度優(yōu)先策略，從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試，也就是說每當(dāng)前進(jìn)的路不通，我們總是返回到前一次的岔路口，選擇下一條新的路線。(1)函數(shù)頭文件定義和宏定義#include<stdio.h>#include<stdlib.h>#defineN8/便于改變棋盤大小(2)棧數(shù)據(jù)結(jié)構(gòu)定義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;/初始方向下表入棧/回溯法開始尋找合適方案(詳見“詳細(xì)設(shè)計(jì)”)(4)定義主函數(shù)voidmain()/定義基本變量及BoardNN數(shù)組/輸入初始位置x0,y0/調(diào)用HorsePath(Board,x0,y0);/輸出方案2,貪心法算法思想從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的

6、某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。該算法存在問題：1,不能保證求得的最后解是最佳的；2,不能用來求最大或最小解問題；3,只能求滿足某些約束條件的可行解的范圍。(1)函數(shù)頭文件定義和宏定義/便于改變棋盤大小控制馬能走的8個(gè)方向/初始棋盤所有位置可走/計(jì)算每個(gè)點(diǎn)的后續(xù)著點(diǎn)個(gè)數(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ù)體(詳見“詳細(xì)設(shè)計(jì)”)(4)定義NextPath/*找出一個(gè)著點(diǎn)的后續(xù)著點(diǎn)中可走方位最少的，把著點(diǎn)到后續(xù)點(diǎn)的方向記下返回主函數(shù)*/intNextPath(intx,inty,intstart)/函數(shù)體(詳見“詳細(xì)設(shè)計(jì)”)(5)定義主函數(shù)voidmain()/輸入初始位置x0,y0/定義變量整型變量start控制起始8種方向While(start<8)/循環(huán)調(diào)用NextPath(x0,y0,start)/找到方案，則輸出之start+;三詳細(xì)設(shè)計(jì)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個(gè)方向/如果下一格可走且不超出棋盤范圍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)結(jié)束，未找到合適方案)voidmain()boolflag;intx0,y0,i,j;intBoardNN=0;/設(shè)置開始每一格都可走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個(gè)方向/初始棋盤所有位置可走/計(jì)算每個(gè)點(diǎn)的后續(xù)著點(diǎn)個(gè)數(shù)intFeassiblePath(intx,inty,intstart)intcount=0,i=0,p,k;k=start;while(i<8)/若下一著點(diǎn)可走且沒有超出邊界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;/找出一個(gè)著點(diǎn)的后續(xù)著點(diǎn)中可走方位最少的，把著點(diǎn)到

13、后續(xù)著點(diǎn)的方向記下返回主函數(shù)intNextPath(intx,inty,intstart)intmin=9,i=0,num,p,k,f;k=start;while(i<8)/若下一著點(diǎn)可走且沒有超出邊界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ù)著點(diǎn)的方向記下返回主函數(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("此起始點(diǎn)下無法遍歷，或許方案根本不存在！n試改變起始點(diǎn)尋找方案！n");四最終輸由1.回溯法(1)程序正確輸入下運(yùn)行結(jié)果(2)回溯法求解的時(shí)間復(fù)雜度分析設(shè)問題的規(guī)模為n,即棋盤的的大小為n*n。則棋盤初始化的時(shí)間復(fù)雜度為O(M2),程序運(yùn)行過程中，還有一個(gè)while(s->top>-1)循環(huán)，同時(shí)這個(gè)循環(huán)內(nèi)部還有一個(gè)while(p<8)的循環(huán)，由回溯算法的思想，我們可知這個(gè)外循環(huán)的時(shí)間復(fù)雜度相當(dāng)大，故整個(gè)程序的時(shí)間復(fù)雜度也很

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

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