合肥学院。计算机科学与技术系。
课程设计报告。
2010～2011 学年第二学期。
课程。数据结构与算法。
课程设计题目名称。
国王与骑士问题。
学生姓名。学号。
专业班级。指导教师。
王昆仑、张贯虹。
2011 年 6 月。
合肥学院。计算机科学与技术系。
课程设计报告。
2010～2011 学年第二学期。
2011 年 6 月。
一、课程设计名称及内容。
名称：国王和骑士问题。
内容：初始状态：一个国王和n个骑士分布在8*8的棋盘上0 <=n <=63
目标状态：国王和所有的骑士走到同一个格子里
游戏规则：在一次移动中，国王可以走到相邻的八个格子里；骑士可以走八个方向的“日”字；国王和某个骑士相遇后，可以由骑士带着移动。
要求：编写算法解决问题，用最少的总移动步数达到目标状态。
二、问题分析。
本程序要求实现最短步数的计算，首先需要考虑8×8的棋盘的存储方式，以及各点的国王或骑士的表示方法，然后考虑最少步数的计算方法，最后通过各功能函数的调用解决问题。设计程序所能达到的功能：对一个国王与n个骑士会合在同一点的最少步数的计算。
1、数据的输入：
1）需要输入的数据：①国王的坐标，②骑士的个数，③每个骑士的坐标；
2）数据的类型与范围：坐标均为2个字符，横坐标为a~h中任意字符，纵坐标为1~8中任意字符，骑士个数须在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()
各函数之间关系如下 ：
四、算法思想。
国王与骑士位置均用坐标表示，因为只有一个国王，首先遍历国王至棋盘上每一点的最短路径；又有n个骑士，分别遍历每个骑士至每一点的最短路径，并求它们的最短路径之和，同样要求最短，求国王与所有骑士的最短路径之和org。又由于存在情况骑士带着国王前进，故还要考虑国王与骑士相遇时的情况，便利骑士经过棋盘中每一点到另外每一点的步数，计算相遇时骑士带着国王前进的最短距离change，最后比较得到最终答案。
五、详细设计。
实现概要设计中定义的数据类型，并对每个函数操作给出流程图、伪**。
1、结点类型与定义。
struct pos
调用解题函数solve；
2）解题函数：已知骑士路径，分别判断国王与骑士重合时路径和不重合时路径，找出最少步数。
void solve(),
//骑士移动路径。
参考书本上广度优先搜索算法设计算法，找出最短路径；
六、上机调试情况及分析。
1、设计骑士最短路径计算函数时的问题。
由于每个点可以有8个不同方向的走法（超出棋盘范围忽略），要找其最短路径必须分布搜索，首先考虑了弗洛伊的算法求解最短路径，但因结点数较多，算法时间复杂度较大，经过验证比较，最终采用广度优先搜索bfs算法。该算法主要根据图的广度优先搜索进行改写，使用循环队列存储数据。
设计广度优先算法时，虽然理论上每个结点有8中不同的移动方式，但考虑到棋盘范围有限，必须在移动式作出判断，防止越界。
for(i=0;i<8;i++)
fx=nx+moveway[i][0];
fy=ny+moveway[i][1];
if(fx<8 &&fx>=0 &&fy<8 &&fy>=0) /判断，防止越界，离开棋盘。
if(mindistance[x][y][fx][fy]>steps)
mindistance[x][y][fx][fy]=steps;
queue[front].x=fx+steps*100;
queue[front].y=fy;
front++;
2、输入坐标以字符形式输入，由于回车键也被识别为一个字符，故输入算法中应该增加一位吸收回车键，否则输入错误。
for(i=0;i
3、设计算法，比较国王与骑士如果有重合时的最短路径和不重合时的最短路径之间的差别，用差值法可以减少算法的时间复杂度。
for(m=0;m 福建工程学院软件学院。题目。专业。姓名。学号。同组其他学生 学号。2015年月日。目录。一 需求分析 3 二 总体设计 3 三 详细设计 3 四 调试与测试 3 五 测试结果 3 六 用户手册 3 七 附录 3 描述问题。简述课题要解决的问题是什么，有什么要求和限制条件。二 总体设计。必须包含程序设... 你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。命运如同手中的掌纹，无论多曲折，终掌握在自己手中。数据结构与算法课程设计 harbin institute of technology 数据结构与算法。课程设计报告。2014年度秋季学期 设计题目。小组成员 11337... 算法与数据结构。课程设计指导书。题目 校园导游咨询系统。2012年5月23日。一 课程性质与教学目的。算法与数据结构课程设计 是计算机科学中一门综合性的专业基础课。主要介绍如何合理地组织数据 有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。本课程设计旨在加深对数据结构的逻辑结构和物理结构...算法与数据结构课程设计报告
《数据结构与算法课程设计》报告
算法与数据结构课程设计报告