数据结构与算法-课程设计报告

课程设计报告书合肥学院计算机科学与技术系课程设计报告20102011 学年第二学期课程 数据结构与算法课程设计题目名称国王与骑士问题学生姓名学号专业班级指导教师王昆仑、张贯虹2011 年 6 月一、课程设计名称及内容名称：国王和骑士问题内容：初始状态：一个国王和N个骑士分布在8*8的棋盘上0 = N = 63目标状态：国王和所有的骑士走到同一个格子里 游戏规则：在一次移动中，国王可以走到相邻的八个格子里；骑士可以走八个方向的“日”字；国王和某个骑士相遇后，可以由骑士带着移动。要求：编写算法解决问题，用最少的总移动步数达到目标状态。二、问题分析本程序要求实现最短步数的计算，首先需要考虑88的棋盘的存储方式，以及各点的国王或骑士的表示方法，然后考虑最少步数的计算方法，最后通过各功能函数的调用解决问题。设计程序所能达到的功能：对一个国王与n个骑士会合在同一点的最少步数的计算。1、数据的输入：（1）需要输入的数据：国王的坐标，骑士的个数，每个骑士的坐标；（2）数据的类型与范围：坐标均为2个字符，横坐标为AH中任意字符，纵坐标为18中任意字符，骑士个数须在0与64之间（不包括0、64）。2、数据的输出：输出骑士与国王会合的最少步数、3、测试数据：（1）国王坐标：D4 骑士个数：4 每个骑士坐标：A3 A8 H1 H8 预计结果：最短步数为 10（2）国王坐标：G1 骑士个数：3 每个骑士坐标：C3 A7 A5 预计结果：最短步数为 7（3）国王坐标：F3 骑士个数：5 每个骑士坐标：A3 A5 B2 C5 D3 预计结果：最短步数为 9三、概要设计1、为了实现上述设计：需要：（1）定义结点类型，分别表示棋盘上每个点的x，y坐标；（2）设计遍历算法，因为国王与骑士最终可能在任意一点相遇，所以要求其最少步数，必须遍历棋盘上每一点，分别求出国王和骑士到每一点的步数，再进一步比较出其最小值；（3）使用恰当搜索算法，由于骑士以“日”字型在棋盘上走动，要求其到达某一点的最短路径必须使用搜索算法，考虑遍历结点较多，采用广度优先搜索（BFS算法）；（4）判断国王与骑士相遇及步数，由于一旦国王与骑士相遇，骑士便可以带着国王行动，所以必须比较在相遇与不相遇两种情况下的最少步数，得出最终答案；2、本程序包含4个函数：（1）主函数：main()（2）解题函数：solve()（3）计算所有点骑士最少步数的函数：knightmindis()（4）计算某两点间出发到某点骑士的最少步数的函数（包含BFS算法）：BFS()各函数之间关系如下 ：main()solve()knightmindis()BFS()四、算法思想 国王与骑士位置均用坐标表示，因为只有一个国王，首先遍历国王至棋盘上每一点的最短路径；又有n个骑士，分别遍历每个骑士至每一点的最短路径，并求它们的最短路径之和，同样要求最短，求国王与所有骑士的最短路径之和org。又由于存在情况骑士带着国王前进，故还要考虑国王与骑士相遇时的情况，便利骑士经过棋盘中每一点到另外每一点的步数，计算相遇时骑士带着国王前进的最短距离change，最后比较得到最终答案。五、详细设计实现概要设计中定义的数据类型，并对每个函数操作给出流程图、伪代码。1、结点类型与定义struct Pos /定义数据类型int x,y; /x、y分别表示横纵坐标;2、定义全局变量struct Pos king,knight63; /定义国王，骑士int mindistance8888; /任意两点之间骑士的最少步数int knights; /骑士个数int mindist=32767; /最少步数3、流程图YN开始输入国王坐标输入骑士个数坐标处理输入次数=骑士个数？输入骑士坐标坐标处理调用解题函数solve结束 (主函数)YNNY开始调用函数求所有骑士最短路径knighmindissolve遍历所有点至所有点，完成？计算国王最短路径国王与骑士最短路径之和国王与骑士重合时走过的最少步数国王与骑士不重合时走过的最少步数判断得出最终答案结束调用广度优先搜索判断每个骑士最短路径遍历所有骑士，完成？N存入数组mindistance（骑士最短路径计算函数）（解题函数）4、各函数设计思想及伪代码（1）主函数：对需要数据进行输入，处理int main() 输入国王坐标； 处理坐标； /数组下标与实际坐标相差一位ASC码； 输入骑士个数; for（int i=0;i骑士数;i+） 输入骑士坐标； 处理坐标； 调用解题函数solve；（2）解题函数：已知骑士路径，分别判断国王与骑士重合时路径和不重合时路径，找出最少步数void solve() 定义i，j，k，l； /分别代表起始点坐标和目标点坐标 调用计算骑士最少步数的函数knightmindis； 遍历所有点至所有点，找出国王与骑士最少步数之和； 计算在国王与骑士在不重合情况下的最少步数； 计算国王与骑士在重合情况下的最少步数； 比较上面两种情况的结果，得出答案；（3）计算所有点骑士最少步数的函数：所有骑士最少步数之和void knightmindis() 定义i，j，k，l； /分别代表起始点坐标和目标点坐标 初始化数组mindistance8888； 遍历所有点，调用骑士最小步数计算函数BFS（4）计算某两点间出发到某点骑士的最少步数的函数：使用广度优先搜索找寻起始点与目标点之间的最短路径void BFS(int x,int y) struct Pos queue1000; /存放骑士移动后坐标 int moveway82=1,2,2,1,1,-2,2,-1,-1,2,-1,-2,-2,1,-2,-1; /骑士移动路径 参考书本上广度优先搜索算法设计算法，找出最短路径；六、上机调试情况及分析1、设计骑士最短路径计算函数时的问题由于每个点可以有8个不同方向的走法（超出棋盘范围忽略），要找其最短路径必须分布搜索，首先考虑了弗洛伊的算法求解最短路径，但因结点数较多，算法时间复杂度较大，经过验证比较，最终采用广度优先搜索BFS算法。该算法主要根据图的广度优先搜索进行改写，使用循环队列存储数据。设计广度优先算法时，虽然理论上每个结点有8中不同的移动方式，但考虑到棋盘范围有限，必须在移动式作出判断，防止越界。 for(i=0;i8;i+) fx=nx+movewayi0; fy=ny+movewayi1; if(fx=0 & fy=0) /判断，防止越界，离开棋盘 if(mindistancexyfxfysteps) mindistancexyfxfy=steps; queuefront.x=fx+steps*100; queuefront.y=fy; front+; 2、输入坐标以字符形式输入，由于回车键也被识别为一个字符，故输入算法中应该增加一位吸收回车键，否则输入错误 for(i=0;iknights;i+)printf(请输入第%d个骑士的坐标：,i+1);scanf(%c%c,&inputknightj,&inputknightj+1); getchar(); /吸收回车字符 knighti.x=inputknightj-A; /输入数据处理 knighti.y=inputknightj+1-1; j=j+2;3、设计算法，比较国王与骑士如果有重合时的最短路径和不重合时的最短路径之间的差别，用差值法可以减少算法的时间复杂度 for(m=0;msubsmax) subsmax=org-changed; /org-changed表示可以减少的步数七、测试用例、结果及其算法性能分析1、测试用例及结果2、算法性能分析（1）空间性能分析struct Pos int x,y; ;struct Pos king,knight63; int mindistance8888; int knights; int mindist=32767; Pos类型的数据，每个元素包含2个int型变量，每个int类型元素占2个字节，所以以上定义所占用总空间为：2*2+63*2*2+8*8*8*8*2+2+2=8 452字节另外，处理数据过程中，还设置了一些临时变量，由于可以重复使用，使用结束时可以释放，在此不做计算。（2）时间性能分析： 设骑士个数knights = n，则： 主函数中输入骑士坐标时有循环语句： for(i=0;iknights;i+) printf(请输入第%d个骑士的坐标：,i+1); scanf(%c%c,&inputknightj,&inputknightj+1); getchar(); /吸收回车字符 knighti.x=inputknightj-A; /输入数据处理 knighti.y=inputknightj+1-1; j=j+2; 时间复杂度O（n）= n ； 解题函数中由于便利循环的循环次数固定，故不计入时间复杂度计算，经计算如下语句：for(m=0;mknights;m+) /至每一点骑士最短步数 nowdist+=mindistanceknightm.xknightm.yij; subsmax=0; or(m=0;msubsmax) subsmax=org-changed; 时间复杂度O（n）= n ； 骑士最短路径计算函数中，主要参考了书本上有关广度优先搜索的算法，循环语句如下； while(front!=rear) steps=queuerear.x/100; nx=queuerear.x%100; ny=queuerear.y; rear+; steps+; for(i=0;i8;i+) fx=nx+movewayi0; fy=ny+movewayi1; if(fx=0 & fy=0) if(mindistancexyfxfysteps) mindistancexyfxfy=steps; queuefront.x=fx+steps*100; queuefront.y=fy; front+; 时间复杂度等同于广度优先，O（n）= n2 。八、用户使用说明1、打开程序，运行cpp.exe；2、输入国王坐标，两个字符，横坐标为AH，纵坐标为18；3、输入骑士个数；4、分别输入每个骑士的坐标；5、回车确认，得出答案。九、参考文献1 王昆仑、李红，数据结构与算法，北京，中国铁道出版社，20102 何钦铭、颜辉，C语言程序设计，北京，高等教育出版社，20093 郑莉、董渊、张瑞丰，C+语言程序设计，北京，清华大学出版社,，20044 /p-.html5 /mythit/archive/2009/07/02/89123.html附录（完整源程序）#include#includestruct Pos /定义数据类型int x,y; /x、y分别表示横纵坐标;struct Pos king,knight63; /定义国王，骑士int mindistance8888; /任意两点之间骑士的最少步数int knights; /骑士个数int mindist=32767; /最少步数/计算从 (x,y) 出发到某点骑士的最少步数/广度优先搜索BFS算法void BFS(int x,int y) struct Pos queue1000; /存放骑士移动后坐标 int moveway82=1,2,2,1,1,-2,2,-1,-1,2,-1,-2,-2,1,-2,-1;/骑士移动路径 int i,front=0,rear=0,nx,ny,steps=0,fx,fy; /广度优先搜索 mindistancexyxy=steps; queuefront.x=x+steps*100,queuefront.y=y,front+; while(front!=rear) steps=queuerear.x/100; nx=queuerear.x%100; ny=queuerear.y; rear+; steps+; for(i=0;i8;i+) fx=nx+movewayi0; fy=ny+movewayi1; if(fx=0 & fy=0) /防止走出棋盘 if(mindistancexyfxfysteps) mindistancexyfxfy=steps; queuefront.x=fx+steps*100; /入队 queuefront.y=fy; front+; /计算所有点骑士最少步数void knightmindis() int i,j,k,l; for(i=0;i8;i+) /初始化数组 for(j=0;j8;j+) for(k=0;k8;k+) for(l=0;l8;l+) mindistanceijkl=50; for(i=0;i8;i+) for(j=0;j8;j+) BFS(i,j);/i,j表示起始点/k,l表示某一骑士与国王会合时位置/nowdis表示目前的步数/subsmax为可以减少的步数中的最大值void solve() int i,j,k,l,m; int nowdist,subsmax; int org,changed; knightmindis(); for(i=0;i8;i+) /遍历所有点至所有点 for(j=0;j8;j+) for(k=0;k8;k+) for(l=0;l8;l+) nowdist=abs(king.x-i)+abs(king.y-j); /至每一点国王最短步数 for(m=0;mknights;m+) /至每一点骑士最短步数 nowdist+=mindistanceknightm.xknightm.yij; subsmax=0; for(m=0;msubsmax) /判断最大值 subsmax=o