摘要
分治算法在实际中有广泛的应用，例如，对于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。
2 问题分析
运用分治法，将原问题划分为较小问题，然后由较小问题的解得出原问题的解。
1.分治法:对于一个规模为n的问题，若该问题可以容易的解决（比如说规模n较小），则直接解决，否则将其分解为k个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归的解决这些子问题，然后将个子问题的解合并，得到原问题的解。
2.分治法的解题步骤（由三个步骤组成）
?划分（divide）：将原问题分解为若干个规模较小、相互独立、与
原问题形式相同的子问题。
?解决（conquer）：若子问题规模较小，则直接求解；否则递归求
解各子问题。
?合并（conbine）：将各子问题的解合并为原问题的解
假设n位选手顺序编号为1，2，3……n，比赛的日程表是一个n行n-1列的表格。i行j列的表格内容是第i号选手在第j天的比赛对手。根据分而治之的原则，可从其中以半选手的比赛日程，导出全体n位选手的的日程，最终细分到只有两位选手的比赛日程出发。
3 算法设计
1.设计步骤：
1)先设计主函数(main函数)，然后设计两个函数，分别是安排赛事进行填制表格的函数（void Table(int n, int a[100][100])函数）和输出到屏幕函数（void Out(int n,int a[100][100])）。
2)在主函数(main())里调用void Table()函数，对比赛日程进行安排，根据分而治之原则，绘制比赛日程表格，然后调voidOut()函数，将安排好的比赛日程输出到屏幕上。
2.关键数据结构
1)运用一个二维数组a[i][j]，对安排好的赛事日程进行排列和保存，并在屏幕上输出。
2)使用二维数组的原因：因为根据题目要求，比赛日程表是一个n行n-1列的表格，用a[i][j]代表第i号选手在第j天遇到的对手，所以用一个二维数组表示。
3.程序结构
程序主要由三个函数组成：
1)main()函数（主函数）；
2)void Table()函数（本程序的核心函数）；
3)Out()函数（输出函数）
三个函数的程序结构如下所示：
1)main()函数
图3-1 2)void Table ()函数
图3-2
3)Out（）函数
图3-3
4 算法实现
关键程序功能及程序的说明如下：
1. main（）函数
（1）函数功能：在屏幕上输入k值，计算参赛人数n，然后调用void Table()函数和Out（）函数。
（2）函数实现：
①先定义一个k，然后在键盘上输入一个k值，并赋值给k（假设输入3）；
②运用for循环，计算参赛人数n的值
for (int i=1;i<=k;i++)
n *= 2;
可得n=8，即有八个人参赛。
③然后调用void Table()函数和Out（）函数，并传值。
2.void Table()函数
(1)函数功能：对所有运动员的赛程进行安排，并将其存入数组内。
(2)函数实现：由main（）函数得到k值为3，n值为8
①用一个for循环输出日程表的第一行
for(int i=1;i<=n;i++)
a[1][i] = i；
②然后定义一个m 值，m 初始化为1，m 用来控制每一次填充表格时i （i 表示行）和j （j 表示列）的起始填充位置。
③用一个for 循环将问题分成几部分，对于k=3，n=8，将问题分成3大部分，第一部分为，根据已经填充的第一行，填写第二行，第二部分为，根据已经填充好的第一部分，填写第三四行，第三部分为，根据已经填充好的前四行，填写最后四行。
for (int s=1;s<=k;s++) n/=2;
④用一个for 循环对③中提到的每一部分进行划分 for(int t=1;t<=n;t++)
对于第一部分，将其划分为四个小的单元，即对第二行进行如下划分：
同理，对第二部分（即三四行），划分为两部分，第三部分同理
⑤最后，根据以上
for 循环对整体的划分和分治法的思想，进行每一个单元格的填充。填充原则是：对角线填充
for(int i=m+1;i<=2*m;i++) //i 控制行
for(int j=m+1;j<=2*m;j++) //j 控制列
{ a [i][j+(t-1)*m*2] = a[i-m][j+(t-1)*m*2-m];/*右下角的值等于左上角的值 */
a[i][j+(t-1)*m*2-m] = a[i-m][j+(t-1)*m*2];/*左下角的值等于右上角的值*/
}
例：由初始化的第一行填充第二行
由s控制的第一部分填完。然后是s++，进行第二部分的填充
1 2 3 4 5 6 7 8
2 1 4
3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
最后是第三部分的填充
⑥这样循环，直到填充完毕，a[][]数组被赋予新值。
3.Out（）函数
（1）函数功能：将安排好的赛事日程，即二维数组a[n][n-1]输出到屏幕。
（2）函数主要功能实现：
函数主要运用一个for循环，将二维数组a[n][n-1]输出到屏幕。
for (i = 1; i<= n; i++)
{ for (j = 1; j<= n; j++)
{
printf("%4d", a[i][j]);
} printf("\n");
} printf("\n");
5 测试分析
程序编译成功后，执行程序，在提示下输入k值，程序即可算出参赛的队员人数n（n = 2k），同时屏幕显示我们需要的循环赛日程表，程序运行结果如图5-1所示：
图5-1
结论
程序主要运用了：数据输入、函数调用、函数传值、for循环以及二维数组等主要结构和功能。根据分治算法，将本问题进行了由小规模到大规模的求解设计，程序设计的关键点在于如何对问题进行划分和填充公式的归纳。在划分时，主要运用了两个for循环；在填充时，运用了两个for循环。
通过这次程序设计，加深了对分治算法的认识。解决具体问题时，程序故重要，但一个好的算法更加重要。
本程序的得意之处在于，经过仔细研究，找到了划分的方法，并推导出了表格填充的两个公式。不足之处也在此，即花费了很长时间来推导这个，对算法掌握还不够熟练。
参考文献
[1] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2007：102-121.
[2] 严蔚敏吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997：
170-179.
[3] 谭浩强.C程序设计(第三版) [M].北京：清华大学出版社，2005：1-378.
[4]王志刚李卫华著.需求工程导引[M].北京：人民邮电出版社，2003.
[5] 陆惠恩著.实用软件工程[M].北京：清华大学出版社，2006.
[6] 吕凤翥著.C++语言基础教程（第二版）[M].北京：清华大学出版社，2007.
单循环比赛的编排方法 单循环制参加比赛的各队之间均相互比赛一次,即为单循环赛。 (1)单循环赛的比赛场数计算公式:场数=队数(队数-1)/2 (2)单循环赛的比数轮数计算方法:参赛队为奇数时,比赛轮数等于队数; 参赛队为双数时,比赛轮数等于队数减1。 (3)单循环赛的编排方法: ①一般编排方法。采用“逆时针轮转方法”进行编排,先以阿拉伯数字作 为代号,代替队名进行编排。把队数按U型走向分成均等两边,如遇单数队, 最后一位数字补为O成为偶数。第一轮只要在U形相对队数之间划横线, 即为第一轮比赛秩序。第二轮开始固定左上角1数字,其余数字均按逆时针 方向移动一个位置,即为第二轮比赛秩序,以后各轮比赛秩序以此类推。遇 O队数即轮空队。 例如,有9个队参加比赛,比赛秩序编排如下所示: 第一轮二轮三轮四轮五轮六轮七轮 八轮九轮 1—0 1—9 1—8 1—7 1—6 1—5 1—4 1—3 1—2 2—9 0—8 9—7 8—6 7—5 6—4 5—3 4—2 3—0
3—8 2—7 0—6 9—5 8—4 7—3 6—2 5—0 4—9 4—7 3—6 2—5 0—4 9—3 8—2 7—0 6—9 5—8 5—6 4—5 3—4 2—3 0—2 9—0 8—9 7—8 6—7 采用逆时针轮转法编排的优点,是参赛各队比赛进度一致,编排方法简单, 易操作、检查。但当单数队在5个队以上时,抽签为倒数的第二数字队则在 第四轮开始每轮均同上轮轮空队进行比赛,如上述的数字8代表的队。由此 产生了球类比赛中的不公平竞争现象。为了解决这一问题,目前的比赛大 多采用“贝格尔编排方法”。 贝格尔编排法? 从1985年起，世界性排球比赛多采用“贝格尔”编排法。其优点是单数队参加时可避免第二轮的轮空队从第四轮起每场都与前 一轮的轮空队比赛的不合理现象。 采用“贝格尔”编排法，编排时如果参赛队为双数时，把参赛队数分 一半(参赛队为单数时，最后以“0”表示形成双数)，前一半由1号开始， 自上而下写在左边；后一半的数自上而下写在右边，然后用横线把相对的 号数连接起来。这即是第一轮的比赛。 第二轮将第一轮右上角的编号(“0”或最大的一个代号数)左角上，第 三轮又移到右角上，以此类推。即单数轮次时“0”或最大的一个代号在
循环赛的方法与编排 一、循环赛的种类与特点 （一）循环赛的种类 循环赛又称循环法。是指参赛队（或个人，下同）之间，都要互相轮流比赛，最后按照各参赛队在全部比赛中的胜负场数、得分多少排定名次的比赛方法。它在对抗性项目比赛中经常被采用。循环赛包括单循环、双循环或分组循环三种。单循环是所有参赛队（人）相互轮赛一次；双循环是所有参赛队（人）相互轮赛二次；分组循环是参赛队（人）较多时，采用种子法，把强队（人）分散在各组，先进行小组单循环赛，再根据小组名次来组织第二阶段的比赛。主办单位可根据参赛队多少和比赛期限的长短以及项目特点而灵活选用。一般情况下，单循环宜在参赛队不太多，比赛时间与场地又比较充裕时采用；分组循环大多是在参赛队数多，比赛时间又不能过长，并尽量为参赛队提供比赛机会，使比赛能较合理地排定名次时采用。 （二）循环赛的特点 采用循环法进行比赛，总的优点是参赛队机会均等，实战和互相观摩学习的机会多，能准确地反映出参赛队之间真正的技术水平的高低，客观地排定参赛队的名次，比赛结果的偶然性和机遇性小。上述优点正是淘汰赛的主要缺点，但循环赛自身也存在有某些不足与矛盾，应引起组织者的重视。 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)/2,如有五支球队或六支球队参加比赛,比赛场数分别为5＊(5—1)/2=10(场)与6 ＊(6-１)/２=1５(场) 。 比赛轮数:参加比赛得队数为单数时,比赛轮数等于队数。如5个队参加比赛,即比赛轮数为5轮。参加比赛得队数为双数时,比赛轮数等于队数减一。如６个队参加比赛,则比赛轮数为6－1=5轮。 用逆时针旋转编排方法列出6队参加比赛得对阵轮次与场次如下: 一二三四五 １—６1—5 1—４1-３１-2 ２—5 ６-4 5－3 4－2 3－6 3-42—３６-2 ５—6 4—５ 如上表:共有5轮,15场比赛。 篮球赛有１０队参加比赛,请计算出比赛得场数,轮次,并编排比赛得轮次表,以单循环为例 10队分别数字代替。 第一轮 1—2 3—10 ４－9 5－８6－7 第二轮 1-３2－4５－106—9７-8 第三轮 1－42-6 ３-5 ７—1０８－9 第四轮 1－5 ２—83-7 ４-6 9-10 第五轮 1-６2—1０3－９4—8 5－７ 第六轮 1-7 ２—3 ４—105-96—８ 第七轮 1－8 2-5 ３—4 ６—1０7－9 第八轮 1-9 2-７3－6 4－5 8－10 第九轮 １－10２-9 3—８４－7 5-6 共分为九轮比赛,每轮五场赛事,一共4５场。 篮球赛有７队参加比赛,请计算出比赛得场数,轮次,并编排比赛得轮次表,以单循环为例 7支球队参加,每一轮必然有一队轮空、假设球队代号分别为Ａ至G,轮次表如下: 第一轮: A—--B C——-D E——－F Ｇ轮空 第二轮: A-——C 题目：循环赛日程表 设计一个满足一下要求的比赛日程表 （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”在右下角。 根据参赛队的个数不同，应按规定的间隔数移动（见表）。 间隔移动 （二）双循环赛的编排方法 双循环赛比赛轮次表的排法与单循环相同，只要排出第一循环，第二循环可按表重复一次（表3），也可重新抽签另排位置。第二循环的比赛如何进行，应在竞赛规程中明确规定。双循环赛的轮次与场次，均为单循环的一倍。 表3 5个队参加双循环比赛轮次安排表 第一轮第二轮第三轮第四轮第五轮 第一循环0——50——40——30——20——1 1——45——34——23——12——5 2——31——25——14——53——4 第二循环0——50——40——30——20——1 1——45——34——23——12——5 2——31——25——14——53——4 （三）分组循环赛的编排方法 分组循环通常分预赛和决赛两个阶段。 1.预赛阶段 按规程规定将参赛队分为几个小组，各组参照单循环编排，排出小组比赛表，然后确定种子队的位置。分组循环赛一般按分组数或分组数的2倍数确定种子，若种子数与组数相等，则将种子队分别安排在各小组的1号位置，如种子队为组数的2倍，应采用“蛇形”排列法，将种子队依次排列在各小组的1、2号位置上，非种子队也应抽签后定位。现将分组单循环赛抽签和“蛇形”排列法介绍如下： （1）首先在联席会上协商确定种子队：种子队数一般等于组的组数。如果分4个组进行比赛，应有4个种子队。为了使比赛更合理，也可以多选出几个种子队，但必须是组数的倍数。如分4个组进行比赛，可确定8个种子队。第一号种子队与第八号种子队编为一组；第二号种子队与第七号种子队编为一组，依此类推。 （2）抽签方法：种子队先抽签，确定各种子队的组别，然后其他各队再抽签确定组别。 例如，20个队分为4组，除8个种子队外，其他12个队再抽签。签号分为4组，每组有相同的3个签，由12个队抽签确定组别，然后再把各队按组别填入各组的比赛轮次表中。另外一种分组方法为蛇形排列分组，即按上一届名次进行分组。例如，有16个队分为4个组时，其排法如表4： 表4 16个队分4组比赛安排表 第一组第二组第三组第四组 1234 8765 9101112 16151413 2.决赛阶段 各队在预赛阶段分组单循环赛中的名次，将决定其进入决赛阶段比赛的位置。在预赛阶段已经相遇过的队，比赛成绩依然有效，决赛阶段不再进行比赛。其常用的比赛方法有，同名次赛、分段赛、交叉赛、录取名次赛等。 （1）同名次赛：就是将各小组预赛中相同名次编在一起进行比赛，如预赛时四个组的第一名编成一组进行单循环赛，决出1～4名，各小组的第二名编在一起决出5～8名。 （2）分段赛：将各小组的名次分为几段，同一段名次的队编在一组决出总名次，如预赛两个组的1、2名编在一起决出1～4名，两个组的3、4名，编在一起排出5～8名。 （3）交叉赛：各组的前两名交叉比赛，两场胜者进行决赛争夺1、2名，两场负者再相互比赛决出3、4名，各组3、4名用同样方法决出5～8名，其余类推。 （4）录取名次赛：根据竞赛规程规定的录取名次，在各小组中取录数量相等的队进入决赛（参加第二阶段决赛队的数量应等于或略高于录取名次的队）。例如，有16个队参赛，规定录取前8名，预赛分成两个组，则每组前4名的队，进入第二阶段决赛，其余的队不再比赛。 （四）循环比赛日程编排的注意事项 循环赛要求每个参赛队（人）和其他参赛队之间都要进行比赛。从比赛对象上看，保证了参加者均等的机会，但在比赛顺序和比赛条件上仍存在着机会不均等的问题。如与强、弱对手相遇时间的先后问题；实力相近两队之间决定性比赛前，各自体力消耗多少的问题（指各自在前一场比赛对手的强弱和休息间隔时间的不均等）；各参赛队比赛进度先后不一致问题；比赛场地条件的优劣及对场地条件适应能力等问题。要做到各方面条件完全均等是不可能的，但在编排中应尽量使这些不均等因素降到最低限度，使整个比赛获得更好效果。 摘要 分治算法在实际中有广泛的应用，例如，对于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; } 篮球运动竞赛工作包括竞赛的组织形式和竞赛的编排方法。组织形式有赛会式，如奥运会篮球比赛，世界篮球锦标赛，全运会篮球赛等。赛季式，如NBA篮球赛，甲A篮球联赛，甲B篮球联赛等。竞赛的编排方法有淘汰法、循环法和混合法三种。本章节主要介绍竞赛的编排方法。 一、淘汰法 淘汰法分单淘汰和双淘汰两种。单淘汰是指在比赛中失败一次即被淘汰，获胜者继续比赛直到决出冠亚军为止。双淘汰是指在比赛中，失败一次后，仍可与另一失败一次的队进行比赛，再次失败即被淘汰，获胜队继续比赛，直到决出冠亚军为止。 淘汰法一般是在比赛时间短、参加队数多、经费不足的情况下采用，能节省时间。但除了第一名以外，不能合理地确定其余各队的名次，比赛机会少，胜负有一定偶然性，目前很少采用。 （－）单淘汰法的编排1、场数=参加队数- 1 轮次=参加队数的以2为底的幂的指数，如8个队参加比赛，即为三轮，因为8=23；如果参加比赛的队数不足2的乘方数，则比赛的轮次是稍大的一个以2为底的幂的指数。如，14个队参加比赛，按l6个队的轮数来计算，因为16=24，即为四轮。 2、用（N=2n）*2的公式计算。N代表队数，2n代表略小于队数的2的乘方数。如13个队参加比赛，即（N－2n）*2=(13－8)*2=5*2=10，有10个队参加第一轮比赛，3个轮空。 3、如果参加比赛的队数是2的乘方数，就按照图15－2－l逐步进行淘汰。 如果参加比赛的队数不是2的乘方数，要根据参赛队数，选择最接近的、较大的2的乘方数作为号码位置数，号码位置数减去参加队数，即为轮空队数。如，13个队参加比赛，选用16为号码位置数。16－13=3，即3个轮空。可选2．5。10为轮空的号码位置。 轮空队员必须安排在第一轮，可采用抽签来决定轮空队，也可没种子队再确定种子队轮空的区位，为了避免水平高的队过早相遇而被淘汰，可设种子队，把种子队安排在不同的位置上，使之最后相遇。采用抽签的方法确定其他各队在秩序表上的位置，再填上队名、日期、场地、时间即成为比赛日程表。 〔二）双淘汰法的编排 双淘汰法的编排与单淘汰法的不同在于比赛进入第二轮后，把失败的队员再编排起来继续比赛，再次失败的队则被淘汰，胜者继续与上一轮失败的队进行比赛，只失败一次的队还能参加决赛，并有可能夺取冠军。（图15－2－3） #include 算法分析实验报告--分治策略
篮球单循环比赛排列方法
单循环赛日程表
双循环赛的编排方法
分支算法循环赛日程表课程设计
循环赛日程表_文档
篮球比赛编排方法
循环赛日程表设计源代码
相关主题
文本预览