循环赛日程表问题研究讲解

1、学年论文题目循环赛日程表问题研究学生指导教师年级2009级专业软件工程系别软件工程学院计算机科学与信息工程学院哈尔滨师范大学2012 年 6 月论文提要本文采用分治算法来解决循环赛日程表的安排问题。通过对问题的详细分析，列出 1到 10 个选手的比赛日程表，找出两条规则，作为算法实现的依据，而后采用 c 语言实现算 法，通过测试分析，程序运行结果正确，运行效率较高。同时也介绍了循环赛日程表问题的 另一种解法多边形解法， 这种方法另辟蹊径， 巧妙地解决了循环赛日程表问题， 运行效率较循环赛日程表问题研究摘 要：本文采用分治算法来解决循环赛日程表的安排问题。 根据算法的设计结果， 采 用 c 语言

2、实现算法，通过测试分析，程序运行结果正确，运行效率较高。同时也介绍了循环赛日程表问题的另一种解法，这种方法另辟蹊径，想法独特，运行效率较高。关键词： 循环赛日程表问题；分治法、题目描述设有 n 个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表：1) 每个选手必须与其他 n-1 个选手各赛一次；2) 每个选手一天只能赛一次；3) 当 n 是偶数时，循环赛进行 n-1 天。当 n 是奇数时，循环赛进行 n 天。、问题分析循环赛日程表可以采用分治法实现， 把一个表格分成 4 个小表格来处理， 每个小表格都 是一样的处理方法，只是参数不同。分析过程具体如下：1、n=1表 2-1)2. 、 n

3、=2表 2-2)1212213、n=3(1) 添加一个虚拟选手 4#，构成 n+1 4(2) 4/2 2，分两组，每组各自安排( 1 2)，(3 4)(3) 每组跟另一组分别比赛(拷贝)这是四个人比赛的(4) 把虚选手置为 01234214334124321表 2-3 ) 4 人赛程表 2-4)3 人赛程12302103301230321这是三个人比赛的安排4、n=4，见表 2-35、n=5(1) 加一个虚选手， n+1=6 。安排好 6 个人的比赛后，把第 6 个人用 0 表示即得 5 人的。(2) 分成两组 (1 2 3) (4 5 6)，各 3名选手(3) 依照表 2-4，安排第 1组；

4、按表 2-5安排第 2组(除 0元素外，都加 3)表 2-5)4560540660450321(4) 把表 2-5 排于表 2-4 下方表 2-6)123021033012456054066045(5) 把同一天都有空的两组安排在一起比赛 (按这种安排， 肯定每天只有一对空组 )。表 2-7)123421533612456154266345(6) 第一组的 (1 2 3)和第 2组的(4 5 6)分别比赛。 但是由于 (1,4), (2, 5), (3 6)已经比赛过了，所以在后面的安排中不能再安排他们比赛。1 2 34 5 6首先， 1# 只能和 5#或 6#比赛。3#4#3#5#把 6 换

5、成 0，(a) 若 1#5#，由于 3#和 6#已经比赛过，所以只能安排 : 2#6#，(b) 若 1# 6#，由于 2#和 5#已经比赛过，只能安排：2#4#，这样安排后前三行的后两列，后三行的后两列由上面的三行来定：表 2-8) 6 人赛程123456215364361245456132542613634521表 2-8 就是 6 名选手的比赛日程安排。将其中的 6 号作为虚拟选手， 即得 5 名选手的赛程安排表：表 2-9 )5 人赛程1234502153043012454501325420136345216、n=6 ，见表 2-8。7、n=7, 添加 1，n+1=8。8名选手的安排，由

6、 4 名选手(表 2-3)构成表 2-10) 8 人赛程1234567821436587341278564321876556781234658721437856341287654321将其中的 8 改成 0，即得 7 名选手的赛程安排。表 2-11) 7 人赛程12345670214365073412705643210765567012346507214370563412076543218、n=8 ，见表 2-10。9、n=9，由 n+1 10人，将虚选手 10 号置为 0来得到。10、n=10。10人的比赛，分两组( 1 2 3 4 5)和(6 7 8 9 10)各 5人。前 5人比赛的安排

7、 如表 2-12表 2-12 )67891007610809806791091006871097068然后两组合并，得到表 2-14表 2-14 )12345021530430124545013254201367891007610809806791091006871097068找两组中同一天中没有安排比赛的，安排他们比赛：表 2-15 )123456215374381245459132542101367891017610829836791091046871097568由于两组中：1 2 3 4 56 7 8 9 10按列对应的已经比赛过一次： 1 6，27，38，49，510。后面再安排两组

8、选手分别比赛的时候，就不考虑已经比赛过的组合。安排两组选手分别比赛的时候， 依照这样的规则： 1#按递增顺序依次跟没有比赛过 的第 2组选手比赛（ 7，8，9，10各一天）。若 1#和 x1比赛，则 2号从 610号中从 x1 之后开始按增序中找第一个没有比赛过的选手，跟他比赛（如果 x110，则 2号从 6 号开始按增序找 ）。3、4、5号也如此找。结果如表 2-16 所示：表 2-16）10 人的赛程安排1234567891021537489106381245910674591321067854210136789678910154327610829154383679102154910468

9、7321510975684321观察表 2-16 的右上角，发现如下规律（表 2-8， 6人比赛时，也有此规律） ： 【规则一】：每一行数值从左到右循环递增；每一列上也是6 10（即 n/2+1n ）循环递增（取到最大值 10之后，下一个数字又从 6 开始取值；而且不包含左上角的块同一行中取 过的值）。第一行第 m+1（ 下标从 0 开始 ）列的值为 （m+1）+1 ，依次向右递增；要先处理。其他 行上的值要依赖于它的这个取值。【规则二】：右下角的块：因为比赛是两两之间进行的，所以右下角由右上角决定（比 赛的对手是两个人，因此对应的安排要成对） ；OK ，至此，问题就好解决了，只要按照这个规律

10、填数字，就可以得到一种合理的安排。 由于我们不是求全部的安排，所以，只要得到这么一个解就可以了。9 人比赛，则将表 2-16 中的 10 全部用 0 代替即得。表 2-17） 9 人的赛程安排1234567890215374890638124590674591320678542013678967890154327608291543836790215490468732150975684321三、算法设计n 名选手的赛程安排问题：1、如果 n 为偶数，可分为两个 n/2 人的组，分别比赛，然后两组间比赛。（ 1）如果 n/2 为偶数，左下角为左上角加 n/2 来得到，然后左下角拷贝到右上角；左 上

11、角拷贝到右下角；（2）如果 n/2 为奇数，先安排左下角（除 0 外都加 n/2 ），然后把同一天都有空的选手 安排比赛。然后，右上角要按规则一来完成，右下角由规则二来定。2、如果 n 为奇数，则加 1 个选手使 n+1 成为偶数。转化成偶数名选手的赛程安排问题 来解决。最后把虚拟选手 n+1 号所在位置上的值置为 0。即完成安排。四、算法改进循环赛要求比赛的每两个选手都要进行一次比赛， 而且每个选手每天都要比赛一场。 这 种题目的解法通常是用分治的思想来做， 并且是分治方法解题的经典题目。 下面的一种受多 边形启发的方法，也能巧妙解决循环赛日程表问题。多边形解法： 有 n 个选手要进行循环赛

12、，画 n 边形，每个点表示一个选手。 在同一水平线上的选手进行比赛。每天的比赛由旋转一次的多边形决定，每次顺时针旋转 360/n 度 。例如：（ 1）假设有 5名运动员（每天将有一名队员轮空） ，则可建立一个如下五边多边形：所以第一天 4号轮空，对局为 1-2 和5-3（ 2）第二天顺时针旋转 360/5 度，即为：所以第二天 3号轮空，对局为 1-5 和2-4（3）依此类推，直到第五天，多边形为比赛结束，同理，若比赛人数为8人，多边形则为8依次顺时针旋转 360/8 度7次后，五、算法实现即比赛进行 7 天，即可结束比赛1）采用分治法实现代码（ c 语言实现）/* 循环赛日程安排问题- 采用

13、分治法 */#include #include int *A;/int *int *schedule; /int int N =1;/指针数组，数组，一维数组保存二维数组的数据 问题的规模。初始化时会设定/isodd: 判断 x 是否奇数，是则返回 1，否则 0 int isodd(int x)return x&1;/print: 打印赛程 void print()int i,j, row, col;if(isodd(N)row=N; col=N+1;else row=N; col=N;10printf( 第 1 列是选手编号 n);for(i=0;irow; i+)for(j=0;jcol;

14、 j+) printf(%4d, Aij); printf(n);/*init ：初始化，设置问题规模 N 值，分配内存，用 schedule 指向； 把 A 构造成一个二维数组 */void init() int i, n;char line100=0;printf( 请输入选手人数： );fgets(line,sizeof(line), stdin);N=atoi(line);if(N=0) exit(-1); if(isodd(N)n=N+1;elsen=N;/schedule 是行化的二维数组 schedule=(int *)calloc(n*n, sizeof(int);A=(int

15、 *)calloc(n, sizeof(int *);if(!schedule | A=NULL) exit(-2);for(i=0;in;i+) /把 A 等价为二维数组Ai=schedule+i*n;Ai0=i+1;/ 初始化这个数组的第一列return;/*replaceVirtual: 把第 m号虚的选手去掉(换做 0) */void replaceVirtual(int m)11int i,j;for(i=0;im-1;i+) / 行：对应选手号 1 m-1 for (j=0;j=m;j+) /列 : 比行要多 1Aij = (Aij=m)?0:Aij; return;2组 m位选手

16、/*copyeven:m 为偶数时用 ,由前 1 组的 m位选手的安排，来构成第的赛程安排，以及两组之间的比赛安排 */void copyeven(int m)if(isodd(m) return;int i,j;for (j=0;jm;j+) /1.for (i=0;im;i+)Ai+mj=Aij+m;for (j=m;j2*m;j+)/for (i=0;im;i+) /2.Aij=Ai+mj-m; /for (i=m;i2*m;i+) /3.Aij=Ai-mj-m; /求第 2 组的安排（ +m）两组间比赛的安排第 1 组和第 2 组把左下角拷贝到右上角对应的，第 2 组和第 1 组把左上

17、角拷贝到右下角return;/*copyodd:m 为奇数时用 , 由前 1 组的 m位选手的安排，来构成第 2 组 m位选手 的赛程安排，以及两组之间的比赛安排。这时和m为偶数时的处理有区别。*/12void copyodd(int m)int i,j;for (j=0;j=m;j+) /1.求第 2 组的安排 ( 前 m天 )for (i=0;im;i+)/ 行if (Aij!=0)Ai+mj=Aij+m;else / 特殊处理：两个队各有一名选手有空，安排他们比赛Ai+mj = i+1;Aij = i+m+1;/* 安排两组选手之间的比赛 (后 m-1 天)*/ for(i=0,j=m+

18、1;j2*m;j+)Aij= j+1; /2. 1 号选手的后 m-1 天比赛A (Aij -1) j = i+1; /3.他的对手后 m-1 天的安排 / 以下的取值要依赖于 1号选手的安排，所以之前先安排 1 号的赛程 for (i=1;im;i+) / 第 1 组的其他选手的后 m-1 天的安排 for (j=m+1;j2*m;j+)/2.观察得到的规则一：向下 m+12*m循环递增Aij (Ai-1j+1)%m;/3.= (Ai-1j+1)%m=0)?Ai-1j+1 :m +对应第 2 组的对手也要做相应的安排A (Aij-1) j = i+1; return;13/*makecopy

19、: 当前有 m位（偶数）选手，分成两组，每组由m/2 位选手构成由第一组的 m/2 位选手的安排来构成第二组的比赛安排，第一 组与第二组的比赛安排。要区分 m/2 为奇数和偶数两种情况 */void makecopy(int m)if (isodd(m/2)/m/2copyodd(m/2);else /m/2 copyeven(m/2);void tournament(int m)if(m=1)A00=1; return ;else if(isodd(m) /tournament(m+1); / replaceVirtual(m+1); / return ;else /mtournament(

20、m/2); / makecopy(m); /return ;为偶数如果 m为奇数，则 m+1是偶数 按照偶数个选手来求解然后把第 m+1号虚选手置成 0是偶数，则先安排第 1 组的 m/2 人比赛然后根据算法，构造左下、右下、右上、右下的矩阵/*endprogram: 回收分配的内存 */ void endprogram()free(schedule);free(A);14int main()init(); /初始化tournament(N);/求解print(); /打印结果endprogram(); /回收内存getchar();return 0;2)多边形法( C语言实现) /* 采用多

21、边形实现法 */ #include #define N 1000 int aNN;int bN;inline bool odd(int n)return n & 1;void init()int i;for(i=0;iN;+i) ai0=i;void tour(int n)an1=n; if(n=1) return;int m=odd(n) ? n : n-1; int i,j,k,r;for(i=1;i=m;+i)ai1=i;15 bi=i+1; bm+i=i+1; for(i=1;i=m;+i)a1i+1=bi;abii+1=1;for(j=1;j=m/2;+j) k=bi+j; r=bi+m-j; aki+1=r;ari+1=k;void out(int n)if(n=1)printf(1n);return;int i,j;int m;if(odd(n)m=n+1;elsem=n;for(i=1;i=n;+i)for(j=1;jn)printf(0 );16elseprintf