使用分治策略递归和非递归和递推算法解决循环赛日程表课程设计报告

《使用分治策略递归和非递归和递推算法解决循环赛日程表课程设计报告》由会员分享，可在线阅读，更多相关《使用分治策略递归和非递归和递推算法解决循环赛日程表课程设计报告（25页珍藏版）》请在毕设资料网上搜索。

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 较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相 当困难的。 基本思