马的遍历VC++课程设计报告.docVIP

课 程 设 计 报 告 学院、系： 专业名称： 网络工程 课程设计科目 VC++程序课程设计 学生姓名： 指导教师： 完成时间： 2010年9月-11月 解骑士巡游问题 设计任务与目标 国际象棋中马采用“日”字走法，对棋盘上马所在的结点，一步内到达的结点最多有八个，即假设马所在点的坐标为（i，j），那么其它八个结点的坐标为（i+1,j+2）,（i+2,j+1）,（i+2,j-1）,（i+1,j-2），（i-1,j-2）,（i-2,j-1）,（i-2,j+1）,（i-1,j+2）把这些点看作马所在点的邻接点，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点 棋盘的规格限制为8*8，输入数据为起始点的位置（0-7）。输出数据为可以遍历成功的若干方案（本程序设置为至多八种）。 方案设计与论证 解决马的遍历问题，可以用一个二维数组board[][]来表示棋盘，一开始用来存放步骤号，若走过了则把它赋值为1。另对马的8种可能走法设定一个顺序，如当前位置在棋盘的（i，j）方格，下一个可能的位置依次为（i+2，j+1）、（i+1，j+2）、（i-1，j+2）、（i-2，j+1）、（i-2，j-1）、（i-1，j-2）、（i+1，j-2）、（i+2，j-1），实际可以走的位置尽限于还未走过的和不越出边界的那些位置。为便于程序的同意处理，可以引入两个数组mover[]、movec[]，分别存储各种可能走法对当前位置的纵横增量。整形变量step存放步骤号，start存放遍历次数，在numable函数和number函数中的语句k=(i+start)%N;中是用于定位，保证不会超过棋盘范围和八次遍历都不会走同样的路径test存放遍历成功次数。 在8×8方格的棋盘上，从任意指定的方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。 程序框图或流程图，程序清单与调用关系 调用 调用 调用 函数调用关系 2．重要模块（next 模块）的流程图： 是 否 否 是 否 是 图2.2 流程图 全部源程序清单 #includeiostream.h #includeiomanip.h #includestdlib.h #define N 8//棋盘行列数 #define INF 9999999 int mover[]={-2,-1,1,2,2,1,-1,-2};//用来表示要走向该i行，需要移动的格子数 int movec[]={1,2,2,1,-1,-2,-2,-1};//用来表示要走向该j列，需要移动的格子数 class qi { private : int board[N+1][N+1];//用于保存走的次序 int start;//测试次数 int ber,bec;//用于保存输入（初始）的行列 int step;//走的步数 int test;//可以遍历成功的次数 int r,c;//当前行列值 int i,j;//循环变量 int k;//下次可以查找的增量的个数 public : qi(); qi(int a,int b); int next(int r, int c); int numable(int r,int c,int nexta[]);//返回下次可以查找的增量 int number(int r,int c);//返回下次可以查找的增量的个数 bool begin(int a,int b); void set(int a,int b); }; qi::qi(int a,int b) { ber=a; bec=b; } qi::qi() { } void qi::set(int a,int b) { ber=a; bec=b; } int qi::next(int r,int c) { int nexta[20],num,num1=0,minnum,i,k; minnum=INF;//初始化minnum num=numable(r,c,nexta);//下次可以查找的增量 if(num==0) return -1; //没有出口 for(i=0;i=num-1;i++)//预测路径 { num1=number(r+mover[nexta[i]],c+movec[nexta[i]]); if(num1=minnum) { minnum=num1; k=nexta[i];//存放预测路径中的格子 } } r