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

1、算法设计与分析课程设计报告题 目： 循环赛日程表 院 （系）： 信息科学与工程学院 专业班级： 软工 学生姓名： 学 号： 指导教师： 2018 年 1 月 8 日至 2018 年 1 月 19 日 算法设计与分析 课程设计任务书一、设计题目循环赛日程表问题描述：设有n=2k个运动员要进行网球循环赛。现要设计一个满足一下要求的比赛日程表。(1) 每个选手必须与其他n-1个选手各赛一次。(2) 每个选手一天只能参赛一次。(3) 循环赛在n-1天内结束。请按此要求将比赛日程表设计成有n行和n-1列的一个表格。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手，其中1in，1jn-1。例如：

2、当n=4时，其比赛日程表如下： 1 2 3 (天)2341434123211 2 3 4当n=8时，其比赛日程表如下： 1 2 3 4 5 6 7 （天）23456781436587412785632187656781234587214385634127654321 1 2 3 4 5 6 7 8二、设计主要内容具体要求如下：(1) 使用分治策略递归算法实现。(2) 使用分治策略非递归算法实现。(3) 使用递推算法实现。(4) 对各种算法的时间复杂度进行分析和比较。(5) 设计出相应的菜单，通过菜单的选择实现各个功能三、原始资料无四、要求的设计成果(1) 实现该系统功能的程序代码(2) 撰写符

3、合规范要求的课程设计报告五、进程安排序号课程设计内容学时分配备注1选题与搜集资料1天2分析与设计1天3模块实现4天4系统调试与测试2天5撰写课程设计报告2天合计10天六、主要参考资料1吕国英算法设计与分析第2版北京：清华大学出版社，20112 王晓东算法设计与分析 北京，清华大学出版社，20093 徐士良计算机常用算法第2版北京，清华大学出版社出版，2010指导教师（签名）： 20 年 月 日目 录1 常用算法11.1分治算法1基本概念:11.2递推算法22 问题分析及算法设计52.1分治策略递归算法的设计52.2 分治策略非递归算法的设计72.3 递推策略算法的设计83 算法实现93.1分治

4、策略递归算法的实现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参考文献201 常用算法1.1分治算法基本概念: 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问

5、题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换) 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。基本思想及策略: 分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小

6、的相同问题，以便各个击破，分而治之。 分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 如果原问题可分割成k个子问题，1<kn，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接

7、求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。分治法适用的情况:分治法所能解决的问题一般具有以下几个特征： 1) 该问题的规模缩小到一定的程度就可以容易地解决 2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 3) 利用该问题分解出的子问题的解可以合并为该问题的解； 4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。1.2递推算法 递推算法是一种根据递推关系进行问题求解的方法。递推关系可以抽象为一个简单的数学模型，即给定一个数的序列a0，a1.，an若存在整数n0，使当

8、n>n0时可以用等号将an与其前面的某些项ai联系起来,这样的式子成为递推公式。递推算法是一种简单的算法，通过已知条件利用特点的递推关系可以得出中间推论，直至得到问题的最终结果，递推算法分为顺推法和逆推法两种，顺推法则是在不知道初始条件的情况下，从问题的结果除非经递推关系逐步推算出问题的解，这个问题的解也是问题的初始条件。        递归法是从已知条件出发，一步步地递推出未知项，直到问题的解。递归也是递推的一种，只不过它是对待解问题的递推，知道把一个负责的问题递推为简单的易解问题，然后再一步步返回，从而得到原问题的

9、解。严格来讲，递归不仅仅是一种问题求解方法，更是一种编程技术，许多算法可以通过递归技术来编程实现。在计算机科学中，人们把程序直接或间接调用自身的过程称为递归。过程或函数直接调用自身的递归成为直接递归，间接调用自身的递归称为间接递归。在问题求解中，采用递归算法有两个重要的好处：一是容易证明算法有两个重要的好处，其次是代码实现简洁，代码编程量少。不足是程序运行效率较低。         递推算法的基本思想是把一个复杂庞大的计算过程转化为简单过程的多次重复。该算法利用了计算机速度快和自动化的特点。  而递归法的

10、思想是从已知条件出发，一步步地递推出未知项，直到问题的解。五种典型的递推关系: 1.fibonacci数列 在所有的递推关系中，fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言 logo语言中，就有很多这类的题目。而在较为复杂的basic、pascal、c语言中，fibonacci数列类的题目因为解法相对容易一些，逐渐退出了竞赛的舞台。可是这不等于说fibonacci数列没有研究价值，恰恰相反，一些此类的题目还是能给我们一定的启发的。 fibonacci数列的代表问题是由意大利著名数学家fibonacci于1202年提出的“兔子繁殖问题”(又称“fibonacci问题”)。

11、 问题的提出：有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？ 解：设满x个月共有兔子fx对，其中当月新生的兔子数目为nx对。第x-1个月留下的兔子数目设为fx-1对。则： fx=nx+ fx-1 nx=fx-2 (即第x-2个月的所有兔子到第x个月都有繁殖能力） fx=fx-1+fx-2 边界条件：f0=0，f1=1 由上面的递推关系可依次得到： f2=f1+f0=1，f3=f2+f1=2，f4=f3+f2=3，f5=f4+f3=5，。 fabonacci数列常出现在比较简单的组合计数问题中，例如以前的竞赛中出现的“骨牌覆盖”问题。在优选法中，fibon

12、acci数列的用处也得到了较好的体现。2.hanoi塔问题 问题的提出：hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图3-11所示。 要求把a柱上n个圆盘按下述规则移到c柱上： (1)一次只能移一个圆盘； (2)圆盘只能在三个柱上存放； (3)在移动过程中，不允许大盘压小盘。 问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？ 解：设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a 柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c 柱；最

13、后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。 hn=2hn-1+1 边界条件：h1=13.平面分割问题问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。 解：设an为n条封闭曲线把平面分割成的区域个数。 由图3-13可以看出：a2-a1=2；a3-a2=4；a4-a3=6。 从这些

14、式子中可以看出an-an-1=2(n-1)。当然，上面的式子只是我们通过观察4幅图后得出的结论，它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成an-1个区域后，第n-1条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了n-1条封闭曲线，且第n条曲线与已有的每一条闭曲线恰好相交于两点，且不会与任两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的an-1个区域，一共有an-1+2(n-1)个区域。所以本题的递推关系是an=an-1+2(n-1)，边界条件是a1=1。4.catalan数 catalan数首先是由euler在精确计算对

15、凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。 问题的提出：在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn表示，hn即为catalan数。例如五边形有如下五种拆分方案(图3-14)，故h5=5。求对于一个任意的凸n边形相应的hn。5.第二类stirling数 n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用s(n,m)表示，称为第二类stirling数。 根据定义来推导带两个参数的递推关系第二类stirling数。 解：设有n个不同的球，分别用b1,b2,bn表示。从中取出一个球bn，bn的放法

16、有以下两种： bn独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为s2(n-1,m-1)； bn与别的球共占一个盒子；那么可以事先将b1,b2,bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为ms2(n-1,m)。 综合以上两种情况，可以得出第二类stirling数定理： 【定理】s2(n,m)=ms2(n-1,m)+s2(n-1,m-1) (n>1,m1) 边界条件可以由定义2推导出： s2(n,0)=0；s2(n,1)=1；s2(n,n)=1；s2(n,k)=0(k>n)。2 问题分析及算法设计2.1分治策略递归算法的设计从本问题的

17、具体情况出发，根据分治算法思想，设计出本问题的分治递归算法按分治策略，可将所有选手分成两组。n个选手的比赛日程表，可以通过n/2个选手的比赛日程表，可以通过n/4个选手设计日程表来决定；直到为2个选手的比赛日程表。这样比赛日程表的设计就变得很简单，这时只要让两个选手互相比赛即可，这样可以形成n/2组2个选手的比赛日程表（如表1、表2）。然后再反过来在两个选手的日程表上为4个选手设计比赛日程表（如表3）。然后再类推到8个、16个、2k个选手。对所有运动员的赛程进行安排，并将其存入数组内:12345678对于第一部分，将其划分为四个小的单元，即对第二行进行如下划分:同理，对第二部分（即三四行），划

18、分为两部分，第三部分同理由初始化的第一行填充第二行:( 填充原则是对角线填充)1234567821436587由 s控制的第一部分填完。然后是s+，进行第二部分的填充12345678214365873412785643218765最后是第三部分的填充1234567821436587341278564321876556781234658721437856341287654321这样循环，直到填充完毕递归算法解：2.2 分治策略非递归算法的设计分治策略同上。非递归算法解：2.3 递推策略算法的设计递推策略：3 算法实现3.1分治策略递归算法的实现#include <stdio.h>#i

19、nclude <stdlib.h>#include <time.h>const int max = 1024;/int amaxmax;/二位数组int number=2,g_k=1;clock_t start, finish;/开始和结束时间double duration;/程序运行时间void test1(int k,int m);/分治策略 递归实现int main(void) printf("请输入指数kn");while(scanf("%d",&g_k)=0)fflush(stdin);for (int y=1;

20、y<g_k;y+) number*=2;printf("参赛人员");for(int z=1;z<number;z+)printf(" day%d",z); system("cls");start=clock();for(int i=0;i<10000;i+)test1(1,number);finish=clock();duration=finish-start;/menu();for( i=1;i<=number;i+)/for(int j=1;j<=number;j+)/第一列为参赛人员printf(

21、" %d",aij);printf("n");printf("程序循环10000次所用的时间：%lfmsn",duration);return 0;void test1(int k,int m)/采用分治策略递归实现int i,j;if(m=2)/只有两个人的时候ak1=k;ak+11=k+1;elsetest1(k,m/2);test1(k+m/2,m/2);for(i=k;i<k+m/2;i+)/一次填充半个子表 上半部分的表格for(j=m/2+1;j<=m;j+)/左右对称填充aij=ai+m/2j-m/2;/填充

22、表格for(i=k+m/2;i<k+m;i+)for(j=m/2+1;j<=m;j+)aij=ai-m/2j-m/2;3.2 分治策略非递归算法的实现#include <stdio.h>#include <stdlib.h>#include <time.h>const int max = 1024;/int amaxmax;/二位数组int number=2,g_k=1;clock_t start, finish;/开始和结束时间 double duration;/程序运行时间void test2(int k);/分治策略 非递归实现int ma

23、in(void) printf("请输入指数kn");while(scanf("%d",&g_k)=0)fflush(stdin);printf("请输入“整数”kn");for (int y=1;y<g_k;y+) number*=2; printf("参赛人员");for(int z=1;z<number;z+)printf(" day%d",z); system("cls"); start=clock();for(int i=0;i<10000

24、;i+)test2(g_k);finish=clock();duration=finish-start;for( i=1;i<=number;i+)for(int j=1;j<=number;j+)/第一列为参赛人员printf(" %d",aij);printf("n");printf("程序循环10000次所用的时间：%lfmsn",duration);return 0;void test2(int k)/分治策略非递归方式实现 int i,j; int n; n=number;/拷贝参赛选手人数 for(i=1;i&

25、lt;=n;i+) a1i=i; int m=1; /填充初始位置 for(int s=1;s<=k;s+) n/=2; for(int t=1;t<=n;t+) for(i = m+1 ; i <= 2*m ; i+) for(j = m+1 ; j <=2*m ; j+) aij+(t-1)*m*2 = ai-mj+(t-1)*m*2-m; aij+(t-1)*m*2-m = ai-mj+(t-1)*m*2; m*=2; 3.3 递推策略算法的实现#include <stdio.h>#include <stdlib.h>#include &l

26、t;time.h>const int max = 1024;/int amaxmax;/二位数组int number=2,g_k=1;clock_t start, finish;/开始和结束时间 double duration;/程序运行时间void test3(int k);/对推策略实现int main(void) printf("请输入指数kn");while(scanf("%d",&g_k)=0)fflush(stdin);printf("请输入“整数”kn");for (int y=1;y<g_k;y+)

27、 number*=2; printf("参赛人员");for(int z=1;z<number;z+)printf(" day%d",z); system("cls");start=clock();for(int i=0;i<10000;i+)test3(number);finish=clock();duration=finish-start;for( i=1;i<=number;i+)for(int j=1;j<=number;j+)/第一列为参赛人员printf(" %d",aij);p

28、rintf("n");printf("程序循环10000次所用的时间：%lfmsn",duration);return 0;void test3(int num)/递推算法实现a11=1;int n,n0,i,j,k,k0;n0=1;n=2;k=g_k;/人数for (k0=1;k0<=k;k0+)for (i=n0+1;i<=n;i+)for (j=1;j<=n;j+)aij=ai-n0j+n0;for (j=n0+1;j<=n;j+)for (i=1;i<=n0;i+)aij=aij-n0+n0;for (j=n0+1;

29、j<=n;j+)for (i=n0+1;i<=n;i+)aij=aij-n0-n0;n0=n;n=n*2;4 测试和分析4.1分治策略递归算法测试给出输入情况：得到输出结果：4.2分治策略递归算法时间复杂度的分析递归算法的优点是结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，赢此为设计算法、调试程序带来很大的方便。递归算法的运行效率较低，无论是耗费计算时间的还是占用存储空间的都比非递归算法要多。时间复杂度分析：迭代处理的循环体内部3个循环语句，每个循环语句都是一个嵌套的for循环，且它们的执行次数相同，基本语句是最内层循环体的赋值语句，即填写比赛日程表的元素。基本执行语

30、句的执行次数是：t(n)= 21*21=41所以时间复杂度为o(4k)4.3 分治策略非递归算法测试给出输入情况:得到输出结果:4.4分治策略非递归算法时间复杂度的分析时间复杂度为：o(5(n-1) 4.5 递推策略算法测试给出输入情况:得到输出结果:4.6 递推策略算法时间复杂度的分析时间复杂度为：o(n3) 4.7 三种算法的比较分治递归：适用于分解后的小规模问题很好解决的问题分治非递归：适用于分治递归算法设计过于复杂的问题递推：适用于可根据已有结果推出结果的问题通过对比可知分治非递归效率最高。分治递归更简便，效率差些，递推的时间复杂度最大，效率最低。5 总结在这次课程设计当中，我了解到了我的不足，如算法的不完善、不细心和耐心不是很好等等。不细心的我在调试程序时，老是因为某个书写错误导致错误；对这些错误，我不得不花大量的时间去更正，并且还要重复检查是否出现雷同的错误而导致程序不能运行。但是通过这次课程设计，我的这些缺点有些改善。我在写新的程序时，首先要考虑的深入一点、仔细一点，这样要修改程序的时间就会少很多。并且也不会因为自己不细心而导致的浪费时间的情况出现。  在进行程序设计时，要注意想好思路。即要有恰当模块名、变量名、常量名、子程序名等。将每个功