题目：循环赛日程表
设计一个满足一下要求的比赛日程表
（1）每个选手必须与其他n-1个选手各赛一次；
（2）每个选手一天只能赛一次；
（3）若才赛选手为偶数，循环赛一共进行n-1天；若参赛选手为奇数循环赛一共进行n天。主要思想：“贝格尔”编排法,其优点是单数队参加时可避免第二轮的轮空队从第四轮起每场都与前一轮的轮空队比赛的不合理现象。
方法如下：
所谓贝格尔编排法，第一轮开始的编排同传统方法一样，假设现在有7个队参加单循环，分别抽签成为1-7队，由于贝格尔编排法必须是双数队，所以再加一个0队，与0队比赛表示该队轮空，现在必须定下一个数为参照数，因此我们假设0为参照数（任意数都可以，一般取0或者最大数），第一轮的对阵形式如下：
1 – 0
2 – 7
3 – 6
4 – 5
这个大家都能看明白，这跟贝格尔编排法无关，第二轮则开始相关了。在第一轮中，0在右边，现在我们要在第二轮让它换成左边，第三轮又让它换回右边，反反复复，到最后一轮即第七轮时，它还是在右边。我们把0安排好后，再把第一轮右下角的5提到右上角来，因此第二轮的第一场比赛就变成：
0 – 5
然后我们还要回到第一轮的八个数字来，我们假设它是一个环，无论是顺时针还是逆时针，它们的位置是相对固定的（除了它们与0的位置有时候会改变外，因为0的位置是先定好的），比如按照顺时针方向看，5的前面是6，后面是4，因此，第二轮我们还是安排5的前面是6，后面是4，0我们假设它不存在，于是第二轮的第一、二场比赛就是：
0 – 5
6 – 4
那其他怎么办呢，照旧轮呗，就像排球的轮转一样，于是第二轮就是
0 – 5
6 – 4
7 – 3
1 – 2
其他依次类推。
无论比赛队是单数还是双数，最后一轮时，必定是“0”或最大的一个代号在右上角，“1”在右下角。
根据参赛队的个数不同，应按规定的间隔数移动（见表）。
间隔移动
#include
#define MAXSIZA 32 //最大参赛队伍个数
void main()
{
int m,n,i;
int a[MAXSIZA][MAXSIZA]; //用于日程表存储
//输入处理
printf("请输入参赛队伍个数（2-%d）：",MAXSIZA);
scanf("%d",&m);
while(m>MAXSIZA || m<2)
{
printf("输入数据有误，请重新输入参赛队伍个数（2-%d）：",MAXSIZA);
scanf("%d",&m);
}
//奇数个选手，虚拟一个选手，使之成为偶数
n=m+m%2;
//给选手编号，存储在数组第一列
for(i=0;i a[i][0]=i+1; //生成日程表，将比赛安排存储在数组中 for(i=1;i { for(int j=0;j { a[a[j][0]-1][i]=a[(n-1-j)%n][0]; a[a[(n-1-j)%n][0]-1][i]=a[j][0]; } //将数组第一列按将除n外的选手按顺时针（或逆时针旋转）n/2-1个位置int k=0,t;t=a[k][0]; for(;k a[(k*(n/2-1))%(n-1)][0]=a[(k+1)*(n/2-1)%(n-1)][0]; a[(k*(n/2-1))%(n-1)][0]=t; } for(i=0;i { if(i==0)printf("队号\t"); else printf("第%d天\t",i); } printf("\n"); for(i=0;i { for(int j=0;j { if(m!=n && a[i][j]==n) //用输出‘-’表示轮空printf(" -\t"); else printf(" %d\t",a[i][j]); } printf("\n"); } } 运行结果如下： 循环赛的方法与编排 一、循环赛的种类与特点 （一）循环赛的种类 循环赛又称循环法。是指参赛队（或个人，下同）之间，都要互相轮流比赛，最后按照各参赛队在全部比赛中的胜负场数、得分多少排定名次的比赛方法。它在对抗性项目比赛中经常被采用。循环赛包括单循环、双循环或分组循环三种。单循环是所有参赛队（人）相互轮赛一次；双循环是所有参赛队（人）相互轮赛二次；分组循环是参赛队（人）较多时，采用种子法，把强队（人）分散在各组，先进行小组单循环赛，再根据小组名次来组织第二阶段的比赛。主办单位可根据参赛队多少和比赛期限的长短以及项目特点而灵活选用。一般情况下，单循环宜在参赛队不太多，比赛时间与场地又比较充裕时采用；分组循环大多是在参赛队数多，比赛时间又不能过长，并尽量为参赛队提供比赛机会，使比赛能较合理地排定名次时采用。 （二）循环赛的特点 采用循环法进行比赛，总的优点是参赛队机会均等，实战和互相观摩学习的机会多，能准确地反映出参赛队之间真正的技术水平的高低，客观地排定参赛队的名次，比赛结果的偶然性和机遇性小。上述优点正是淘汰赛的主要缺点，但循环赛自身也存在有某些不足与矛盾，应引起组织者的重视。 1.比赛总的期限长，占用场地和时间多，当参赛队（人）多时，直接采用大循环赛有一定困难，应用范围上有一定的局限性。 2.如何合理地安排比赛的顺序，避免在比赛时间、间隙、地点、场次和比赛条件等方面出现的不均衡现象。 3.当比赛结果有两个或两个以上队的胜负场数相同，得失分相等时，如何根据不同项目的特点，科学地解决好最后名次的排定。 二、循环赛的轮数与场数计算 （一）循环赛的轮数 每个参赛队赛毕一场（轮空队除外），称为一轮结束。计算循环赛的轮数，目的在于计划整个比赛所需用的时间或期限，是比赛日程安排的主要依据。其计算方法：Y=轮次数，N=参赛队数 如果参赛队为偶数Y=N-1 即轮次数=参赛队数-1 如果参赛队为奇数，则：比赛轮数=参赛队数。 注：双循环赛的轮数是单循环赛轮数的加倍。 （二）循环赛的场数 循环赛的场数是指参赛队之间互相轮流比赛全部结束的总场数。计算循环赛的比赛总场数，目的在于计划安排人力、物力、比赛日程与场地。其计算方法如下： X=N×（N-1）÷2 X为比赛场数，N为参赛队数。 单循环比赛场数=参赛队数×（参赛队数-1）÷2 双循环比赛的总场数=参赛队数×（参赛队数-1） 三、循环比赛顺序的编排方法与注意事项 （一）单循环比赛顺序的编排方法 1.轮次表的安排方法 一、问题表述： 设有n个运动员要进行网球循环赛。设计一个满足以下要 求的比赛日程表， (1)每个选手必须与其他n-1个选手各赛一次； (2) 每个选手一天只能赛一次； (3) 当n是偶数时，循环赛进行n-1天，当n是奇数时，循环 赛进行n天 二、分析问题 题目是要n名运动员进行循环比赛。当n为偶数时，正好每天都可以两两一组，与其余的n-1个选手比赛，只需n-1天； 而当n为奇数，每天将有一个选手轮空，比赛将持续n天。 可以采用的算法如下： 1.算法一：使用分治法 当n为偶数时，可以讲问题分为两个部分n/2; 然后继续划分， 知道最后剩余两名选手单独比赛。当n为奇数时，增设一个虚拟 选手，运动员为n+1个，将问题转化为是偶数的情形。当选手与 虚拟选手比赛时，表示轮空，因此只需要关注n为偶数的情形。 a)当n/2为偶数时，与n = 2^k情形类此。 b)当n/2为奇数时，增设一个虚拟的选手，递归返回的将有轮 空的选手，可以讲在前面n/2轮比赛的选手与后面n/2轮空的 选手进行比赛。 2.算法二：利用边是奇数的正多边形。 特点：以多边形中的任意一个顶点画对称轴，其余偶数对顶点相 互对称。 N名选手编号为1~n，将其画成一个正多边形。 a)所以当n为奇数时，第一天1号休息，其余以一号为对称轴， 两两对称打比赛，第二天开始一次轮流休息，其余一休息的 那个人编号为对称轴，两两比赛。这样比赛可进行n天。如 图： b) 当n 为偶数时，取出编号最大的，其他的组成一个正多边形，n 号一次顺序与1,2，。。。n-1号选手比赛，其他与a ）相同。如图所示：（图中是从0开始编号） 第一节循环赛的方法与编排 一、循环赛的种类与特点 （一）循环赛的种类 1、概念循环赛又称循环法。指参赛队（人）之间，都相互轮流比赛，最后按照各参赛队在全部比赛中的胜负场数、得分多少排定名次的比赛方法。 2、分类循环赛包括单循环、双循环和分组循环三种。 单循环是所有参赛队（人）相互轮赛一次；一般在参赛队人不太多，场地和时间比较充裕时采用。 双循环是所有参赛队（人）相互轮赛二次；一般在参赛队人不多，场地和时间比较充裕时采用。 分组循环是参赛队（人）较多时，采用种子法，把强队（人）分散在各组，先进行小组循环，再根据小组名次组织第二阶段的比赛。一般在参赛队人多，场地和时间较紧时采用。 （二）循环赛的优缺点 优点：参赛队机会均等，实战和相互观摩学习的机会多，能准确反映出参赛队之间真正的技术水平的高低，客观地排定参赛队的名次，比赛结果的偶然性和机遇小。 缺点： 1、比赛总的期限长，站用场地和时间多，当参赛队人多时，直接采用大循环有一定的困难，应用范围具有一定的局限性。 2、如何合理安排比赛的顺序，避免在比赛时间、间隙、地点、场次和比赛条件等方面出现不均衡现象。 3、当比赛结果有两个或两个以上队人的胜负场数相同，得失分相等时，如何根据不同项目的特点，科学地解决好最后的名次排定。 二、循环赛的轮数与场数计算 （一）循环赛的轮数 每个参赛队赛完一场（轮空队除外），称为一轮结束。计算循环赛的轮数的目的在于计划整个比赛所需要的时间和期限，是比赛日程安排的主要依据。 计算方法： 1、单循环 当N=2n时，Y=N-1 当N=2n-1时，Y=N （其中Y=轮次数，N=参赛对数） 2、双循环和多循环为单循环的倍数。 （二）循环赛的场数 循环赛的场数是指参赛队人之间相互轮流比赛全部结束 学年论文 题目循环赛日程表问题研究 学生 指导教师 年级2009级 专业软件工程 系别软件工程 学院计算机科学与信息工程学院 哈尔滨师范大学 2012年6月 论文提要 本文采用分治算法来解决循环赛日程表的安排问题。通过对问题的详细分析，列出1到10个选手的比赛日程表，找出两条规则，作为算法实现的依据，而后采用c语言实现算 法，通过测试分析，程序运行结果正确，运行效率较高。同时也介绍了循环赛日程表问题的另一种解法多边形解法，这种方法另辟蹊径，巧妙地解决了循环赛日程表问题，运行效率较高。 循环赛日程表问题研究 摘要：本文采用分治算法来解决循环赛日程表的安排问题。根据算法的设计结果，采 用c 语言实现算法，通过测试分析，程序运行结果正确，运行效率较高。同时也介绍了循环赛日程表问题的另一种解法，这种方法另辟蹊径，想法独特，运行效率较高。 关键词：循环赛日程表问题；分治法 一、题目描述 设有n 个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能赛一次； （3）当n 是偶数时，循环赛进行n-1天。当n 是奇数时，循环赛进行n 天。 二、问题分析 循环赛日程表可以采用分治法实现，把一个表格分成4个小表格来处理，每个小表格都是一样的处理方法，只是参数不同。分析过程具体如下： 1、n=1 （表2-1） 2.、n=2 （表2-2） 3、n=3 (1) 添加一个虚拟选手4#，构成n+1＝4 (2) 4/2＝2，分两组，每组各自安排（1 2），（3 4） (3) 每组跟另一组分别比赛（拷贝）这是四个人比赛的 （表2-3） 4人赛程 (4) 把虚选手置为0 （表2-4）3人赛程 1 1 2 2 1 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 西北农林科技大学信息工程学院《算法分析与设计》综合训练实习报告 题目：分治法循环赛日程表 学号 姓名 专业班级 指导教师 实践日期2011年5月16日-5月20日 目录 一、综合训练目的与要求 (1) 二、综合训练任务描述 (1) 三、算法设计 (1) 四、详细设计及说明 (3) 五、调试与测试 (4) 六、实习日志 (6) 七、实习总结 (6) 八、附录：核心代码清单 (6) 一、综合训练目的与要求 本综合训练是软件工程专业重要的实践性环节之一，是在学生学习完《算法分析》课程后进行的综合练习。本课综合训练的目的和任务： （1）巩固和加深学生对算法分析课程基本知识的理解和掌握； （2）培养利用算法知识解决实际问题的能力； （3）掌握利用程序设计语言进行算法程序的开发、调试、测试的能力； （4）掌握书写算法设计说明文档的能力； （5）提高综合运用算法、程序设计语言、数据结构知识的能力。 二、综合训练任务描述 假设有n=2k 个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次 （2）每个选手一天只能赛一次 （3）循环赛一共进行n-1天 利用Java语言开发一个界面，输入运动员的个数，输出比赛日程表。对于输入运动员数目不满足n=2k时，弹出信息提示用户。 三、算法设计 (1) 文字描述 假设n位选手顺序编号为1，2，3……n，比赛的日程表是一个n行n-1列的表格。第i行j列表示第i号选手在第j天的比赛对手，根据分治法，要求n个选手的比赛日程，只要知道其中一半的比赛日程，所以使用递归最终可以分到计算两位选手的比赛日程，然后逐级合并，得出结果。 (2) 框图 循环赛日程表 问题描述：设有n位选手参加网球循环赛，n=2^k，循环赛共进行n-1天，每位选手要与其他n-1位选手比赛一场，且每位选手每天比赛一场，不能轮空，按一下要求为比赛安排日程， （1）每位选手必须与其他n-1格选手格赛一场； （2）每个选手每天只能赛一场； （3）循环赛一共进行n-1天； #include int n=1; cout<<"请输入k值"< 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 题目：循环赛日程表 设计一个满足一下要求的比赛日程表 （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能赛一次； （3）若才赛选手为偶数，循环赛一共进行n-1天；若参赛选手为奇数循环赛一共进行n天。主要思想：“贝格尔”编排法,其优点是单数队参加时可避免第二轮的轮空队从第四轮起每场都与前一轮的轮空队比赛的不合理现象。 方法如下： 所谓贝格尔编排法，第一轮开始的编排同传统方法一样，假设现在有7个队参加单循环，分别抽签成为1-7队，由于贝格尔编排法必须是双数队，所以再加一个0队，与0队比赛表示该队轮空，现在必须定下一个数为参照数，因此我们假设0为参照数（任意数都可以，一般取0或者最大数），第一轮的对阵形式如下： 1 – 0 2 – 7 3 – 6 4 – 5 这个大家都能看明白，这跟贝格尔编排法无关，第二轮则开始相关了。在第一轮中，0在右边，现在我们要在第二轮让它换成左边，第三轮又让它换回右边，反反复复，到最后一轮即第七轮时，它还是在右边。我们把0安排好后，再把第一轮右下角的5提到右上角来，因此第二轮的第一场比赛就变成： 0 – 5 然后我们还要回到第一轮的八个数字来，我们假设它是一个环，无论是顺时针还是逆时针，它们的位置是相对固定的（除了它们与0的位置有时候会改变外，因为0的位置是先定好的），比如按照顺时针方向看，5的前面是6，后面是4，因此，第二轮我们还是安排5的前面是6，后面是4，0我们假设它不存在，于是第二轮的第一、二场比赛就是： 0 – 5 6 – 4 那其他怎么办呢，照旧轮呗，就像排球的轮转一样，于是第二轮就是 0 – 5 6 – 4 7 – 3 1 – 2 其他依次类推。 无论比赛队是单数还是双数，最后一轮时，必定是“0”或最大的一个代号在右上角，“1”在右下角。 根据参赛队的个数不同，应按规定的间隔数移动（见表）。 间隔移动 摘要 分治算法在实际中有广泛的应用，例如，对于n个元素的排序问题，当n = 1 时，不需任何计算；当n = 2 时，只要做一次比较即可排好序；当n = 3时只要做两次比较即可……而当n较大时，问题就不容易那么处理了。要想直接解决一个较大的问题，有时是相当困难的。分治算法的基本思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题，1 < k < n+1，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治算法就是可行的。由分治算法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易求出其解。由此自然引出递归算法。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 本次课程设计正是采用分治算法来解决循环赛日程表的安排问题。根据算法的设计结果，采用c语言实现算法，通过测试分析，程序运行结果正确，运行效率较高。 关键词：分治算法 目录 摘要 ..................................................................................................................... I 1 问题描述 (1) 2 问题分析 (2) 3 算法设计 (3) 4 算法实现 (7) 5 测试分析 (11) 结论 (12) 参考文献 (13) 1 问题描述 设有n位选手参加网球循环赛，n=2k，循环赛共进行n-1天，每位选手要与其他n-1位选手比赛一场，且每位选手每天比赛一场，不能轮空，按以下要求为比赛安排日程， 1)每位选手必须与其他n-1格选手格赛一场； 2)每个选手每天只能赛一场； 3)循环赛一共进行n-1天； 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行和第j列处填入第i个选手在第j天所遇到的选手，其中1≤i≤n,1≤j≤n-1。 循环赛日程表文档 一、问题描述： 设有n个运动员要进行循环赛。现要设计一个满足以下要求的比赛日程表： 1.每个选手必须与其他n-1个选手各赛一次； 2.每个选手一天只能参赛一次； 3.n是偶数时,循环赛在n-1天内结束。n是奇数时,循环赛进行n天. 二：程序源代码： #include a[n][i]=i; } } //输出表头 printf("\n "); for(j=1;j<=days;j++) printf("第%d天 ",j); printf("\n"); //输出比赛日程 for(i=1;i<=n;i++) { printf("第%d号 ",i); for(j=1;j<=days;j++) printf("%d ",a[i][j]); printf("\n"); } printf("\n"); system("pause"); } void Table ( int **a , int n) { int i,j,m1,m2; int *b; //指向对阵关系数组 //建立初始对阵关系（,n-1,2,n-2,...,i,n-i） b=new int [n]; //0下标不用 for(i=1;i<=n/2;i++) { b[2*i-1]=i; b[2*i]=n-i; } for(i=1;i<=n;i++)//i控制天数变化 { a[i][i]=0; //n为奇数时在第i天第i号运动员轮空 for(j=1;j<=(n-1);j+=2) { //第i天m1与m2对阵 m1=((b[j]+i)<=n)?(b[j]+i):(b[j]+i)%n; m2=((b[j+1]+i)<=n)?(b[j+1]+i):(b[j+1]+i)%n; a[m1][i]=m2; a[m2][i]=m1; } #include 单循环比赛日程安排 一、摘要： 本文在合理假设的基础上由问题的数学实质，建立出问题的模板模型，并根据问题的特殊性将模板分为奇数和偶数两种来研究，运用归纳的方法发现了列出矩阵后的特殊规律，根据这些规律得出一般模型，把模型与矩阵相对应，即得出日程安排的结果，并把模型一般化，使之能广泛应用于日程安排中，给出一个性能指标，用于判断日程安排是否公平、适合 对模型进行了推广。 二、问题重述： 1）七支球队进行单循环比赛，每天一场，每个队伍在两场比赛之间至少间隔一天， 2)若变成八支，九支，如何安排合理。能是两只球队至少 间隔两天吗。 3）推广到N支球队的比赛，如何安排，每支球队两场比赛之间至少间隔多少天。 4）你建议用那些指标衡量比赛日程的优劣，如何使这些指标达到最优。 三、建模假设： 1)每天的同一天进行比赛。 2)符号假设 i j 第i 队与第j 队比赛 [x]第x 场比赛 x(ij)第i 队与第j 队的比赛在第x(ij)场 N 球队的总支数 四、分析与建立模型: （1） 建模思路：首先用矩阵的方式把每场比赛列出来（顺序列出），从矩阵中的到一定规律，通过专业人士以前得出的日程安排概况，按一定规律建立一个模板，把矩阵与模板相应的值对应，比赛日期=比赛开始日期+x(ij)-1。 首先，建立一个关于x(ij)矩阵，i 代表行，j 代表列。 ???? ??? ???? ??? ??? ?? ? ? ?)77() 76() 75() 74() 73() 72()71()67()66()65()64()63()62()61()57()56()55()54()53()52()51()47()46()45()44()43()42()41()37()36()35()34()33()32()31() 27()26()25()24()23()22()21()17()16()15()14()13()12() 11(x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ii 这种情况不存在，ij 与ji 意义相同，为了简便，我们只看对角线上半部分， 既得： 南通大学 算法设计与分析 实验报告 姓名：鹿瑶 班级：软件工程122 学号：1213042037 日期：2014 . 12 . 16 目录 Question-2编程实现循环赛日程表（分治法） (3) Question-3编程实现最长公共子序列（动态规划） (3) Question-4 The Triangle（动态规划） (4) Question-5超级台阶（动态规划） (5) Question-6最大和（动态规划） (6) Question-7 剑客决斗（动态规划） (7) Question-8最长上升子序列问题（动态规划） (8) Question-9独木舟上的旅行（贪婪法） (9) Question-10背包问题（贪心算法） (10) Question-11田忌赛马（动规中的贪心算法） (10) Question-12硬币问题（贪心算法） (11) 附：源代码 (12) Question-2编程实现循环赛日程表（分治法） 描述 设有n=2 k 个运动员要进行网球循环赛，先要设计一个满足一下要求的比赛日常表： （1）每个选手必须与其他n-1 个选手各赛一次 （2）每个选手一天只能赛一次 （3）循环赛一共进行n-1 天 算法设计 将n*n个格子，也就是n阶方阵从中间十字划分，一次划分分成四块，令其右上角和左下角的数据完全相同，右下角和左上角的数据完全相同；每次划分都得到了若干个n/2阶的方阵，然后对这些方阵进行操作，继续令其右上角和左下角的数据完全相同，右下角和左上角的数据完全相同，如此循环下去，直至n<2时结束递归。 运行结果 Question-3编程实现最长公共子序列（动态规划） 描述 如题，需要你做的就是写一个程序，得出最长公共子序列。 tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列S ，如果分别是两个或多个已知序列的子序列，且是 所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。 输入 第一行给出一个整数N(0 要求：编写程序，用分治法求解循环赛日程表。 一、实验目的与要求 1、掌握网球循环赛日程表的算法； 2、初步掌握分治算法 二、实验题： 问题描述：有n=2^k个运动员要进行循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次 （2）每个选手一天只能赛一次 （3）循环赛一共进行n-1天 三、实验代码 #include 算法设计与分析实验报告循环赛日程表 一．问题描述 设有n位选手参加循环赛，设计循环赛日程表，要求： 每位选手必须和其余n-1个选手比赛； 每位选手每天只能比一场比赛； 若n为奇数，则比赛n天； 若n为偶数，则比赛n-1天。 二．实验目的 熟悉分治法的思想并掌握其运用。 三．实现方式 编译环境：Dev-C++ 算法思路： 使用分治法的思想，给n个选手安排日程表转化为给n/2个选手安排日程表，直到问题规模变成给两个选手安排日程。 日程表可以用一个二维数组表示，数组的大小为k （n<=2^k），第i行第j列的数组值表示第i个选手在第j-1 天比赛的对手（第1列表示选手的编号，假定选手的编号为1， 2，3…恰为数组的行数）。 划分：n个选手的日程表可以由n/2个选手的日程表合并而得。 解决：当只有两个选手比赛的时候，可以直接给出其日程表，得到一个2×2的数组。 当有4个选手参加比赛的时候，则将两个2×2的数组合并，得到一个4×4的数组。 以此类推，n 个选手的日程表由n-1个选手的日程表合并而成。合并规则为： 若n 为偶数，则会得到一个n ×n 的表格；若n 为奇数，需要比赛n 天，则会得到一个n ×（n+1）的表格且每一天必定有一位选手轮空。因此在合并的时候要先把表格扩充为（n+1）×（n+1）的表格，然后再消除虚拟的选手（用0表示轮空）。 例：n=3时赛程表为： 当n=6时，将两个n=3的赛程表合并，在同一天轮空的选手便可 在该天比赛。然后再补上表格右边的元素。 设当前要合并的数组的长度为s，表格左下角的元素可由左上角的元素+s而得： 表格右上角的元素由前一行决定： 表格右下角的元素由表格右上角对应元素所决定： /* *设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： *每个选手必须与其他n-1个选手各赛一次； *每个选手一天只能参赛一次； *xx在n-1天内结束。 *数组a[i][j]第i个选手在第j天所遇到的选手。*/ #include for(i=temp+1;i<=n;i++)//将左上角元素抄到右下角 for(j=temp+1;j<=n;j++) a[i][j]=a[i-temp][j-temp];}printf("参赛人数为: %d\n(第i行第j列表示和第i个选手在第j天比赛的选手序号)\n",n);for(i=1;i<=n;i++) for(j=1;j<=n;j++){printf("%d ",a[i][j]); if(j==n) printf("\n");}} void main(){int k; printf("比赛选手个数为n(n=2^k)，请输入参数K(K>0): \n"); scanf("%d",&k); if(k!=0) gametable(k);}循环赛的方法与编排
网球循环赛日程表
第一节 循环赛的方法与编排
循环赛日程表问题研究
(完整word版)分治法循环赛日程表实验报告
用C++编写循环赛日程表
算法分析实验报告--分治策略
单循环赛日程表
分支算法循环赛日程表课程设计
循环赛日程表_文档
循环赛日程表设计源代码
单循环比赛日程安排
算法实验二(题库)二
要求：编写程序,用分治法求解循环赛日程表。
循环赛日程表
循环赛日程表分治算法(c语言)
相关主题
文本预览