循环赛问题分析与C语言代码-分治法.docx

循环赛问题分析与C语言代码-分治法.docx问题描述：设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表：
每个选手必须与其他n-l个选手各赛一次；
每个选手一天只能赛一次；
当n是偶数时，循环赛进行n-l天。当n是奇数时，循环赛进行n天。
分析过程：
这个问题的解搜索空间是一个n的全排列。要求的解是其中的n个排列，满足条件：第1 列n个元素值按增序排列；每行每列没有相同的数。也是一个幻方(除对角线的和不作要求) 的问题。
=l
（表1）
2. n=2
（表2）
=3,
添加一个虚拟选手4#,构成n+l=4
4/2=2,分两组，每组各自安排(12), (34)
每组跟另一组分别比赛(拷贝)这是四个人比赛的安排
(4)把虚选手置为0
(表3) 4人赛程
这是三个人比赛的安排
n=4,见表 3
n=5,⑴加一个虚选手，n+l=6。安排好6个人的比赛后，把第6个人用0表示即得5人的。
分成两组(1 2 3) (456)，各3名选手
依照表4,安排第1组；按表5安排第2组(除0元素外，都加3)
(表5)
4
5
6
0
把表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
把同一天都有空的两组安排在一起比赛(按这种安排，肯定每天只有一对空组，?)。
（表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
⑹ 第一组的(12 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#
⑹若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。
8 n=8 ,见表 10o
9n=9,由n+l = 10人，将虚选手10号置为0来得到。
10n=10« 10人的比赛，分两组（1 23 4 5）和（6789 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）号对应加5
（表 13）
6
7
8
9
10
0
7
6
10
8
0
9
8
0
6
7
9
10
9
10
0
6
8
7
10
9
7
0
6
8
然后两组合并
俵14)
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
7
8
9
10
0
7
6
10
8
0
9
8
0
6
7
9
10
9
10
0
6
8
7
10
9
7
0
6
8
找两组中同一天中没有安排比赛的，安排他们比赛:
（表 15）
1
2
3
4
5
6
2
1
5
3
7
4
3
8
1
2
4
5
4
5
9
1
3
2
5
4
2
10
1
3
6
7
8
9
10
1
7
6
10
8
2
9
8
3
6
7
9
10
9
10
4
6
8
7
10
9
7
5
6
8