數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)_馬踏棋盤.doc

學(xué) 號： 2012812044杭州師范大學(xué)錢江學(xué)院課 程 設(shè) 計(jì)題 目馬踏棋盤算法研究教 學(xué) 院信息與機(jī)電工程分院專 業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班 級計(jì)算機(jī)1201姓 名吳秋浩指導(dǎo)教師王李冬2013年12月21日目 錄一概述2二總體方案設(shè)計(jì)3三詳細(xì)設(shè)計(jì)4四最終輸出5五課程設(shè)計(jì)總結(jié)6參考文獻(xiàn)7一 概述1. 課程設(shè)計(jì)的目的（1） 課題描述設(shè)計(jì)一個(gè)國際象棋的馬踏遍棋盤的演示程序。（2） 課題意義通過“馬踏棋盤”算法的研究，強(qiáng)化了個(gè)人對“?！睌?shù)據(jù)結(jié)構(gòu)的定義和運(yùn)用，同時(shí)也鍛煉了自身的C語言編程能力。另一方面，通過對“馬踏棋盤”算法的研究，個(gè)人對“迷宮”、“棋盤遍歷”一類的問題，有了深刻的認(rèn)識，為今后解決以此問題為基礎(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ì)過程中，難免會(huì)遇到困難，但是不能輕易放棄，要肯花時(shí)間，能靜得下心，積極查閱相關(guān)資料，積極與指導(dǎo)老師溝通。2. 課程設(shè)計(jì)的要求（1） 課題設(shè)計(jì)要求將馬隨機(jī)放在國際象棋的88棋盤Board0707的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)方格只進(jìn)入一次，走遍棋盤上全部64個(gè)方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，64依次填入一個(gè)88的方陣，輸出之。程序由回溯法和貪心法實(shí)現(xiàn)，比較兩種算法的時(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，則找到可行方案，輸出之。反之，改變初始尋找方向繼續(xù)尋找，直到8種方向順序都試過，若還是沒有合適的方案，則說明以該起始點(diǎn)開始馬無法踏遍棋盤。二 總體方案設(shè)計(jì)1. 回溯法算法思想按深度優(yōu)先策略，從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試，也就是說每當(dāng)前進(jìn)的路不通，我們總是返回到前一次的岔路口，選擇下一條新的路線 。（1）函數(shù)頭文件定義和宏定義#include#include#define N 8 /便于改變棋盤大?。?）棧數(shù)據(jù)結(jié)構(gòu)定義typedef structint bN*N;/記錄每次走的方向int top;/棧指針SqStack;（3）定義探尋路徑函數(shù)BoardNN模擬N*N棋盤，填入1,2,364。x、y傳遞初始位置。bool HorsePath(int BoardN,int x,int y)/ 初始化棧/定義方向數(shù)組/int xx8=1,2,2,1,-1,-2,-2,-1;/int yy8=2,1,-1,-2,-2,-1,1,2;/初始方向下表入棧/回溯法開始尋找合適方案（詳見“詳細(xì)設(shè)計(jì)”）（4）定義主函數(shù)void main()/定義基本變量及BoardNN數(shù)組/輸入初始位置x0，y0/調(diào)用HorsePath（Board,x0,y0）;/輸出方案2. 貪心法算法思想從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。該算法存在問題：1. 不能保證求得的最后解是最佳的；2. 不能用來求最大或最小解問題；3. 只能求滿足某些約束條件的可行解的范圍。（1）函數(shù)頭文件定義和宏定義#include#define N 8/便于改變棋盤大?。?）程序要用到的一些全局變量的定義int xx8=1,2,2,1,-1,-2,-2,-1;int yy8=2,1,-1,-2,-2,-1,1,2;/控制馬能走的8個(gè)方向int BoardNN=0;/初始棋盤所有位置可走(3)定義FeassiblePath /計(jì)算每個(gè)點(diǎn)的后續(xù)著點(diǎn)個(gè)數(shù)int FeassiblePath(int x,int y,int start)/函數(shù)體(詳見“詳細(xì)設(shè)計(jì)”)(4)定義NextPath/*找出一個(gè)著點(diǎn)的后續(xù)著點(diǎn)中可走方位最少的，把著點(diǎn)到后續(xù)點(diǎn)的方向記下返回主函數(shù)*/int NextPath(int x,int y,int start)/函數(shù)體(詳見“詳細(xì)設(shè)計(jì)”)(5)定義主函數(shù)void main()/輸入初始位置x0，y0/定義變量整型變量start控制起始8種方向While(start8)/循環(huán)調(diào)用NextPath（x0,y0,start）/找到方案，則輸出之start+;三 詳細(xì)設(shè)計(jì)1.回溯法“馬踏棋盤”演示程序#include#include#define N 8typedef structint bN*N;/記錄每次走的方向int top;SqStack;bool HorsePath(int BoardN,int x,int y)SqStack *s;s=(SqStack*)malloc(sizeof(SqStack);/初始化棧s-top=-1;int xx8=1,2,2,1,-1,-2,-2,-1;int yy8=2,1,-1,-2,-2,-1,1,2;/控制馬能走的8個(gè)方向int p=0;s-top+;s-bs-top=p;while(s-top-1)Boardxy=s-top+1;/找到方案，則輸出之if(Boardxy=N*N)return true;while(p=0&(x+xxp)=0&(y+yyp)top+;s-bs-top=p;p=0;break;p+;if(p=8)Boardxy=0;x-=xxs-bs-top;y-=yys-bs-top;p=s-bs-top+1;s-top-;return false;/循環(huán)結(jié)束，未找到合適方案void main()bool flag;int x0,y0,i,j;int BoardNN=0;/設(shè)置開始每一格都可走printf(請輸入馬的起始位置x,yn注：(0=x%d,0=y%d)：,N,N);while(scanf(%d,%d,&x0,&y0)if(x0=N|y0=N)printf(位置輸入有誤，請重新輸入：);elsebreak;flag=HorsePath(Board,x0,y0);if(flag=false)printf(無法遍歷！n);elseprintf(一種可行的方案為：n);for(i=0;iN;i+)for(j=0;jN;j+)printf(t%d,Boardij);printf(nn);z2.貪心法“馬踏棋盤”演示程序#include#define N 8int xx8=1,2,2,1,-1,-2,-2,-1;int yy8=2,1,-1,-2,-2,-1,1,2;/控制馬能走的8個(gè)方向int BoardNN=0;/初始棋盤所有位置可走/計(jì)算每個(gè)點(diǎn)的后續(xù)著點(diǎn)個(gè)數(shù)int FeassiblePath(int x,int y,int start)int count=0,i=0,p,k;k=start;while(i=0&x+xxk%8=0&y+yyk%8N)count+;k+;i+;return count;/找出一個(gè)著點(diǎn)的后續(xù)著點(diǎn)中可走方位最少的，把著點(diǎn)到后續(xù)著點(diǎn)的方向記下返回主函數(shù)int NextPath(int x,int y,int start)int min=9,i=0,num,p,k,f;k=start;while(i=0&x+xxk%8=0&y+yyk%8num)min=num;f=k%8;k+;i+;if(min=9)return -1;return f; /后續(xù)著點(diǎn)的方向記下返回主函數(shù)void main()int i,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=N|y0=N)printf(位置輸入有誤，請重新輸入：);elsebreak;Boardx0y0=1;while(start8)/如果一種起始方位無法遍歷，改變方位，再次尋找i=x0;j=y0;for(int step=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;iN;i+)printf(t);for(j=0;jtop-1）循環(huán)，同時(shí)這個(gè)循環(huán)內(nèi)部還有一個(gè)while（p8）的循環(huán)，由回溯算法的思想，我們可知這個(gè)外循環(huán)的時(shí)間復(fù)雜度相當(dāng)大，故整個(gè)程序的時(shí)間復(fù)雜度也很大，如果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é)果（2）貪心法求解的時(shí)間復(fù)雜度分析設(shè)問題的規(guī)模為n，即棋盤的的大小為n*n。由貪婪算法可知選擇下一出口的貪婪標(biāo)準(zhǔn)是在那些允許走的位置中，選擇出口最少的那個(gè)位置。顯然，影響程序運(yùn)行時(shí)間的基本運(yùn)算是在尋找出口最少的位置。由程序我們可知T(n)= O(n2)。顯然貪心算法的時(shí)間復(fù)雜度小多了，即使棋盤的大小是8*8，想要搜索任意起始點(diǎn)下的可行方案，一秒鐘內(nèi)就可以輸出結(jié)果。（3）回溯法和貪心法的比較回溯法求解馬踏棋盤，思想簡單易懂，能夠一次性得到所有可能的情況，但是算法時(shí)間復(fù)雜度過大，在棋盤大小過大時(shí)，不推薦采用。貪心法，思想也是比較容易讓人理解的，同時(shí)，算法的時(shí)間復(fù)雜度為O(n2),能夠較快地找出一種復(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)化的算法存在，為了較快得到實(shí)驗(yàn)結(jié)果，我又開始在網(wǎng)上搜索，然后我得知了利用貪心法能夠大大提高程序運(yùn)行的效率，因?yàn)樵撍惴ㄟx擇下一出口的貪婪標(biāo)準(zhǔn)是在那些允許走的位置中，選擇出口最少的那個(gè)位置。直到?jīng)]有下一著點(diǎn)位置。于是，我又用貪心法實(shí)現(xiàn)了“馬踏棋盤”演示程序。在此次課程設(shè)計(jì)中我一直想嘗試一次輸出所有的“馬踏棋盤”方案，并記錄方案的個(gè)數(shù)。雖然用回溯法實(shí)現(xiàn)了對5*5等小規(guī)模棋盤，馬踏遍棋盤所有方案的輸出，但是對于8*8的棋盤，問題規(guī)模過大，無法在短時(shí)間內(nèi)得到所有的方案。我也曾想過用貪心法實(shí)現(xiàn)“馬踏棋盤”所有方案的一次性輸出，但是我覺得如果要用貪心法得到“馬踏棋盤”所有方案，需要循環(huán)對每一著點(diǎn)的后繼可行著點(diǎn)進(jìn)行嘗試遍歷。這樣就違背了貪心法“選擇下一出口的貪婪標(biāo)準(zhǔn)是在那些允許走的位置中，選擇出口最少的那個(gè)位置”這一標(biāo)準(zhǔn)，這樣做就會(huì)失去貪心法本身的優(yōu)點(diǎn)，反而使