文档介绍：实验四回溯法的应用------跳马算法学号:012124345姓名:梁文耀一、实验目的掌握使用回溯法求解问题的基本思路;理解其特点。二、实验思想算法的基本思路是:定义结构体:structPLACE{intx,inty}表示棋盘上的位置。依题意,马每跳一步之后都可以从七个不同的方向选择下一步的跳马,当然,前提是跳的这一步在棋盘内且它前面的任何一步都没跳到这一格子上(限界),就可以认为这一步跳成功,否则跳马不成功。若跳马不成功,则找下一个方向尝试跳马,若七个方向都跳马不成功,则回溯。假设棋盘的行(列)数为n。在本算法中设置这样一个全局数组:c[8][2]={{2,1},{2,-1},{1,2},{1,-2},{-2,1},{-2,-1},{-1,2},{-1,-2}};来记录跳马的八个方向。三、程序分析(主要算法)intmap[12][12],status[12][12],kp;intstart,finsh;intc[8][2]={{2,1},{2,-1},{1,2},{1,-2},{-2,1},{-2,-1},{-1,2},{-1,-2}};intflag=0;voidprt(inta[][12])/*打印棋盘状态*/{inti,j;printf("\n");for(i=2;i<=9;i++){ for(j=2;j<=9;j++) printf("%4d",a[i][j]);printf("\n");}}voidstatus2(void)/*计算棋盘各点条件数*/{inti,j,k,i2,j2,kz;for(i=0;i<12;i++)for(j=0;j<12;j++)status[i][j]=100;for(i=2;i<=9;i++)for(j=2;j<=9;j++){ kz=0;for(k=0;k<=7;k++){ i2=i+c[k][0]; j2=j+c[k][1];if(map[i2][j2]<50)kz++;}status[i][j]=kz;}//prt(status);}voidsort1(intb1[],intb2[])/*对8个可能的方向按条件数排序*/{inti,j,mini,t;/*b1[]记录状态值(升序),b2[]记录排序后的下标*/for(i=0;i<=7;i++){mini=i;for(j=i+1;j<=7;j++)if(b1[j]<b1[mini])mini=j;t=b1[i];b1[i]=b1[mini];b1[mini]=t;t=b2[i];b2[i]=b2[mini];b2[mini]=t;}}voidinit1(void)/*初始化*/{inti,j;for(i=0;i<12;i++)for(j=0;j<12;j++)map[i][j]=100;for(i=2;i<=9;i++)for(j=2;j<=9;j++)map[i][j]=0;status2();}voidsearch(inti2,intj2)/*利用递归回溯进行搜索*/{if(flag==1) return;intb1[8],b2[8],i,i3,j3;kp++;for(i=0;i<=7;i++)//8个方向{ b2[i]=i;b1[i]=status[i2+c[i][0]][j2+c[i][1]];}//forsort1(b1,b2);for(i=0;i