循环赛日程表问题研究.docx
- 文档编号:16297940
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:22
- 大小:20.99KB
循环赛日程表问题研究.docx
《循环赛日程表问题研究.docx》由会员分享,可在线阅读,更多相关《循环赛日程表问题研究.docx(22页珍藏版)》请在冰点文库上搜索。
循环赛日程表问题研究
循环赛日程表问题研究
题目循环赛日程表问题研究
学生
指导教师
年级2009级
专业软件工程
系别软件工程
学院计算机科学与信息工程学院
哈尔滨师范大学
2012年6月
论文提要
本文采用分治算法来解决循环赛日程表的安排问题。
通过对问题的详细分析,列出1到10个选手的比赛日程表,找出两条规则,作为算法实现的依据,而后采用c语言实现算
法,通过测试分析,程序运行结果正确,运行效率较高。
同时也介绍了循环赛日程表问题的另一种解法多边形解法,这种方法另辟蹊径,巧妙地解决了循环赛日程表问题,运行效率较高。
循环赛日程表问题研究
摘要:
本文采用分治算法来解决循环赛日程表的安排问题。
根据算法的设计结果,采
2
用c语言实现算法,通过测试分析,程序运行结果正确,运行效率较高。
同时也介绍了循环
赛日程表问题的另一种解法,这种方法另辟蹊径,想法独特,运行效率较高。
关键词:
循环赛日程表问题,分治法
一、题目描述
设有n个运动员要进行网球循环赛。
设计一个满足以下要求的比赛日程表:
(1)每个选手必须与其他n-1个选手各赛一次;
(2)每个选手一天只能赛一次;
(3)当n是偶数时,循环赛进行n-1天。
当n是奇数时,循环赛进行n天。
二、问题分析
循环赛日程表可以采用分治法实现,把一个表格分成4个小表格来处理,每个小表格都
是一样的处理方法,只是参数不同。
分析过程具体如下:
1、n=1
(表2-1)
1
2.、n=2
-2)(表2
12
21
3、n=3
(1)添加一个虚拟选手4#,构成n+1,4
(2)4/2,2,分两组,每组各自安排(12),(34)
(3)每组跟另一组分别比赛(拷贝)这是四个人比赛的
(表2-3)4人赛程
1234
2143
3412
4321(4)把虚选手置为0
(表2-4)3人赛程
3
1230
2103
3012
0321
这是三个人比赛的安排
4、n=4,见表2-3
5、n=5
(1)加一个虚选手,n+1=6。
安排好6个人的比赛后,把第6个人用0表示即得5
人的。
(2)分成两组(123)(456),各3名选手
(3)依照表2-4,安排第1组;按表2-5安排第2组(除0元素外,都加3)
(表2-5)
4560
5406
6045
0321
(4)把表2-5排于表2-4下方
(表2-6)
1230
2103
3012
4560
5406
6045
(5)把同一天都有空的两组安排在一起比赛(按这种安排,肯定每天只有一对空组)。
(表2-7)
1234
2153
3612
4561
5426
6345
(6)第一组的(123)和第2组的(456)分别比赛。
但是由于(1,4),(2,5),(36)已经比
4
赛过了,所以在后面的安排中不能再安排他们比赛。
123
456
首先,1#只能和5#或6#比赛。
(a)若1#,5#,由于3#和6#已经比赛过,所以只能安排:
2#,6#,3#,4#
(b)若1#,6#,由于2#和5#已经比赛过,只能安排:
2#,4#,3#,5#
这样安排后前三行的后两列,后三行的后两列由上面的三行来定:
(表2-8)6人赛程
123456
215364
361245
456132
542613
634521
表2-8就是6名选手的比赛日程安排。
将其中的6号作为虚拟选手,把6换成0,
即得5名选手的赛程安排表:
(表2-9)5人赛程
123450
215304
301245
450132
542013
634521
6、n=6,见表2-8。
7、n=7,添加1,n+1=8。
8名选手的安排,由4名选手(表2-3)构成
(表2-10)8人赛程
12345678
21436587
34127856
43218765
5678123465872143
78563412
87654321
将其中的8改成0,即得7名选手的赛程安排。
5
(表2-11)7人赛程
1234567021436507
34127056
43210765
56701234
65072143
70563412
07654321
8、n=8,见表2-10。
9、n=9,由n+1,10人,将虚选手10号置为0来得到。
10、n=10。
10人的比赛,分两组(12345)和(678910)各5人。
前5人比赛的安排
如表2-12
(表2-12)
123450215304
301245
450132
542013
第2组的5人比赛就是将前5人比赛选手(非0)号对应加5
(表2-13)
6789100
76108098067910
9100687
1097068
然后两组合并,得到表2-14
6
(表2-14)
123450
215304
301245450132
542013
6789100
7610809
8067910
9100687
1097068
找两组中同一天中没有安排比赛的,安排他们比赛:
(表2-15)
123456
215374
381245459132
5421013
6789101
7610829
8367910
9104687
1097568
由于两组中:
12345
678910
按列对应的已经比赛过一次:
1,6,2,7,3,8,4,9,5,10。
后面再安排两组
选手分别比赛的时候,就不考虑已经比赛过的组合。
安排两组选手分别比赛的时候,依照这样的规则:
1#按递增顺序依次跟没有比赛过
的第2组选手比赛(7,8,9,10各一天)。
若1#和x比赛,则2号从6~10号中从x11
之后开始按增序中找第一个没有比赛过的选手,跟他比赛(如果x,10,则2号从6号1
开始按增序找)。
3、4、5号也如此找。
结果如表2-16所示:
7
(表2-16)10人的赛程安排
12345678910
21537489106
3812459106745913210678
54210136789
67891015432
76108291543
83679102154
91046873215
10975684321
观察表2-16的右上角,发现如下规律(表2-8,6人比赛时,也有此规律):
【规则一】:
每一行数值从左到右循环递增;每一列上也是6,10(即n/2+1~n)循环递增(取到最大值10之后,下一个数字又从6开始取值;而且不包含左上角的块同一行中取过的值)。
第一行第m+1(下标从0开始)列的值为(m+1)+1,依次向右递增;要先处理。
其他行上的值要依赖于它的这个取值。
【规则二】:
右下角的块:
因为比赛是两两之间进行的,所以右下角由右上角决定(比赛的对手是两个人,因此对应的安排要成对);
OK,至此,问题就好解决了,只要按照这个规律填数字,就可以得到一种合理的安排。
由于我们不是求全部的安排,所以,只要得到这么一个解就可以了。
9人比赛,则将表2-16中的10全部用0代替即得。
(表2-17)9人的赛程安排
1234567890
2153748906
3812459067
4591320678
5420136789
6789015432
7608291543
8367902154
9046873215
0975684321
8
三、算法设计
n名选手的赛程安排问题:
1、如果n为偶数,可分为两个n/2人的组,分别比赛,然后两组间比赛。
(1)如果n/2为偶数,左下角为左上角加n/2来得到,然后左下角拷贝到右上角;左上角拷贝到右下角;
(2)如果n/2为奇数,先安排左下角(除0外都加n/2),然后把同一天都有空的选手安排比赛。
然后,右上角要按规则一来完成,右下角由规则二来定。
2、如果n为奇数,则加1个选手使n+1成为偶数。
转化成偶数名选手的赛程安排问题
来解决。
最后把虚拟选手n+1号所在位置上的值置为0。
即完成安排。
四、算法改进
循环赛要求比赛的每两个选手都要进行一次比赛,而且每个选手每天都要比赛一场。
这种题目的解法通常是用分治的思想来做,并且是分治方法解题的经典题目。
下面的一种受多边形启发的方法,也能巧妙解决循环赛日程表问题。
多边形解法:
有n个选手要进行循环赛,画n边形,每个点表示一个选手。
在同一水平线上的选手进行比赛。
每天的比赛由旋转一次的多边形决定,每次顺时针旋转360/n度。
例如:
(1)假设有5名运动员(每天将有一名队员轮空),则可建立一个如下五边多边形:
12
53
4
所以第一天4号轮空,对局为1-2和5-3
(2)第二天顺时针旋转360/5度,即为:
51
42
3
9
所以第二天3号轮空,对局为1-5和2-4
(3)依此类推,直到第五天,多边形为
23
14
5
比赛结束,同理,若比赛人数为8人,多边形则为
12
83
74
65
依次顺时针旋转360/8度7次后,即比赛进行7天,即可结束比赛
五、算法实现
(1)采用分治法实现代码(c语言实现):
/*循环赛日程安排问题-采用分治法*/
#include
#include
int**A;//int*指针数组,
int*schedule;//int数组,一维数组保存二维数组的数据
intN=1;//问题的规模。
初始化时会设定
//isodd:
判断x是否奇数,是则返回1,否则0
intisodd(intx)
{
returnx&1;
}
//print:
打印赛程
voidprint()
{
inti,j,row,col;
if(isodd(N))
{
row=N;
col=N+1;
}
else
{
row=N;
col=N;
10
}
printf("第1列是选手编号\n");
for(i=0;i { for(j=0;j { printf("%4d",A[i][j]); } printf("\n"); } } /*init: 初始化,设置问题规模N值,分配内存,用schedule指向; 把A构造成一个二维数组*/ voidinit() {inti,n; charline[100]={'\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;i { A[i]=schedule+i*n; A[i][0]=i+1;//初始化这个数组的第一列 } return; } /*replaceVirtual: 把第m号虚的选手去掉(换做0)*/voidreplaceVirtual(intm){ 11 inti,j; for(i=0;i 对应选手号1,m-1 { for(j=0;j<=m;j++)//列: 比行要多1 A[i][j]=(A[i][j]==m)? 0: A[i][j]; } return; } /*copyeven: m为偶数时用,由前1组的m位选手的安排,来构成第2组m位选手 的赛程安排,以及两组之间的比赛安排*/voidcopyeven(intm) { if(isodd(m))return; inti,j; for(j=0;j { for(i=0;i { A[i+m][j]=A[i][j]+m; } } for(j=m;j<2*m;j++)//两组间比赛的安排 { for(i=0;i { A[i][j]=A[i+m][j-m];//把左下角拷贝到右上角 } for(i=m;i<2*m;i++)//3.对应的,第2组和第1组 { A[i][j]=A[i-m][j-m];//把左上角拷贝到右下角 } } return; } /*copyodd: m为奇数时用,由前1组的m位选手的安排,来构成第2组m位选手 的赛程安排,以及两组之间的比赛安排。 这时和m为偶数时的 处理有区别。 */ 12 voidcopyodd(intm) { inti,j; for(j=0;j<=m;j++)//1.求第2组的安排(前m天) { for(i=0;i { if(A[i][j]! =0) { A[i+m][j]=A[i][j]+m; } else//特殊处理: 两个队各有一名选手有空,安排他们比赛 { A[i+m][j]=i+1; A[i][j]=i+m+1; } } } /*安排两组选手之间的比赛(后m-1天)*/ for(i=0,j=m+1;j<2*m;j++) { A[i][j]=j+1;//2.1号选手的后m-1天比赛 A[(A[i][j]-1)][j]=i+1;//3.他的对手后m-1天的安排 } //以下的取值要依赖于1号选手的安排,所以之前先安排1号的赛程 for(i=1;i { for(j=m+1;j<2*m;j++) {//2.观察得到的规则一: 向下m+1~2*m循环递增 A[i][j]=((A[i-1][j]+1)%m==0)? A[i-1][j]+1: m+ (A[i-1][j]+1)%m; //3.对应第2组的对手也要做相应的安排 A[(A[i][j]-1)][j]=i+1; } } return; 13 } /*makecopy: 当前有m位(偶数)选手,分成两组,每组由m/2位选手构成 由第一组的m/2位选手的安排来构成第二组的比赛安排,第一 组与第二组的比赛安排。 要区分m/2为奇数和偶数两种情况*/ voidmakecopy(intm) { if(isodd(m/2))//m/2为奇数 copyodd(m/2); else//m/2为偶数 copyeven(m/2); } voidtournament(intm) { if(m==1) { A[0][0]=1; return; } elseif(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; } /*endprogram: 回收分配的内存*/ voidendprogram() { free(schedule); free(A); 14 } intmain() { init();//初始化 tournament(N);//求解 print();//打印结果 endprogram();//回收内存 getchar(); return0; } (2)多边形法(C语言实现): /*采用多边形实现法*/ #include inta[N][N]; intb[N]; inlineboolodd(intn) { returnn&1;} voidinit() { inti; for(i=0;i a[i][0]=i;} voidtour(intn){ a[n][1]=n; if(n==1)return; intm=odd(n)? n: n-1; inti,j,k,r; for(i=1;i<=m;++i) { a[i][1]=i; 15 b[i]=i+1; b[m+i]=i+1; } for(i=1;i<=m;++i) { a[1][i+1]=b[i]; a[b[i]][i+1]=1; for(j=1;j<=m/2;++j) { k=b[i+j]; r=b[i+m-j]; a[k][i+1]=r; a[r][i+1]=k; } } } voidout(intn) { if(n==1) { printf("1\n"); return; } inti,j; intm; if(odd(n)) m=n+1; else m=n; for(i=1;i<=n;++i) { for(j=1;j<=m;++j) { if(a[i][j]>n) printf("0"); 16 else printf("%d",a[i][j]); } printf("\n"); } } intmain() { intn; init(); while(scanf("%d",&n),n) { tour(n); out(n); } return0; } 六、总结 算法实现1采用的分治算法,其基本思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 这是循环赛日程表问题解决方法的经典形式,但是比较复杂,分析起来比较繁琐。 而算法实现2采用的多边形解法,其基本思想是,对于n个选手进行的循环赛,画出一个n边形,每个点表示一个选手,在同一水平线上的选手进行比赛,每天的比赛由旋转一次的多边形决定,每次顺时针旋转360/n度。 ,该解法很巧妙,思想独特,并且容易理解。 两者效率差不多,在整体上多边形解法比分治法较优。 多边形解法给了我们一个良好的启发,对于一个复杂的问题,往往会有一个很简单的解决方法。 参考文献: [1]王晓东: 计算机算法分析与设计,电子工业出版社,2006年版。 [2]严蔚敏吴伟民: 数据结构(C语言版),清华大学出版社,1997年版。 17 学年论文(设计)成绩表 论文题目循环赛日程表问题研究 作者 指导教师职称讲师 该生在论文中,详细介绍循环赛日程表问题,在对问题进行详 细分析论述的基础上提出了两种风格不同的解题策略,对每种策略 都给出了实现算法的具体程序。 指 该生在完成论文的过程中态度认真积极,能及时与老师沟通,导 教按时完成写作进度。 该生基本上具有独立分析问题、解决问题的能 师 力。 评 语论文结构清晰,论述完整,观点明确,表达清楚。 文章书写工 整,格式及标点规范。 符合本科生学年论文标准。 指导教师签字等级 18
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 循环赛 日程表 问题 研究