WORD格式整理版
学习好帮手
问题描述:设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表:
(1)每个选手必须与其他n-1个选手各赛一次;
(2)每个选手一天只能赛一次;
(3)当n是偶数时,循环赛进行n-1天。当n是奇数时,循环赛进行n天。
分析过程:
这个问题的解搜索空间是一个n的全排列。要求的解是其中的n个排列,满足条件:第1列n个元素值按增序排列;每行每列没有相同的数。也是一个幻方(除对角线的和不作要求)的问题。
1.n=1
(表1)
1
2. n=2
(表2)
1
2
2
1
3.n=3,
(1) 添加一个虚拟选手4#,构成n+1=4
(2) 4/2=2,分两组,每组各自安排(1 2),(3 4)
(3)每组跟另一组分别比赛(拷贝)这是四个人比赛的安排
(表3) 4人赛程
1
2
3
4
2
1
4
3
3
4
1
2
4
3
2
1
(4)把虚选手置为0
(表4)3人赛程
1
2
3
0
2
1
0
3
3
0
1
2
0
3
2
1
这是三个人比赛的安排
4. n=4, 见表3
5. n=5, (1)加一个虚选手,n+1=6。安排好6个人的比赛后,把第6个人用0表示即得5人的。
(2) 分成两组(1 2 3) (4 5 6),各3名选手
(3) 依照表4,安排第1组;按表5安排第2组(除0元素外,都加3)
(表5)
4
5
6
0
5
4
0
6
6
0
4
5
0
3
2
1
(4) 把表5排于表4下方
(表6)
1
2
3
0
2
1
0
3
3
0
1
2
4
5
6
0
5
4
0
6
6
0
4
5
(5) 把同一天都有空的两组安排在一起比赛(按这种安排,肯定每天只有一对空组,?)。
(表7)
1
2
3
4
2
1
5
3
3
6
1
2
4
5
6
1
5
4
2
6
6
3
4
5
(6) 第一组的(1 2 3)和第2组的(4 5 6)分别比赛。 但是由于(1,4), (2, 5), (3 6)已经比赛过了,所以在后面的安排中不能再安排他们比赛。
1 2 3
4 5 6
首先,1#只能和5#或6#比赛。
若1#-5#,由于3#和6#已经比赛过,所以只能安排: 2#-6#, 3#-4#
若1#-6#,由于2#和5#已经比赛过,只能安排: 2#-4#, 3#-5#
这样安排后前三行的后两列,后三行的后两列由上面的三行来定:
(表8)6人赛程
1
2
3
4
5
6
2
1
5
3
6
4
3
6
1
2
4
5
4
5
6
1
3
2
5
4
2
6
1
3
6
3
4
5
2
1
表8就是6名选手的比赛日程安排。将其中的6号作为虚拟选手,把6换成0,即得5名选手的赛程安排表:
(表9)5人赛程
1
2
3
4
5
0
2
1
5
3
0
4
3
0
1
2
4
5
4
5
0
1
3
2
5
4
2
0
1
3
6
3
4
5
2
1
6 n=6,见表8。
7 n=7, 添加1,n+1=8。8名选手的安排,由4名选手(表3)构成
(表10)8人赛程
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
5
6
7
8
1
2
3
4
6
5
8
7
2
1
4
3
7
8
5
6
3
4
1
2
8
7
6
5
4
3
2
1
将其中的8改成0,即得7名选手的赛程安排。
(表11)7人赛程
1
2
3
4
5
6
7
0
2
1
4
3
6
5
0
7
3
4
1
2
7
0
5
6
4
3
2
1
0
7
6
5
5
6
7
0
1
2
3
4
6
5
0
7
2
1
4
3
7
0
5
6
3
4
1
2
0
7
6
5
4
3
2
1
8 n=8 ,见表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人比赛的安排如表9
(表12)
1
2
3
4
5
0
2
1
5
3
0
4
3
0
1
2
4
5
4
5
0
1
3
2
5
4
2
0
1
3
第2组的5人比赛就是将前5人比赛选手(非0)号对
如果觉得《分治法循环赛c语言 循环赛问题分析和C语言代码-分治法.doc》对你有帮助,请点赞、收藏,并留下你的观点哦!