实验四 回溯法的应用------跳马算法.doc

时间就是金钱，效率就是生命！实验四 回溯法的应用-跳马算法学号：012124345 姓名：梁文耀 一、 实验目的掌握使用回溯法求解问题的基本思路；理解其特点。二、实验思想算法的基本思路是： 定义结构体：struct PLACEint x, int y表示棋盘上的位置。 依题意，马每跳一步之后都可以从七个不同的方向选择下一步的跳马，当然，前提是跳的这一步在棋盘内且它前面的任何一步都没跳到这一格子上（限界），就可以认为这一步跳成功，否则跳马不成功。若跳马不成功，则找下一个方向尝试跳马，若七个方向都跳马不成功，则回溯。 假设棋盘的行（列）数为n。 在本算法中设置这样一个全局数组：c82=2,1,2,-1,1,2,1,-2,-2,1,-2,-1,-1,2,-1,-2; 来记录跳马的八个方向。三、程序分析（主要算法） int map1212, status1212, kp;int start,finsh;int c82=2,1,2,-1,1,2,1,-2, -2,1,-2,-1,-1,2,-1,-2;int flag = 0;void prt(int a12) /* 打印棋盘状态 */ int i,j; printf(n); for (i=2;i=9;i+) for (j=2;j=9;j+) printf(%4d,aij); printf(n); void status2(void) /* 计算棋盘各点条件数 */ int i,j,k,i2,j2,kz; for(i=0;i12;i+) for(j=0;j12;j+) statusij=100; for(i=2;i=9;i+) for(j=2;j=9;j+) kz=0; for (k=0;k=7;k+) i2=i+ck0; j2=j+ck1; if (mapi2j250) kz+; statusij=kz; /prt(status); void sort1(int b1,int b2) /* 对8个可能的方向按条件数排序 */ int i,j,mini,t; /*b1记录状态值（升序），b2记录排序后的下标 */ for (i=0;i=7;i+) mini=i; for (j=i+1;j=7;j+) if (b1jb1mini) mini=j; t=b1i; b1i=b1mini; b1mini=t; t=b2i; b2i=b2mini; b2mini=t; void init1(void) /* 初始化 */ int i,j; for(i=0;i12;i+) for(j=0;j12;j+) mapij=100; for(i=2;i=9;i+) for(j=2;j=9;j+) mapij=0; status2();void search(int i2,int j2) /* 利用递归回溯进行搜索 */ if (flag = 1) return ; int b18,b28,i,i3,j3; kp+; for(i=0;i=7;i+)/8个方向 b2i=i; b1i=statusi2+ci0j2+ci1; /for sort1(b1,b2); for(i=0;i=7;i+)/检查是否可以走 i3=i2+cb2i0; /按照排序中的方向查找 j3=j2+cb2i1; if (mapi3j3=1 & kp=65) prt(map); flag = 1; if (mapi3j3=0)/若有路可以走，则执行下面操作 mapi3j3=kp; search(i3,j3); /递归调用 mapi3j3=0; /若还没有走完并且已经没有路走则恢复0状态 /if /for kp-;/回朔/searchint main()int row, column;char ch;/int start,finsh; while (true)/打印提示信息cout 1: 开始程序endl;cout 2: 退出程序endl;cout注意：endl;coutendl;cout输入选择(1 或 2):endl;/如果输入信息不正确，继续输入doch = (char)_getch();while(ch != 1 & ch != 2);system(cls);/选择3，返回if (ch = 2)cout退出!endl;return 0;/选择1,进入操作程序else init1();cout输入初始位置(行row)(1=row=8)：row;row = row + 1; cout输入初始位置(列column)(1=column=8)：column;column = column + 1; maprowcolumn = 1; kp = 1;start = clock();cout遍历结果：endl;search(row,column);flag = 0; finsh = clock(); cout算法运行时间：finsh-startendl;kp = 1;/结束coutendlPress Any Key To Contimue:endl;_getch();system(cls);/whilereturn 0; 四、心得体会这程