课程设计报告马拦过河卒问题

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); /接收卒的坐标 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=