循环赛日程表问题研究

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

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

3、13、n=3(1) 添加一个虚拟选手4#，构成n+14(2) 4/22，分两组，每组各自安排（1 2），（3 4）(3) 每组跟另一组分别比赛（拷贝）这是四个人比赛的 （表2-3） 4人赛程1234214334124321(4) 把虚选手置为0 （表2-4）3人赛程1230210330120321 这是三个人比赛的安排4、n=4，见表2-3 5、n=5(1) 加一个虚选手，n+1=6。安排好6个人的比赛后，把第6个人用0表示即得5人的。 (2) 分成两组(1 2 3) （4 5 6），各3名选手(3) 依照表2-4，安排第1组；按表2-5安排第2组(除0元素外，都加3)（表2-5）456054

4、0660450321 (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 3 4 5 6首先，1#只能和5#或6#比赛。(a) 若1#5#，由于3#和6#已经比赛过，所以只能安排: 2#6#， 3#4#(b) 若1#6#，由于2#和5#已

5、经比赛过，只能安排： 2#4#， 3#5#这样安排后前三行的后两列，后三行的后两列由上面的三行来定：123456215364361245456132542613634521 （表2-8）6人赛程 表2-8就是6名选手的比赛日程安排。将其中的6号作为虚拟选手，把6换成0，即得5名选手的赛程安排表： （表2-9）5人赛程1234502153043012454501325420136345216、n=6，见表2-8。7、n=7, 添加1，n+1=8。8名选手的安排，由4名选手（表2-3）构成 （表2-10）8人赛程1234567821436587341278564321876556781234658

6、721437856341287654321将其中的8改成0，即得7名选手的赛程安排。 （表2-11）7人赛程12345670214365073412705643210765567012346507214370563412076543218、n=8 ，见表2-10。9、n=9，由n+110人，将虚选手10号置为0来得到。10、n=10。10人的比赛，分两组（1 2 3 4 5）和(6 7 8 9 10)各5人。前5人比赛的安排如表2-12 （表2-12）123450215304301245450132542013第2组的5人比赛就是将前5人比赛选手（非0）号对应加5 （表2-13）6789100

7、7610809806791091006871097068然后两组合并，得到表2-14（表2-14）12345021530430124545013254201367891007610809806791091006871097068找两组中同一天中没有安排比赛的，安排他们比赛： （表2-15）123456215374381245459132542101367891017610829836791091046871097568由于两组中：1 2 3 4 5 6 7 8 9 10 按列对应的已经比赛过一次：16，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人的赛程安排12345678910215374891063812459106745913210678542101367896789101543276108291543836791021549104687321510975684321观察表2-16的右上角，发现如下规律（表2-8，6人比赛

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

10、替即得。 （表2-17）9人的赛程安排1234567890215374890638124590674591320678542013678967890154327608291543836790215490468732150975684321三、算法设计n名选手的赛程安排问题：1、如果n为偶数，可分为两个n/2人的组，分别比赛，然后两组间比赛。（1）如果n/2为偶数，左下角为左上角加n/2来得到，然后左下角拷贝到右上角；左上角拷贝到右下角； （2）如果n/2为奇数，先安排左下角（除0外都加n/2），然后把同一天都有空的选手安排比赛。然后，右上角要按规则一来完成，右下角由规则二来定。2、如果n为奇数

11、，则加1个选手使n+1成为偶数。转化成偶数名选手的赛程安排问题来解决。最后把虚拟选手n+1号所在位置上的值置为0。即完成安排。四、算法改进循环赛要求比赛的每两个选手都要进行一次比赛，而且每个选手每天都要比赛一场。这种题目的解法通常是用分治的思想来做，并且是分治方法解题的经典题目。下面的一种受多边形启发的方法，也能巧妙解决循环赛日程表问题。多边形解法：有n个选手要进行循环赛，画n边形，每个点表示一个选手。 在同一水平线上的选手进行比赛。每天的比赛由旋转一次的多边形决定，每次顺时针旋转360/n度。例如：（1）假设有5名运动员（每天将有一名队员轮空），则可建立一个如下五边多边形： 1 2 5 3

12、4 所以第一天4号轮空，对局为1-2和5-3（2）第二天顺时针旋转360/5度，即为： 5 1 4 2 3 所以第二天3号轮空，对局为1-5和2-4 （3）依此类推，直到第五天，多边形为 2 3 1 4 5 比赛结束，同理，若比赛人数为8人，多边形则为 1 2 8 3 7 4 6 5 依次顺时针旋转360/8度7次后，即比赛进行7天，即可结束比赛五、算法实现（1）采用分治法实现代码（c语言实现）：/* 循环赛日程安排问题-采用分治法 */#include#includeint *A; /int *指针数组，int *schedule; /int数组，一维数组保存二维数组的数据int N =1;

13、 /问题的规模。初始化时会设定/isodd:判断x是否奇数，是则返回1，否则0int 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; printf(第1列是选手编号n); for(i=0;irow; i+) for(j=0;jcol; j+) printf(%4d, Aij); printf(n); /*init：初始化，设置问题规模N值，分配内存，用schedule指向； 把A构造成一个二维数组*/void ini

14、t() 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; else n=N; /schedule是行化的二维数组 schedule=(int *)calloc(n*n, sizeof(int); A=(int *)calloc(n, sizeof(int *); if(!schedule | A=NULL) exit(-2); for(i=0;in;i+) /把A等价为二维数组 Ai=sch

15、edule+i*n; Ai0=i+1;/初始化这个数组的第一列 return;/*replaceVirtual:把第m号虚的选手去掉（换做0）*/void replaceVirtual(int m) int i,j; for(i=0;im-1;i+) /行：对应选手号1m-1 for (j=0;j=m;j+) /列: 比行要多1 Aij = (Aij=m)?0:Aij; return;/*copyeven:m为偶数时用,由前1组的m位选手的安排，来构成第2组m位选手 的赛程安排，以及两组之间的比赛安排 */void copyeven(int m) if(isodd(m) return; int

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

17、dd(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+1;j2*m;j+) Aij= j+1; /2. 1号选手的后m-1天比赛 A (Aij -1) j = i+1; /3. 他的对手后m-1天的安排 /以下的取值要依赖于1号选手的安排，所以之前先安排1号的赛程 for (i=

18、1;im;i+) /第1组的其他选手的后m-1天的安排 for (j=m+1;j2*m;j+) /2. 观察得到的规则一：向下m+12*m循环递增 Aij = (Ai-1j+1)%m=0)?Ai-1j+1 :m + (Ai-1j+1)%m; /3. 对应第2组的对手也要做相应的安排 A (Aij-1) j = i+1; return;/*makecopy:当前有m位（偶数）选手，分成两组，每组由m/2位选手构成 由第一组的m/2位选手的安排来构成第二组的比赛安排，第一 组与第二组的比赛安排。要区分m/2为奇数和偶数两种情况 */void makecopy(int m) if (isodd(m/

19、2) /m/2为奇数 copyodd(m/2); else /m/2为偶数 copyeven(m/2);void tournament(int m) if(m=1) A00=1; return ; else if(isodd(m) /如果m为奇数，则m+1是偶数 tournament(m+1); /按照偶数个选手来求解 replaceVirtual(m+1); /然后把第m+1号虚选手置成0 return ; else /m是偶数， tournament(m/2); /则先安排第1组的m/2人比赛 makecopy(m); /然后根据算法，构造左下、右下、右上、右下的矩阵 return ;/*

20、endprogram:回收分配的内存*/void endprogram() free(schedule); free(A); int main() init(); /初始化 tournament(N);/求解 print(); /打印结果 endprogram(); /回收内存 getchar(); return 0;（2） 多边形法（C语言实现）：/* 采用多边形实现法 */#include #define N 1000int aNN;int bN;inline bool odd(int n) return n & 1;void init() int i; for(i=0;iN;+i) ai

21、0=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; 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; else m=n; for(i=1;i=n;+i) for(j=1;jn) pri