1、 算法设计与分析算法设计与分析 课程设计报告课程设计报告 题 目： 循环赛日程表 院 （系） ： 信息科学与工程学院 专业班级： 软工 学生姓名： 学 号： 指导教师： 2018 年 1 月 8 日至 2018 年 1 月 19 日 算法设计与算法设计与分析分析 课程设计任务书课程设计任务书 一、设计题目一、设计题目 循环赛日程表 问题描述：问题描述：设有 n=2 k个运动员要进行网球循环赛。现要设计一个满足一下要求的比 赛日程表。 (1) 每个选手必须与其他 n-1 个选手各赛一次。 (2) 每个选手一天只能参赛一次。 (3) 循环赛在 n-1 天内结束。 请按此要求将比赛日程表设计成有 n
2、 行和 n-1 列的一个表格。在表中的第 i 行，第 j 列处填入第 i 个选手在第 j 天所遇到的选手，其中 1in，1jn-1。 例如：当 n=4 时，其比赛日程表如下： 1 2 3 (天) 1 2 3 4 当 n=8 时，其比赛日程表如下： 1 2 3 4 5 6 7 （天） 1 2 3 4 5 6 7 8 2 3 4 1 4 3 4 1 2 3 2 1 2 3 4 5 6 7 8 1 4 3 6 5 8 7 4 1 2 7 8 5 6 3 2 1 8 7 6 5 6 7 8 1 2 3 4 5 8 7 2 1 4 3 8 5 6 3 4 1 2 7 6 5 4 3 2 1 二、设计主要
3、内容二、设计主要内容 具体要求如下： (1) 使用分治策略递归算法实现。 (2) 使用分治策略非递归算法实现。 (3) 使用递推算法实现。 (4) 对各种算法的时间复杂度进行分析和比较。 (5) 设计出相应的菜单，通过菜单的选择实现各个功能 三、原始资料三、原始资料 无 四、要求的设计成果四、要求的设计成果 (1) 实现该系统功能的程序代码 (2) 撰写符合规范要求的课程设计报告 五、进程安排五、进程安排 序号序号 课程设计内容课程设计内容 学时分配学时分配 备注备注 1 选题与搜集资料 1 天 2 分析与设计 1 天 3 模块实现 4 天 4 系统调试与测试 2 天 5 撰写课程设计报告 2
4、 天 合计 10 天 六、主要参考资料六、主要参考资料 1 吕国英算法设计与分析第 2 版北京：清华大学出版社，2011 2 王晓东算法设计与分析 北京，清华大学出版社，2009 3 徐士良计算机常用算法第 2 版北京，清华大学出版社出版，2010 指导教师（签名） ：指导教师（签名） ： 20 20 年年 月月 日日 目 录 1 1 常用算法常用算法 .1 1.1 分治算法 .1 基本概念: .1 1.2 递推算法 .2 2 2 问题分析及算法设计问题分析及算法设计 .5 2.1 分治策略递归算法的设计 5 2.2 分治策略非递归算法的设计7 2.3 递推策略算法的设计 8 3 3 算法实现
5、算法实现 .9 3.1 分治策略递归算法的实现 9 3.2 分治策略非递归算法的实现 10 3.3 递推策略算法的实现 12 4 4 测试和分析测试和分析 15 4.1 分治策略递归算法测试 15 4.2 分治策略递归算法时间复杂度的分析 16 4.3 分治策略非递归算法测试 . 16 4.4 分治策略非递归算法时间复杂度的分析 . 17 时间复杂度为：O(5(n-1). 17 4.5 递推策略算法测试 17 4.6 递推策略算法时间复杂度的分析. 18 时间复杂度为：O(5(n-1). 18 4.7 三种算法的比较 . 18 5 5 总结总结 19 参考文献参考文献. 20 1 1 1 常用
6、算法常用算法 1.1 分治算法 基本概念: 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之” ，就是 把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问 题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧 是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变 换) 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越 小，越容易直接求解，解题所需的计算时间也越少。例如，对于 n 个元素的排序问题，当 n=1时， 不需任何计算。 n=2时， 只要作一次比较即可排好序。 n=3时只要作3次比较即可， 。 而当 n 较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相 当困难的。 基本思
