循环赛日程表_文档

一、问题表述：设有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天。

如图：12345678012345678对称轴此时n=9，为奇数，从0开始每天有一个人轮空对称轴b) 当n 为偶数时，取出编号最大的，其他的组成一个正多边形，n 号一次顺序与1,2，。

n -1号选手比赛，其他与a ）相同。

如图所示：（图中是从0开始编号）123456789 9N=2k 时9三、 理论分析算法及实现1. 算法一：使用分治法a) 算法的思路：按分治策略，可以将所有的选手对分为两组（如果n 是偶数，则直接分为n/2每组，如果n 是奇数，则取（n+1）/2每组），n 个选手的比赛日程表就可以通过为（n/2或（n+1）/2）个选手设计的比赛日程表来决定。

循环赛日程表问题描述：设有n位选手参加网球循环赛，n=2^k，循环赛共进行n-1天，每位选手要与其他n-1位选手比赛一场，且每位选手每天比赛一场，不能轮空，按一下要求为比赛安排日程，（1）每位选手必须与其他n-1格选手格赛一场；（2）每个选手每天只能赛一场；（3）循环赛一共进行n-1天；#include<iostream.h>int a[50][50];void table (int x,int k)//此函数为从x号球员起的共2的k次方名球员的安排日程表{int i,j,y=1;if(k==1)//只有两名球员{a[x][0]=x;a[x][1]=x+1;a[x+1][0]=x+1;a[x+1][1]=x;}else{for(i=1;i<=k-1;i++){y=y*2;}table(x,k-1);table(x+y,k-1);for(i=x;i<x+y;i++){for(j=y;j<2*y;j++)a[i][j]=a[i+y][j-y];}for(i=x+y;i<x+2*y;i++){for(j=y;j<2*y;j++)a[i][j]=a[i-y][j-y];}}}void main(){int i,j,k;int n=1;cout<<"请输入k值"<<endl;cin>>k;for(i=1;i<=k;i++){n=n*2;}cout<<"参赛人数"<<" "<<n<<endl; table(1,k);cout<<"*****循环赛日程表****"<<endl;cout<<endl;cout<<"日期:";for( i=1;i<n;i++)cout<<" "<<i;cout<<endl;for(i=1;i<n;i++){cout<<endl;for(j=1;j<n;j++)cout<<" "<<a[i][j]<<" ";}cout<<endl;}执行结果如下：。

循环赛轮转表常用循环赛轮转表四队轮转表六队轮转表八队轮转表轮次 1桌 2 桌轮次 1桌 2桌 3桌轮次 1 桌 2 桌 3桌 4桌 1轮 1 -4 2- 3 1轮 1-4 2-6 3- 5 1轮 1-4 2-63-8 5- 7 2轮 3 -1 4-2 2轮3-2 5- 4 6-1 2轮 5- 38-47-2 6- 1 3轮 1- 2 3-4 3轮1- 5 6- 3 4-2 3轮 6-7 2- 31-8 4-54 轮 4-6 2- 53-1 4轮 5-8 1-7 2-43-65 轮 1- 2 3- 4 5-6 5 轮 7-36-4 1- 5 8- 26轮8-62-5 4-7 3-17轮1- 2 3- 4 5- 6 7-8十队轮转表十二队轮转表轮次 1 桌 2 桌 3桌 4桌 5 桌轮次1桌 2桌 3桌 4桌 5桌 6桌 1轮7-9 5 -10 3-8 1-42-6 1 轮 1- 4 3-8 7- 12 9-11 2- 6 5- 10 2轮 10- 2 8 -4 6-1 7-5 9- 3 2轮 10 -2 9-7 8- 46-1 11 - 5 12- 3 3轮 4 -9 3- 5 2- 7 6 -10 1 -8 3轮 4 - 12 6 -10 2 -11 5-7 3- 9 1-8 4轮 10 -1 7-6 9-83-2 5-4 4 轮 5-3 9-4 10 -1 12- 8 11 -6 7-2 5轮8-5 4-2 10-7 1 -9 6-3 5轮8 -9 1- 12 6- 710-11 2 -3 4- 5 6轮4-6 7- 1 5-9 3-10 2 -8 6轮 7 -10 5-89-12 2- 4 11-1 3- 6 7轮 7-3 9-2 10 -4 8 -61-5 7轮6 -4 11-7 10 -3 1- 912-5 8- 2 8轮 6 -9 8-10 3-1 2- 5 4- 7 8轮 5-9 6-8 2-123-11 7-1 4-10 9轮 1-2 3- 4 5- 6 7-8 9 -10 9轮 7-3 9-211-4 12- 6 10 -8 1- 510轮8-11 10- 12 3 -1 2-5 4-7 6-911 轮 1-2 3-4 5-67-8 9-10 11 -121十四队轮转表轮次 1桌2桌 3桌 4桌5桌 6 桌 7 桌1轮3-8 2-6 1-45-10 7-12 9-14 11 -132轮14-5 8-4 11-9 13 -7 6-1 12-3 10 -23轮 4 -123-13 2-14 1-8 5-116-10 7-94轮 11 -2 10-112-8 13-4 9-37-5 14 -65轮 1 -122-7 3-5 6 -11 10 -14 4-9 8 -136轮 7-6 9-8 11 -10 3-2 13-12 14 -1 5 -47轮8-5 10 -712-9 14 -114-2 1 -13 6-38轮 9-13 11-14-6 3-10 7 -14 2-8 5-129轮14-3 12 -2 11-7 1 -9 8-6 13-5 10 -410轮 6-12 5 -9 2 -13 4 -143-11 8 -10 7-111轮11-4 13 -6 14-8 12-10 1 -5 7-39-212轮10-13 12 -14 3-12-5 4-7 6-9 8-1113轮 1 -2 3-45-6 7-8 9 -1011-1213 -14十六队轮转表轮次1桌2 桌 3桌 4桌5桌 6桌 7桌 8桌 1轮 9 -14 13-155-10 1-4 3-811-16 2-6 7 -12 2轮 6 -1 16 -7 13 -11 15 -910-2 14 -5 12 -38-4 3轮7-13 9 -11 2-14 4 -12 3-16 1-86-10 5 -15 4轮 16-414-6 12-8 13-311-5 15-2 9 -7 10 -1 5轮 3-9 5-7 4-13 10-14 6-15 8 -161-12 2 -11 6轮 11-616-12 7-2 5-314-1 9 -415-10 13-8 7轮4-5 2-3 1-16 14 -1512-13 10 -11 8 -9 6-7 8轮 13-16 11-149-12 7 -10 5 -8 3-62-4 15-1 9轮 14 -7 12 -5 10 -3 8-26-4 1-1315-11 16-9 10轮 2- 12 4-10 6-8 11-19-13 7-15 5-16 3-14 11轮 10 -8 1 -9 11 -715-3 16-213-5 14-4 12 -6 12轮3-112 -13 4-15 6-16 8 -14 10 -12 7-1 5-9 13轮 13 -6 15 -8 16-1014-12 1-5 7-3 9-2 11-4 14轮 12-15 14-163-1 2-5 4-7 6-9 8 -11 10 -13 15轮1-23 -4 5-6 7-8 9 -10 11 -1213-14 15 -162十八队轮转表轮次 1桌2桌 3 桌 4桌 5 桌 6桌 7桌 8 桌 9桌1轮 5 -10 9-14 7-12 11-16 2 -6 13 -18 1 -4 15-17 3 -82轮 18-9 16 -7 17-1115-13 6-1 14-5 8 -412-3 10-23轮 11 -13 1-85-18 4 -12 9 -15 3 -166-10 2 -147-174轮12-8 17 -3 14-615-5 16-4 10-1 13 -7 11 -918-25轮4-17 2 -15 8 -16 6-18 3-13 7-9 5-11 1-12 10-146轮 16-12 13-411-2 14-118 -10 15-6 9 -3 7-517-87轮 2 -7 6 -1110-15 4-9 8 -13 12 -173-514 -18 1- 168轮 18 -1 9 -8 3-2 13 -12 17 -16 15-147-611 -10 5-49轮 16 -13 14 -11 1-17 6-310-7 4-2 18-15 8-512-910轮 4-6 5-12 7-14 11 -182-8 3 -10 13-17 9-16 15-111轮 14 -3 16 -5 10 -417-915 -11 1- 13 12 -28-6 18 -712轮8-10 7 -159-13 11-1 6-12 2-16 5 -173-18 4 -1413轮 11-7 1-9 14-8 12-1015-3 13 -5 18-417-2 16-614轮5-92 -13 4 -15 6-17 12 -14 8- 18 10-167-1 3 -1115轮 15-8 17-1018-1216 -14 1 -5 7-3 9-2 11-413-616轮 14-17 16-18 3-1 2-5 4-7 6-98-11 10-13 12 -1517轮 1 -23-4 5-6 7-8 9-1011-12 13 -1415-16 17 -18二十队轮转表轮次1桌 2 桌 3 桌 4桌 5 桌6桌 7桌8桌 9 桌 10桌 1轮3-85 -10 15 -20 9-14 7-12 17 -1913-18 2 -6 1-4 11 -16 2轮14-519 -13 18-9 17 -15 10 -2 20-11 6-1 8-4 16 -7 12-3 3轮 7-20 4-1211-17 6- 101-8 13 -15 3-16 5-18 2-149-19 4轮 15 -9 13 -11 10 -112-8 14-6 16 -4 18 -220-3 19 -517-7 5轮10-14 8 - 16 6 -18 4-20 2 -193-17 5-15 7-13 9-111-12 6轮20-819 -6 17-4 15-213-3 11-5 9-7 14 -116-1218 -10 7轮 6-154-13 2-11 3 -95-7 1 -16 14 -18 12 -2010-198 -17 8轮 9-47-2 5-318-1 20-16 19 -14 17-1215-1013 --811 -6 9轮 2-3 1-20 18-19 16-17 14 -15 12-13 10-11 8-9 6-7 4-5 10轮 17 -20 15-18 13-16 11 -14 9- 127-10 5-8 3-6 2-4 19-1 11轮 18 -11 16 -914-7 12-510-3 8-2 6-41-17 19 -15 20-13 12轮 5- 16 3-14 2 -124-10 6-8 15-1 13-17 11-19 9- 207-18 13轮14-412 -6 10 -8 1 -13 15 -11 17-9 19-7 20 -518-3 16 -2 14轮 10 -1211-1 9 -137-15 5 -17 3-19 2 -20 4 -186-16 8-14 15轮 13-5 15-3 17 -219-4 20 -6 18 -8 16 -10 14 -12 1-9 11-7 16轮 4-156-17 8-1910-20 12 -1814-16 7-15-9 3-112-13 17轮 17 -10 19 -12 20 -14 18 -161-5 7-39-2 11-4 13 -6 15 -8 18轮 16-19 18-20 3-1 2-5 4-7 6-9 8-11 10 -13 12-15 14 -17 19轮 1-2 3-4 5-67-8 9-10 11-12 13-14 15-16 17 -18 19 -2034。

利用分治法设计循环赛日程表摘要:对于单循环赛的比赛日程安排问题,利用分治算法给出了可读性较好的设计，并分析了各种假设下的时间复杂度。

关键词:分治算法;复杂度;递归;循环赛引言任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。

问题的规模越小，越容易求解，所需的计算时间也越少。

分治法是计算机科学中经常使用的一种算法。

设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

1分治法应用条件及一般步骤1.1 分治法的应用条件1.1.1能将n个数据分解成k个不同子集合，且得到的k个子集合是可以独立求解的子问题，其中11&&odd(n/2)) copyodd(n);else copy(n);}void copyodd(int n){int m=n/2;for(int i=0;i=m){a[i][j]=b[i];a[m+i][j]=(b[i]+m)%n;}else a[m+i][j]=a[i][j]+m;}for(j=1;j<m;j++){a[i][m+j]=b[i+j];a[b[i+j]][m+j]=i;}}}分析算法的时间性能:当n/2为奇数时，基本语句的执行次数是：当n/2为偶数时，基本语句的执行次数是：综上，时间复杂度为O(4k )。

2.3 运行结果及分析当输入n为2时，输出：0 11 0在上面n=2时的日程表（二维表）中，左边第一列表示球队编号，第二列表示在某天碰到的对手球队的编号。

推广之，对于n行n列的二维日程表，那么，a[0][0]，a[1][0]，……，a[n-1][0]表示参加循环赛的n支球队的编号；a[0][1]，a[0][2]，……，a[0][n-1]表示球队a[0][0]在第1，2，……,n-1天碰到的对手球队编号。

a[i][j]（i,j<n）表示编号为a[i][0]的球队在第j日遇到的对手球队的编号。

以下同。

附件二【学生用】《算法分析与设计》综合训练实习报告题目：利用分治思想设计循环赛日程表学号姓名专业班级指导教师实践日期目录一、综合训练目的与要求 (1)二、综合训练任务描述 (1)三、算法设计 (1)四、详细设计及说明 (3)五、调试与测试 (5)六、实习日志 (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=2^k ，求出kNNYNYNYYNYint i=1i<=Ni++a[1][i]=ii++m=1s=1s<=k?N=N/2int t=1t<=N?int i=m+1i<=2*mj=m+1j<=m+1a[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]j++i++t++s++ m=m*2结束(3)伪代码public static void Table(int n,int[][]a) {int b = 2;n = saicheng.x;//参赛人数int k=(int) (Math.log(n)/Math.log(b)); //计算输入值是2的几次幂for(int i=1;i<=n;i++){a[1][i]=i;//打印出第一行即选手1的赛程表}int m=1;//控制每一次填充表格时i（i表示行）和j（j表示列）的起始填充位置for(int s=1;s<=k;s++){n/=2;//将问题分成k部分for(int t=1;t<=n;t++)//对每一部分进行划分{for(int i=m+1;i<=2*m;i++)//控制行{for(int j=m+1;j<=2*m;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];//左下角等于右上角}}}m*=2;}}四、详细设计及说明1.输入一个数字n，根据（x&（x-1））==0判断n是否等于2^k。

循环赛⽇程表（Java实现） 1/**2 * 循环赛⽇程表：有n = 2^k个运动员要进⾏⽹球循环赛3 * 赛程表满⾜：4 * 每个选⼿必须与其他n-1个选⼿各赛⼀次5 * 每个选⼿⼀天只能参赛⼀次6 * 循环赛在n-1天内结束7 *8 * 解题思路：9 * 将⽐赛⽇程表设计成⼀个n⾏和n-1列的表，第i⾏，第j列分别填⼊第i个选⼿在第j天所遇到的选⼿10 * 栗⼦：11 * 4个选⼿12 * ---------13 * |1|2|3|4|14 * ---------15 * |2|1|4|3|16 * ---------17 * |3|4|1|2|18 * ---------19 * |4|3|2|1|20 * ---------21 * 分治思想：将所有区域看成四块，区域1：(0,i) 区域2：(0,r+i) 区域3：(r,i) 区域4：(r,r+i)22 * 递归执⾏的是区域1拷贝到区域4，区域2拷贝到区域323 * ---------24 * | 1 | 2 |25 * ---------26 * | 3 | 4 |27 * ---------28 * * @author焦含寒29 *30*/31public class Roundrobin {32public static int[][] table(int k){33int n = 1<<k;34int[][] a = new int[n][n];35//构造赛程表第⼀⾏数据36for(int i = 0; i<n;i++)37 a[0][i] = i+1;38//采⽤分治算法，构造整个赛程表39for(int r = 1;r<n;r<<=1){40for(int i =0;i<n;i += 2*r){41 copy(a,r,r+i,0,i,r);42 copy(a,r,i,0,r+i,r);43 }44 }45return a;46 }4748private static void copy(int[][] a, int tox, int toy,49int fromx, int fromy, int r){50for(int i =0;i<r;i++){51for(int j = 0;j<r;j++){52 a[tox+i][toy+j] = a[fromx+i][fromy+j];53 }54 }5556 }57585960public static void main(String[] args) {6162int[][] a = table(4);63for(int i=0;i<a.length;i++){64for(int j = 0;j<a[0].length;j++){65 System.out.print(a[i][j] + "ss ");66 }67 System.out.println();68 }6970 }7172 }。