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

《算法设计与分析》课程设计报告题目：循环赛日程表院（系）：信息科学与工程学院专业班级：软工学生姓名：学号：指导教师：2018年1月8日至2018年1月19日算法设计与分析课程设计任务书一、设计题目循环赛日程表问题描述：设有n=2k个运动员要进行网球循环赛。现要设计一个满足一下要求的比赛日程表。(1)每个选手必须与其他n-1个选手各赛一次。(2)每个选手一天只能参赛一次。(3)循环赛在n-1天内结束。请按此要求将比赛日程表设计成有n行和n-1列的一个表格。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手，其中1≤i≤n，1≤j≤n-1。例如：当n=4时，其比赛日程表如下：123(天)1234当n=8时，其比赛日程表如下：1234567（天）1234567823414341232123456781436587412785632187656781234587214385634127654321二、设计主要内容具体要求如下：(1)使用分治策略递归算法实现。(2)使用分治策略非递归算法实现。(3)使用递推算法实现。(4)对各种算法的时间复杂度进行分析和比较。(5)设计出相应的菜单，通过菜单的选择实现各个功能三、原始资料无四、要求的设计成果(1)实现该系统功能的程序代码(2)撰写符合规范要求的课程设计报告五、进程安排序号课程设计内容学时分配备注1选题与搜集资料1天2分析与设计1天3模块实现4天4系统调试与测试2天5撰写课程设计报告2天合计10天六、主要参考资料[1]吕国英．算法设计与分析．第2版．北京：清华大学出版社，2011．[2]王晓东．算法设计与分析．北京，清华大学出版社，2009．[3]徐士良．计算机常用算法．第2版．北京，清华大学出版社出版，2010．指导教师（签名）：20年月日目录1常用算法..............................................................................................................................................11.1分治算法.......................................................................................................................................1基本概念:............................................................................................................................................11.2递推算法.......................................................................................................................................22问题分析及算法设计..........................................................................................................................52.1分治策略递归算法的设计............................................................................................................52.2分治策略非递归算法的设计.......................................................................................................72.3递推策略算法的设计...................................................................................................................83算法实现..............................................................................................................................................93.1分治策略递归算法的实现............................................................................................................93.2分治策略非递归算法的实现.....................................................................................................103.3递推策略算法的实现.................................................................................................................124测试和分析........................................................................................................................................154.1分治策略递归算法测试..............................................................................................................154.2分治策略递归算法时间复杂度的分析.......................................................................................164.3分治策略非递归算法测试.........................................................................................................164.4分治策略非递归算法时间复杂度的分析...................................................................................17时间复杂度为：O(5^(n-1)).............................................................................................................174.5递推策略算法测试....................................................................................................................174.6递推策略算法时间复杂度的分析.............................................................................................18时间复杂度为：O(5^(n-1)).............................................................................................................184.7三种算法的比较........................................................................................................................185总结...................................................................................................................................................19参考文献...............................................................................................................................................2011常用算法1.1分治算法基本概念:在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。基本思想及策略:分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。如果原问题可分割成k个子问题，1k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。分治法适用的情况:分治法所能解决的问题一般具有以下几个特征：1)该问题的规模缩小到一定的程度就可以容易地解决2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。3)利用该问题分解出的子问题的解可以合并为该问题的解；4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。21.2递推算法递推算法是一种根据递推关系进行问题求解的方法。递推关系可以抽象为一个简单的数学模型，即给定一个数的序列a0，a1...，an若存在整数n0，使当nn0时可以用等号将an与其前面的某些项ai联系起来,这样的式子成为递推公式。递推算法是一种简单的算法，通过已知条件利用特点的递推关系可以得出中间推论，直至得到问题的最终结果，递推算法分为顺推法和逆推法两种，顺推法则是在不知道初始条件的情况下，从问题的结果除非经递推关系逐步