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

课 程 设 计 报 告学院、系：专业名称：网络工程课程设计科目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存放遍历成功次数。在88方格的棋盘上，从任意指定的方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。程序框图或流程图，程序清单与调用关系主函数调用Number函数Next函数调用调用Numable函数 函数调用关系2重要模块（next 模块）的流程图：开始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#define N 8/棋盘行列数#define INF 9999999int mover=-2,-1,1,2,2,1,-1,-2;/用来表示要走向该i行，需要移动的格子数int movec=1,2,2,1,-1,-2,-2,-1;/用来表示要走向该j列，需要移动的格子数class qiprivate :int boardN+1N+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 nexta20,num,num1=0,minnum,i,k;minnum=INF;/初始化minnumnum=numable(r,c,nexta);/下次可以查找的增量if(num=0) return -1; /没有出口 for(i=0;i=num-1;i+)/预测路径num1=number(r+movernextai,c+movecnextai);if(num1=minnum)minnum=num1;k=nextai;/存放预测路径中的格子return k;/出口为kbool qi:begin(int a,int b)cout输入行，列(0-7)：endl;ber=a;bec=b;start=0;test=1;while(start8)/进行测试的次数for(i=0;iN;i+)/初始化board数组for(j=0;jN*N)/如果步数大于棋盘的格子数则表明遍历成功cout方案test+:endl;for(i=0;iN;i+)/打印出该方案for(j=0;jN;j+)coutboardij ;coutendl;coutendl;start+;/测试次数加一break;/进行下一次测试 k=next(r,c);/下次可以查找的增量的个数if(k=-1)/此路不通start+;/测试次数加一break;/进行下一次测试r=r+moverk;/将当前格子行的位置赋值给rc=c+moveck;/将当前格子列的位置赋值给cboardrc=step;/将步数存入board中step+;/步数加一return true;int qi:number(int r,int c)int i,k,a,b; int num=0; for(i=0;iN;i+)k=(i+start)%N;/用于定位，保证不会超过棋盘范围和八次遍历都不会走同样的路径，并且用于控制8种可能着法的选择顺序 a=r+moverk;/由当前格子可以访问的行 b=c+moveck;/由当前格子可以访问的列if(a=0&b=0&bN&boardab=0)num+;/由当前格子可以访问，并且尚未访问过的格子数目return num;int qi:numable(int r,int c,int nexta)int i,k,a,b; int num=0;for(i=0;iN;i+)k=(i+start)%N;/用于定位，保证不会超过棋盘范围和八次遍历都不会走同样的路径，并且用于控制8种可能着法的选择顺序a=r+moverk;/由当前格子可以访问的行b=c+moveck;/由当前格子可以访问的列 if(a=0&b=0&b=7&boardab=0)/下次可以访问的格子，并且尚未访问的格子nextanum=k;/下次可以访问的格子num+;return num;int main()qi q;int a,b,d=1;char c;while(d!=0)cout输入行，列(0-7)：ab;q.begin(a,b);coutc;if(c=y|c=Y)d=1;elsed=0;system(cls);return 0;四、 程序运行的测试与分析因为本程序最大的特点就是可以将所有可遍历成功的路径都显示出来，所以我用了两组测试数据分别对有八种成功遍历路径和小于八种成功遍历路径的情况进行说明。11第一种是遍历成功路径的情况： 图6.1 成功的运行结果 2超过棋盘范围的情况： 图6.2 不成功的运行结果五、 结论与心得在上机过程中遇到了很多问题，也是我得到了长足的进步，在这一部分详细写出我在上机过程中遇到的问题和我的解决方法及体会，上机调试过程遇到主要问题是：上机过程中主要遇到的问题有两种，语法错误和逻辑错误，在这里我只写出了相关的逻辑错误。当输入数据后，无法显示结果，系统没有任何反应，之后会出现内存使的信息。如果第一次输入超过范围的数据，再重新进入系统，则可以正常退出。经过重新仔细阅读程序，模拟计算机的运算，发现我一开始定义全局变量start(用来存放测试次数)，初值为0，尽管第一次运算的一组无解数据，但是计算机还是会运算并返回一个值，所以第二次数据数据时，start的初值不再是0（而是1），于是我又添加了一个text局部变量，所以可以只输出遍历成功的结果。并且，我采用在编译原理中学到的预测分析技术，用一个nexta数组存放下次可以访问的格子，并且尚未访问的格子位置。对于8*8的棋盘，该算法若遇到最好情况（即每次nexta的都为1），它时间复杂度为n2 ，最坏情况（每次nexta都为8）它时间复杂度为n16,所以时间复杂度在n2 和n16之间。空间复杂度为n2。在这次课程设计过程中，因为抽到的题目比较难，所以我充分体会到我的C+及程序设计语言的掌握还远远不够。我觉得在上课时学习到的仅仅是基础知识，我需要大量的实践；通过这次课程设计我知道，对于一门程序设计语言，对于它的库函数掌握是十分重要的，因为这样可以节省我的时间，而且使我的程序看起来更加专业。六、 参考资料面向对象于程序设计，清华大学出版社；潭浩强等，C语言程序设计教程，高等教育出版社