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》对你有帮助，请点赞、收藏，并留下你的观点哦！
