马的遍历vc++课程设计报告

《马的遍历vc++课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计报告学院、系：专业名称：网络工程课程设计科目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）把这些点看作马所在点的邻接点，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按

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），实际可以走的位置尽限于还未走过的和不越出边界的

3、那些位置。为便于程序的同意处理，可以引入两个数组mover[]、movec[]，分别存储各种可能走法对当前位置的纵横增量。整形变量step存放步骤号，start存放遍历次数，在numable函数和number函数中的语句k=(i+start)%N;中是用于定位，保证不会超过棋盘范围和八次遍历都不会走同样的路径test存放遍历成功次数。在8×8方格的棋盘上，从任意指定的方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。程序框图或流程图，程序清单与调用关系主函数调用Number函数Next函数调用调用Numable函数函数调用关系2．重要模块（n

4、ext模块）的流程图：开始Next[],num,num1,minnum,I,k的初始化将返回下次可以查找的增量赋给num判断num是否为0是返回-1否将i赋值为0判断i是否小于num否返回k是给Num1赋值判断num小于1是否minnum否是给Minnum和k赋值I自增图2.2流程图一、全部源程序清单#include#include#include#defineN8//棋盘行列数#defineINF9999999intmover[]={-2,-1,1,2,2,1,-1,-2};//用来表示

5、要走向该i行，需要移动的格子数intmovec[]={1,2,2,1,-1,-2,-2,-1};//用来表示要走向该j列，需要移动的格子数classqi{private:intboard[N+1][N+1];//用于保存走的次序intstart;//测试次数intber,bec;//用于保存输入（初始）的行列intstep;//走的步数inttest;//可以遍历成功的次数intr,c;//当前行列值inti,j;//循环变量intk;//下次可以查找的增量的个数public:qi();qi(inta,intb);intnext(intr,intc);i

6、ntnumable(intr,intc,intnexta[]);//返回下次可以查找的增量intnumber(intr,intc);//返回下次可以查找的增量的个数boolbegin(inta,intb);voidset(inta,intb);};qi::qi(inta,intb){ber=a;bec=b;}qi::qi(){}voidqi::set(inta,intb){ber=a;bec=b;}intqi::next(intr,intc){intnexta[20],num,num1=0,minnum,i,k;minnum=INF;//初始化minnu

7、mnum=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];//存放预测路径中的格子}}returnk;//出口为k}boolqi::begin(inta,intb){cout<<"输入行，列(0-7)："<

8、t=1;while(start<8)//进行测试的次数{for(i=0;i