第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
循环赛问题c语言代码.doc
问题描述：设有 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
4
3
2
2
3
4
1
3
4
1
2
2
1
4
3
(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
6
0
4
0
3
0
4
2
6
5
1
(4) 把表 5 排于表 4 下方
（表 6）
2
1
0
5
4
0
1
2
3
4
5
6
3
0
1
6
0
4
0
3
2
0
6
5
(5) 把同一天都有空的两组安排在一起比赛(按这种安排，肯定每天只有一对空组，？)。
（表 7）
1
2
3
4
5
6
2
1
6
5
4
3
3
5
1
6
2
4
4
3
2
1
6
5
(6) 第一组的(1 2 3)和第 2 组的(4 5 6)分别比赛。但是由于(1,4), (2, 5), (3 6)已经比赛过
了，所以在后面的安排中不能再安排他们比赛。
3
6
2
5
1
4
首先，1#只能和 5#或 6#比赛。
(a) 若 1#－5#，由于 3#和 6#已经比赛过，所以只能安排: 2#－6#， 3#－4#
(b) 若 1#－6#，由于 2#和 5#已经比赛过，只能安排： 2#－4#， 3#－5#
这样安排后前三行的后两列，后三行的后两列由上面的三行来定：
（表 8）6 人赛程
1
2
3
4
5
6
3
5
1
6
2
4
4
3
2
1
6
5
2
1
6
5
4
3
5
6
4
3
1
2
6
4
5
2
3
1
表 8 就是 6 名选手的比赛日程安排。将其中的 6 号作为虚拟选手，把 6 换成 0，即得
5 名选手的赛程安排表：
（表 9）5 人赛程
4
3
2
1
0
5
3
5
1
0
2
4
1
2
3
4
5
6
2
1
0
5
4
3
5
0
4
3
1
2
0
4
5
2
3
1
6 n=6，见表 8。
7 n=7, 添加 1，n+1=8。8 名选手的安排，由 4 名选手（表 3）构成
（表 10）8 人赛程
5
1
2
6
7
3
8
4
5
1
2
6
3
7
8
4
3
4
1
2
7
8
5
6
4
3
2
1
8
7
6
5
2
1
4
3
6
5
8
7
将其中的 8 改成 0，即得 7 名选手的赛程安排。
（表 11）7 人赛程
4
3
2
1
0
7
6
5
3
4
1
2
7
0
5
6
1
2
3
4
5
6
7
0
2
1
4
3
6
5
0
7
5
6
7
0
1
2
3
4
6
5
8
7
2
1
4
3
6
5
0
7
2
1
4
3
7
8
5
6
3
4
1
2
7
0
5
6
3
4
1
2
8
7
6
5
4
3
2
1
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
2
1
0
5
4
3
5
1
0
2
4
3
2
1
0
5
0
4
3
1
0
4
5
2
3
第 2 组的 5 人比赛就是将前 5 人比赛选手（非 0）号对应加 5
然后两组合并
（表 13）
6
7
8
9
10
7
6
0
10
9
（表 14）
1
2
3
4
5
6
7
8
9
10
2
1
0
5
4
7
6
0
10
9
8
10
6
0
7
3
5
1
0
2
8
10
6
0
7
9
8
7
6
0
4
3
2
1
0
9
8
7
6
0
10
0
9
8
6
5
0
4
3
1
10
0
9
8
6
找两组中同一天中没有安排比赛的，安排他们比赛：
（表 15）
1
2
3
4
5
6
7
8
9
10
2
1
8
5
4
7
6
3
10
9
3
5
1
9
2
8
10
6
4
7
4
3
2
1
10
9
8
7
6
5
5
7
4
3
1
10
2
9
8
6
0
9
10
7
8
0
4
5
2
3
0
9
10
7
8
6
4
5
2
3
1
9
10
7
8
2
7
3
8
4
9
5
10
由于两组中：
1
6
按列对应的已经比赛过一次：1－6，2－7，3－8，4－9，5－10。后面再安排两组选手分别
比赛的时候，就不考虑已经比赛过的组合。
安排两组选手分别比赛的时候，依照这样的规则：1#按递增顺序依次跟没有比赛过的第 2
组选手比赛（7，8，9，10 各一天）。若 1#和 x1 比赛，则 2 号从 6~10 号中从 x1 之后开始按
增序中找第一个没有比赛过的选手，跟他比赛(如果 x1＝10，则 2 号从 6 号开始按增序找)。
3、4、5 号也如此找。结果如表 16 所示：
（表 16）10 人的赛程安排
6
4
5
2
3
1
9
10
7
8
3
5
1
9
2
8
10
6
4
7
4
3
2
1
10
9
8
7
6
5
1
2
3
4
5
6
7
8
9
10
2
1
8
5
4
7
6
3
10
9
5
7
4
3
1
10
2
9
8
6
7
8
9
10
6
5
1
2
3
4
8
9
10
6
7
4
5
1
2
3
9
10
6
7
8
3
4
5
1
2
10
6
7
8
9
2
3
4
5
1
观察表 16 的右上角，发现如下规律（表 8，6 人比赛时，也有此规律）：
【规则一】：每一行数值从左到右循环递增；每一列上也是 6～10（即 n/2+1~n）循环递增
（取到最大值 10 之后，下一个数字又从 6 开始取值；而且不包含左上角的块同一行中取过
的值）。第一行第 m+1(下标从 0 开始)列的值为(m+1)+1，依次向右递增；要先处理。其他
行上的值要依赖于它的这个取值。
【规则二】：右下角的块：因为比赛是两两之间进行的，所以右下角由右上角决定（比赛的
对手是两个人，因此对应的安排要成对）；
OK，至此，问题就好解决了，只要按照这个规律填数字，就可以得到一种合理的安排。
由于我们不是求全部的安排，所以，只要得到这么一个解就可以了。
9 人比赛，则将表 16 中的 10 全部用 0 代替即得。
（表 17）9 人的赛程安排
1
2
3
4
5
6
7
8
9
0
2
1
8
5
4
7
6
3
0
9
3
5
1
9
2
8
0
6
4
7
4
3
2
1
0
9
8
7
6
5
5
7
4
3
1
0
2
9
8
6
6
4
5
2
3
1
9
0
7
8
7
8
9
0
6
5
1
2
3
4
8
9
0
6
7
4
5
1
2
3
9
0
6
7
8
3
4
5
1
2
0
6
7
8
9
2
3
4
5
1
由上面的分析，可以总结出如下算法：
n 名选手的赛程安排问题：
1 如果 n 为偶数，可分为两个 n/2 人的组，分别比赛，然后两组间比赛。
1.1 如果 n/2 为偶数，左下角为左上角加 n/2 来得到，然后左下角拷贝到右上角；左
上角拷贝到右下角；
1.2 如果 n/2 为奇数，先安排左下角（除 0 外都加 n/2），然后把同一天都有空的选手
安排比赛。然后，右上角要按规则一来完成，右下角由规则二来定。
2 如果 n 为奇数，则加 1 个选手使 n+1 成为偶数。转化成偶数名选手的赛程安排问题来
解决。最后把虚拟选手 n+1 号所在位置上的值置为 0。即完成安排。
/* exp6_09_3.cpp 循环赛日程安排问题-采用分治法 */
#include
#include
int **A;
int *schedule;
int N =1;
//int *指针数组，
//int 数组，一维数组保存二维数组的数据
//问题的规模。初始化时会设定
//isodd:判断 x 是否奇数，是则返回 1，否则 0
int 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;i
{
int i, n;
char line[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+m][j]=A[i][j]+m;
}
for (j=m;j<2*m;j++)//两组间比赛的安排
{
for (i=0;i
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
最新资料
2022-2023学年河北省唐山市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末数学试题及答案.doc
2022-2023学年河北省衡水市高三上学期期末语文试题及答案.doc
2022-2023学年河北省保定市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末语文试题及答案.doc
2022-2023学年河北省石家庄市高三上学期期末语文试题及答案.doc
2020-2021年四川省凉山州西昌市高一物理上学期期中试卷及答案.doc
2020-2021年四川省遂宁市安居区高一英语上学期期中试卷及答案.doc
2020-2021年四川省西昌市高一英语上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一地理上学期期中试卷及答案.doc
2021-2022年四川省成都市郫都区高一物理上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一物理上学期期中试卷及答案.doc