馬的hamilton周游問題算法設(shè)計課程設(shè)計

1、<p>　　課 程 設(shè) 計 任 務(wù) 書</p><p>　　課程名稱 軟件專題訓(xùn)練 </p><p>　　題 目 ＿＿馬的Hamilton周游路線問題＿＿</p><p><b>　　目錄</b></p><p><b>　　一設(shè)計分析1</b><

2、/p><p>　　1.1 課程設(shè)計題目1</p><p>　　1.2 課程設(shè)計任務(wù)及要求1</p><p>　　1.3 軟硬件運行環(huán)境及開發(fā)工具1</p><p><b>　　二程序結(jié)構(gòu)2</b></p><p><b>　　2.1 流程圖2</b></p>

3、;<p>　　2.2各模塊的功能及程序說明2</p><p><b>　　三源程序3</b></p><p><b>　　3.1源代碼3</b></p><p><b>　　3.2操作方法4</b></p><p><b>　　四試驗結(jié)果7

4、</b></p><p><b>　　五設(shè)計體會8</b></p><p>　　一 設(shè)計分析</p><p><b>　　1.1課程設(shè)計題目</b></p><p>　　馬的Hamilton周游路線問題</p><p>　　1.2 課程設(shè)計任務(wù)及

5、要求</p><p>　　1．確定能對給定的偶數(shù)m,n≥6，且|m-n|≤2，編程計算m╳n的國際象棋棋盤上馬的一條Hamilton周游路線；</p><p>　　2．程序能夠演示一條Hamilton周游路線的周游過程等</p><p>　　1.3 軟硬件運行環(huán)境及開發(fā)工具</p><p>　　1. PC兼容機 &l

6、t;/p><p>　　2．Windows 2000/XP操作系統(tǒng)</p><p>　　3．TC集成開發(fā)環(huán)境或其他C語言開發(fā)環(huán)境</p><p><b>　　二 程序結(jié)構(gòu)</b></p><p><b>　　2.1 流程圖</b></p><p>　　2.2各模塊的功能及程序

7、說明</p><p>　　void step(int m,int n,grid b[])</p><p>　　作用：將讀入的基礎(chǔ)棋盤的Hamilton回路轉(zhuǎn)化為網(wǎng)格數(shù)據(jù)</p><p>　　void input()</p><p><b>　　作用：讀入初始數(shù)據(jù)</b></p><p>　　int

8、 pos(int x,int y,int col)</p><p>　　作用：計算棋盤方格的編號。</p><p>　　void build(int m,int n,int offx,int offy,int col,grid b[])</p><p>　　作用：構(gòu)造結(jié)構(gòu)化Hamilton回路。</p><p>　　void Base(int

9、 mm,int nn,int offx,int offy)</p><p>　　作用：根據(jù)基礎(chǔ)解構(gòu)造子棋盤的結(jié)構(gòu)化Hamilton回路。</p><p>　　bool comp(int mm,int nn,int offx,int offy)</p><p><b>　　作用：分治法主體。</b></p><p>　　v

10、oid output()</p><p><b>　　作用：輸出路線。</b></p><p>　　三 源程序 </p><p><b>　　3.1源代碼</b></p><p>　　#include<stdio.h></p><p>　　#

11、include<stdlib.h></p><p>　　#include<memory.h></p><p>　　#define M 2048</p><p><b>　　int m,n;</b></p><p>　　FILE *fin;</p><p>　　typedef

12、 struct</p><p><b>　　{</b></p><p><b>　　int x,y;</b></p><p><b>　　}grid;</b></p><p>　　grid b66[36],b68[48],b86[48],b88[64],b810[80],b10

13、8[80],b1010[100],b1012[120],b1210[120];</p><p>　　grid link[500][500];</p><p>　　int a[10][12];</p><p>　　void step(int m,int n,grid b[])</p><p><b>　　{</b><

14、/p><p>　　int i,j,k=m*n,p;</p><p><b>　　if(m<n)</b></p><p><b>　　{</b></p><p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<n;j++)</p

15、><p><b>　　{</b></p><p>　　p=a[i][j]-1;</p><p><b>　　b[p].x=i;</b></p><p><b>　　b[p].y=j;</b></p><p><b>　　}</b><

16、;/p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<n;j++)</p&

17、gt;<p><b>　　{</b></p><p>　　p=a[j][i]-1;</p><p><b>　　b[p].x=i;</b></p><p><b>　　b[p].y=j;</b></p><p><b>　　}</b><

18、/p><p><b>　　}</b></p><p><b>　　} </b></p><p>　　void input()</p><p><b>　　{</b></p><p>　　printf("請輸入棋盤規(guī)格（格式為m,n,例如：6

19、，6）");</p><p>　　scanf("%d%d",&m,&n); </p><p>　　fin=fopen("infoundation","r");</p><p><b>　　int i,j;</b></p><p>　　f

20、or(i=0;i<6;i++)//讀入m，n的基本的回路</p><p>　　for(j=0;j<6;j++)</p><p>　　fscanf(fin,"%d",&a[i][j]);</p><p>　　step(6,6,b66);</p><p>　　for(i=0;i<6;i++)</

21、p><p>　　for(j=0;j<8;j++)</p><p>　　fscanf(fin,"%d",&a[i][j]);</p><p>　　step(6,8,b68);</p><p>　　step(8,6,b86);</p><p>　　for(i=0;i<8;i++)<

22、/p><p>　　for(j=0;j<8;j++)</p><p>　　fscanf(fin,"%d",&a[i][j]);</p><p>　　step(8,8,b88);</p><p>　　for(i=0;i<8;i++)</p><p>　　for(j=0;j<10;j

23、++)</p><p>　　fscanf(fin,"%d",&a[i][j]);</p><p>　　step(8,10,b810);</p><p>　　step(10,8,b108);</p><p>　　for(i=0;i<10;i++)</p><p>　　for(j=0;j&

24、lt;10;j++)</p><p>　　fscanf(fin,"%d",&a[i][j]);</p><p>　　step(10,10,b1010);</p><p>　　for(i=0;i<10;i++)</p><p>　　for(j=0;j<12;j++)</p><p>

25、;　　fscanf(fin,"%d",&a[i][j]);</p><p>　　step(10,12,b1012);</p><p>　　step(12,10,b1210);</p><p><b>　　}</b></p><p>　　int pos(int x,int y,int col)&

26、lt;/p><p><b>　　{</b></p><p>　　return col*x+y;</p><p><b>　　} </b></p><p>　　void build(int m,int n,int offx,int offy,int col,grid b[])</p>

27、<p><b>　　{</b></p><p>　　int i,p,q,k=m*n,x1,x2,y1,y2;</p><p>　　for(i=0;i<k;i++)</p><p><b>　　{</b></p><p>　　x1=offx+b[i].x;</p>&l

28、t;p>　　y1=offy+b[i].y;</p><p>　　x2=offx+b[(i+1)%k].x;</p><p>　　y2=offy+b[(i+1)%k].y;</p><p>　　p=pos(x1,y1,col);</p><p>　　q=pos(x2,y2,col);</p><p>　　link[

29、x1][y1].x=q;</p><p>　　link[x2][y2].y=p;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void Base(int mm,int nn,int offx,int offy)</p><p

30、><b>　　{</b></p><p>　　if(mm==6&&nn==6)build(mm,nn,offx,offy,n,b66);</p><p>　　else if(mm==6&&nn==8)build(mm,nn,offx,offy,n,b68);</p><p>　　else if(mm==8&

31、amp;&nn==6)build(mm,nn,offx,offy,n,b86);</p><p>　　else if(mm==8&&nn==8)build(mm,nn,offx,offy,n,b88);</p><p>　　else if(mm==8&&nn==10)build(mm,nn,offx,offy,n,b810);</p>

32、<p>　　else if(mm==10&&nn==8)build(mm,nn,offx,offy,n,b108);</p><p>　　else if(mm==10&&nn==10)build(mm,nn,offx,offy,n,b1010);</p><p>　　else if(mm==10&&nn==12)build(mm,n

33、n,offx,offy,n,b1012);</p><p>　　else if(mm==12&&nn==10)build(mm,nn,offx,offy,n,b1210);</p><p><b>　　}</b></p><p>　　bool comp(int mm,int nn,int offx,int offy)</p

34、><p><b>　　{</b></p><p>　　int mm1,mm2,nn1,nn2,i,j1,j2;</p><p>　　int x[8],y[8],p[8];</p><p>　　if(mm%2||nn%2||mm-nn>2||nn-mm>2||mm<6||nn<6)</p>

35、<p>　　return true;</p><p>　　if(mm<12||nn<12)</p><p><b>　　{</b></p><p>　　Base(mm,nn,offx,offy);</p><p>　　return false;</p><p><b&

36、gt;　　}</b></p><p><b>　　mm1=mm/2;</b></p><p>　　if(mm%4>0)mm1--;</p><p>　　mm2=mm-mm1;</p><p><b>　　nn1=nn/2;</b></p><p>　　if(

37、nn%4>0)nn1--;</p><p>　　nn2=nn-nn1;</p><p>　　comp(mm1,nn1,offx,offy);</p><p>　　comp(mm1,nn2,offx,offy+nn1);</p><p>　　comp(mm2,nn1,offx+mm1,offy);</p><p>

38、　　comp(mm2,nn2,offx+mm1,offy+nn1);</p><p>　　x[0]=offx+mm1-1;y[0]=offy+nn1-3;</p><p>　　x[1]=x[0]-1;y[1]=y[0]+2;</p><p>　　x[2]=x[1]-1;y[2]=y[1]+2;</p><p>　　x[3]=x[2]+2;y[

39、3]=y[2]-1;</p><p>　　x[4]=x[3]+1;y[4]=y[3]+2;</p><p>　　x[5]=x[4]+1;y[5]=y[4]-2;</p><p>　　x[6]=x[5]+1;y[6]=y[5]-2;</p><p>　　x[7]=x[6]-2;y[7]=y[6]+1;</p><p>　

40、　for(i=0;i<8;i++)</p><p>　　p[i]=pos(x[i],y[i],n);</p><p>　　for(i=1;i<8;i+=2)</p><p><b>　　{</b></p><p>　　j1=(i+1)%8;</p><p>　　j2=(i+2)%8;&

41、lt;/p><p>　　if(link[x[i]][y[i]].x==p[i-1])</p><p>　　link[x[i]][y[i]].x=p[j1];</p><p><b>　　else</b></p><p>　　link[x[i]][y[i]].y=p[j1];</p><p>　　if(

42、link[x[j1]][y[j1]].x==p[j2])</p><p>　　link[x[j1]][y[j1]].x=p[i];</p><p><b>　　else</b></p><p>　　link[x[j1]][y[j1]].y=p[i];</p><p><b>　　}</b></

43、p><p>　　return false;</p><p><b>　　}</b></p><p>　　void output()</p><p><b>　　{</b></p><p>　　int i=0,j=0,k=2,x,y,p;</p><p>　

44、　int b[500][500];</p><p>　　if(comp(m,n,0,0))</p><p><b>　　return;</b></p><p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<n;j++)</p><p>　　b[i][j]

45、=0;</p><p>　　b[0][0]=1;</p><p>　　printf("(0,0) ");</p><p>　　for(p=1;p<m*n;p++)</p><p><b>　　{</b></p><p>　　x=link[i][j].x;</p>

46、;<p>　　y=link[i][j].y;</p><p><b>　　i=x/n;</b></p><p><b>　　j=x%n;</b></p><p>　　if(b[i][j])</p><p><b>　　{</b></p><p&

47、gt;<b>　　i=y/n;</b></p><p><b>　　j=y%n;</b></p><p><b>　　}</b></p><p>　　b[i][j]=k++;</p><p>　　printf("(%d,%d) ",i,j);</p&g

48、t;<p>　　if((k-1)%n==0)</p><p>　　printf("\n");</p><p><b>　　} </b></p><p>　　printf("\n");</p><p>　　for(i=0;i<m;i++)</p>&

49、lt;p><b>　　{ </b></p><p>　　for(j=0;j<n;j++)</p><p><b>　　{</b></p><p>　　printf("%d ",b[i][j]); </p><p><b>　　}</b></

50、p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><

51、p><b>　　input();</b></p><p><b>　　output();</b></p><p><b>　　}</b></p><p><b>　　3.2操作方法</b></p><p>　　按提示輸入m，n即可。</p>

52、;<p><b>　　四試驗結(jié)果</b></p><p><b>　　五設(shè)計體會</b></p><p>　　這次課程設(shè)計讓我對算法中的遞歸與分治策略有了更深的了解，對c語言的應(yīng)用更加熟練了。但同時也感到了自己的不足之處，就是對程序的整體的規(guī)劃不是很好，有時候后面寫好了還要返回來改前面的，感覺很費事，下一步要對規(guī)劃更進一步。&l