《课程设计报告马拦过河卒问题》由会员分享,可在线阅读,更多相关《课程设计报告马拦过河卒问题(8页珍藏版)》请在金锄头文库上搜索。
1、合肥学院计算机科学与技术系课程设计报告2010 2011 学年第2学期课程 数据结构与算法课程设计题目名称马拦过河卒问题学生姓名XXX学号XXX专业班级Xxx指导教师Xxx2011 年 6 月1、题目名称:马拦过河卒问题内容:棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示,A点(0, 0)、B点(n, m)(n, m为不超过13的整数),同样马的位置坐标是需要给出的。要求计算出卒从A点能够到达B点的路径的条数,假设马的位置是固定不动的,并不
2、是卒走一步马走一步。2、问题分析图1-1 坐标轴A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如上图1-1的C点),该马所在的点和所有跳跃一步可达的点称为方马的控制点。例如上图C点上的马可以控制9个点(图中的P1,P2.P8和C)。卒不能通过对方的控制点。棋盘用坐标表示,A点(0,0)、B点(n, m)(n,m为不超过20的整数,并由键盘输入),同样马 的位置坐标是需要给出的(约定:CA,同时CB)。现在要求你计算出卒从A点能够到达B点的路径的条数。做一个表,记录马可以攻击的位置,主要要包括马本身的位置;然后从(0,0)开始每次递归(
3、x+1,y)和(x,y+1),如何(x=n1&y=n2)说明走到位置了,那么k+(路径数);如果大于边界和等于马可以攻击的位置就return,这样就可以了。不说考虑速度关系,我们可以加一个过程,即坐标一旦超出目标就return。3、数据结构的选择和概要设计做一个表,记录马可以攻击的位置,主要要包括马本身的位置;然后从(0,0)开始每次递归(x+1,y)和(x,y+1),如何(x=n1&y=n2)说明走到位置了,那么k+(路径数);如果大于边界和等于马可以攻击的位置就return,这样就可以了。不说考虑速度关系,我们可以加一个剪枝过程,即坐标一旦超出目标就return。4、算法思想图1-2 坐标
4、轴 1、卒行走的规则:可以向下、或者向右。2、计算马的控制点 按照题意,对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点,卒不能通过对方马的控制点。在卒出发之前,必须计算对方马的所有控制点。显然,若(0,0)或(n,m)为控制点,则输出路径数为0。3、假设马的位置是固定不动的,并不是卒走一步马走一步。所以从这去计算路径数。5、详细设计和主要编码段使用递归的方法,记录马可以攻击的位置if(c=X&d=0) /马不能在x坐标最边缘的点 if(d+2=0) ac-1d-2=0; /查看马是否能够攻击到 if(c+1=X) /马向右移动一个坐标,判断与x的关系 if(d+2=0) ac+1d-
5、2=0; /查看马是否能够攻击到 if(c-2=0) /马不能在y坐标为1的点 if(d-1=0) ac-2d-1=0; if(d+1=Y) ac-2d+1=0; /查看马是否能够攻击到 if(c+2=0) ac+2d-1=0; if(d+1=Y) ac+2d+1=0; /查看马是否能够攻击到 6、上机调试情况记录对算法的性能分析该算法在进行运算时,存储结果用到一个二维数组,而且当使用完之后,就将初始化,因此不会像数组那样浪费太多的空间,除此之外,还用到一个递归的思想,不过该算法的时间复杂度有点小,不是那么的大,函数中主要运用了递归语句,尤其是在一般情况运算中,用递归的方法,最终实现得到结果。
6、时间复杂度为O(n2)。在调试的时候遇到了一些问题:(1)、程序调试过程中常会出现一些小错误,如少括号少分号等小问题都可以按照提示找到,然后改正。(2)、语句错误语句使用不当造成程序无法运行出正常的结果。(3)、一开始,不会出项了好多错误,没有考虑到特殊情况。我的数据结构学的不好,后来问了几个同学,又参考了借来的一些书后,才会,那个确实好难。(4)、对于递归的一些运算,都会用到我们以前学到的C语言里的知识,因此还算简单,程序能够完成。 (5)我写的这个程序可能过于简单,程序量很小,还请老师原谅。但都能实现任务书的要求。7、测试用例、结果及其分析图2-1 运行后,程序调试运行程序,输入数据,运行
7、成功。如图2-1。图2-2运行后,程序调试每次输入数据都需要重新运行一下程序,所以在原来程序的基础上加入大循环,可以多次使用,最后用判断语句是否为0,来结束函数。见图2-2。图2-3 程序出现错误的情况用判断语句是否为0,来结束函数。结果发现语句发错误,重新修改判断函数,见图2-3。图2-4 程序实现所有的功能修改判断语句函数成功,程序能够实现功能。见图2-4。8、用户使用说明本程序运行过程时带有提示性语句。由于本程序可以对任意一个符合条件的数进行计算,所以运行开始时根据提示输入要输入的数据。注意在这里提醒一下,由于程序的时间复杂度很高所以为了比较快的得到结果,建议输入的数据最好在10以下。本
8、程序在运行过程中可能出现一个问题,即输入一个数据后程序一直在运行,请不要关闭该程序,此程序会在一段较长的时间的运算得到你要的结果。本程序运行过程时带有提示性语句。由于本程序对A点到B点的路径数计算,所以开始得输入马的坐标和B点的坐标(A点位坐标原点),本程序要求的B点的坐标a,b都不能 超过13.,输入坐标时需注意。输入坐标尽量考虑特殊情况,这样可以知道程序的正确性。本程序基本还是很简单,能够快速运行。9、参考文献1 王昆仑,李红. 数据结构与算法. 北京:中国铁道出版社,2006年5月。2 徐孝凯.数据结构实用教程.北京:清华大学出版社。1999年12月第一版 。3 Bjarne Strou
9、strup.C+程序设计语言(特别版)。机械工业出版社。2002 年7月。4 其它。10、附录(完整源程序)#includestdio.hint k=0,s1=1;int a1616;int X,Y,c,d;void fun(int i,int j) if(i=X&j=Y) k+; if(i+1=X&ai+1j) fun(i+1,j); if(j+1=Y&aij+1) fun(i,j+1); /马不能到达 ,判断i是否到达x,j是否到达yint main() int s,t; while(1) printf(卒的坐标是:); scanf(%d,&X); scanf(%d,&Y); /接收卒的坐
10、标 printf(马的坐标是:); scanf(%d,&c); scanf(%d,&d); /接收马的坐标 for(s=0;s=X;s+) for(t=0;t=Y;t+) ast=1; /以(0,0)到点(x,y)所形成的矩形的点都赋值为1 if(c=X&d=0) /马不能在x坐标最边缘的点 if(d+2=0) ac-1d-2=0; if(c+1=X) /马向右移动一个坐标,判断与x的关系 if(d+2=0) ac+1d-2=0; if(c-2=0) /马不能在y坐标为1的点 if(d-1=0) ac-2d-1=0; if(d+1=Y) ac-2d+1=0; if(c+2=0) ac+2d-1=0; if(d+1=Y) ac+2d+1=0; fun(0,0); printf(路径的条数为:); printf(%dn,k); printf(是否继续?0-退出n); scanf(%d,&s); if(s=0) break; return 0;