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

1、时间就是金钱，效率就是生命！实验四 回溯法的应用-跳马算法学号：012124345姓名：梁文耀一、实验目的掌握使用回溯法求解问题的基本思路；理解其特点。二、实验思想算法的基本思路是：定义结构体：struct PLACEi nt x, i nt y 表示棋盘上的位置。依题意，马每跳一步之后都可以从七个不同的方向选择下一步的 跳马，当然，前提是跳的这一步在棋盘内且它前面的任何一步都没跳 到这一格子上（限界），就可以认为这一步跳成功，否则跳马不成功。 若跳马不成功，则找下一个方向尝试跳马，若七个方向都跳马不成功, 则回溯。假设棋盘的行（列）数为n。在本算法中设置这样一个全局数组：c82=2,1,2,

2、-1,1,2,1,-2,-2,1,-2,-1,-1,2,-1,-2;来记录跳马的八个方向。三、程序分析（主要算法）int map1212, status1212, kp;int start,fi nsh;in t 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;prin tf(n);for (i=2;i=9;i+)for (j=2;j=9;j+)pri ntf(%4d,aij);prin tf(n);void status2(void) /*计算棋盘各点条

3、件数 */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+)mi ni 二i;for (j=i+1;

4、j=7;j+)if (b1jb1mi ni)mi ni二j;t=b1i;b1i=b1mi ni;b1 min i=t;t=b2i;b2i=b2mi ni;b2mi ni =t;void initl(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+;f

5、or(i=0;iv=7;i+)/8 个方向b2i=i;b1i=statusi2+ci0j2+ci1;/forsort1(b1,b2);for(i=0;iv=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; 若还没有走完并且已经没有路走则恢复 态/if/forkp-;/ 回朔/searchint mai n()int row, col

6、u mn;char ch;/int start,fi nsh;while (true)打印提示信息coutvv 1:开始程序endl;coutvv 2:退出程序endl;coutvv注意：endl;coute ndl;coutvv输入选择(1 或 2):endl;如果输入信息不正确，继续输入doch = (char)_getch();while(ch != 1 & ch != 2);system(cls);选择3,返回if (ch = 2)cout退出!endl;return 0;选择1,进入操作程序elsein it1();cout输入初始位置(行 row)(1=row=8) : row;r

7、ow = row + 1;cout输入初 始位置(列 column)(1二columnv=8): colu mn;colu mn 二 colu mn + 1;maprowcolu mn = 1;kp = 1;start = clock();cout遍历结果：e ndl;search(row,colu mn);flag = 0;finsh = clock();cout算法运行时间：fi nsh-starte ndl;kp = 1;结束coute ndlvPress Any Key To Con timue:e ndl;_getch();system(cls);/whilereturn 0;四、心得体会这程序和