數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-馬踏棋盤分解演示教學(xué)

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

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

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

4、輸出之。反之，改變初始尋找方向繼續(xù)尋找，直到8種方向順序都試過，若還是沒有合適的方案，則說明以該起始點開始馬無法踏遍棋盤。二總體方案設(shè)計1 .回溯法算法思想按深度優(yōu)先策略，從一條路往前走，能進則進，不能進則退回來，換一條路再試，也就是說每當前進的路不通，我們總是返回到前一次的岔路口，選擇下一條新的路線。(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;/初始方向下表入棧/回溯法開始尋找合適方案(詳見“詳細設(shè)計”)(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ù)體(詳見“詳細設(shè)計”)(4)定義NextPath/*找出一個著點的后續(xù)著點中可走方位最少的，把著點到后續(xù)點的方向記下返回主函數(shù)*/intNextPath(intx,inty,intstart)/函數(shù)體(詳見“詳細設(shè)計”)(5)定義主函數(shù)voidmain()/輸入初始位置x0,y0/定義變量整型變量start控制起始8種方向While(start<8)/循環(huán)調(diào)用NextPath(x0,y0,start)/找到方案，則輸出之start+;三詳細設(shè)計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)/初始化?？刂岂R能走的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)結(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個方向/初始棋盤所有位置可走/計算每個點的后續(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)程序正確輸入下運行結(jié)果(2)回溯法求解的時間復(fù)雜度分析設(shè)問題的規(guī)模為n,即棋盤的的大小為n*n。則棋盤初始化的時間復(fù)雜度為O(M2),程序運行過程中，還有一個while(s->top>-1)循環(huán)，同時這個循環(huán)內(nèi)部還有一個while(p<8)的循環(huán)，由回溯算法的思想，我們可知這個外循環(huán)的時間復(fù)雜度相當大，故整個程序的時間復(fù)雜度也很

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

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