合肥学院计算机科学与技术系课程设计报告20102011学年第二学期课程数据结构与算法课程设计题目名称国王与骑士问题学生姓名学号专业班级指导教师王昆仑、张贯虹2011 年 6 月一、课程设计名称及内容名称：国王和骑士问题内容：初始状态：一个国王和N个骑士分布在8*8的棋盘上0 = N = 63 目标状态：国王和所有的骑士走到同一个格子里游戏规则：在一次移动中，国王可以走到相邻的八个格子里；骑士可以走八个方向的 “日”字；国王和某个骑士相遇后，可以由骑士带着移动。要求：编写算法解决问题，用最少的总移动步数达到目标状态。二、问题分析本程序要求实现最短步数的计算，首先需要考虑8X8的棋盘的存储方式，以及各点的 国王或骑士的表示方法，然后考虑最少步数的计算方法，最后通过各功能函数的调用解决问 题。设计程序所能达到的功能：对一个国王与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、流程图结束(解题函数)4、各函数设计思想及伪代码(1) 主函数：对需要数据进行输入，处理int main()输入国王坐标；处理坐标；数组下标与实际坐标相差一位ASCII码；输入骑士个数;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、测试用例及结果 E:14-Si 和騎士问题辽 UIZT ONGDebd gCppl.exe -点 HENENENE4 4坐坐坐于 r的的的的于暑确 间書第扇第屈an 生星星星冃青PF-Z匚 y3 9 18 n n H H 勺“.-!=、_:16；7 E:14 -国王和 =ragEZUJZHON GDcbu gCp pljext E:14-U 王 JDlt 问蛊 ZU 门 H ON GDfbu gCppl.exe，=回 嘉-nvnnv-、.?k 王y13坐坐坐于2 7 5S_ c A fl 票点1 2 3 - .M 标倉M-.ffl-干士 mm 型s-圾蠻寧ei -垦星垦星tz+ rrr.lrrr.IT-v T土 yF3国第第第第国an aaaaaxas W1BW- -es 请请请冃请请骑Ipr3 5 2 5 3=- n A E c r 询 5坐塑坐坐坐肝 r.L V-卓2、算法性能分析(1) 空间性能分析struct Posint 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,贝9： 主函数中输入骑士坐标时有循环语句：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;mknights;m+) org=abs(king.x-i)+abs(king.y-j)+mindistanceknightm.xknightm.yij; changed=abs(king.x-k)+abs(king.y-l)+min