[讲稿]单循环赛日程表

[讲稿]单循环赛日程表 题目:循环赛日程表 一个满足一下要求的比赛日程表 (1)每个选手必须与其他n-1个选手各赛一次; (2)每个选手一天只能赛一次; (3)若才赛选手为偶数，循环赛一共进行n-1天;若参赛选手为奇数循环赛一共进行n天。 主要思想:“贝格尔”编排法,其优点是单数队参加时可避免第二轮的轮空队从第四轮起每场都与前 一轮的轮空队比赛的不合理现象。 方法如下: 所谓贝格尔编排法，第一轮开始的编排同传统方法一样，假设现在有7个队参加单循环，分别抽签成为1-7队，由于贝格尔编排法必须是双数队，所以再加一个0队，与0队比赛表示该队轮空，现在必须定下一个数为参照数，因此我们假设0为参照数(任意数都可以，一般取0或者最大数)，第一轮的对阵形式如下: 1 – 0 2 – 7 3 – 6 4 – 5 这个大家都能看明白，这跟贝格尔编排法无关，第二轮则开始相关了。在第一轮中，0在右边，现在我们要在第二轮让它换成左边，第三轮又让它换回右边，反反复复，到最后一轮即第七轮时，它还是在右边。我们把0安排好后，再把第一轮右下角的5提到右上角来，因此第二轮的第一场比赛就变成: 0 – 5 然后我们还要回到第一轮的八个数字来，我们假设它是一个环，无论是顺时针还是逆时针，它们的位置是相对固定的(除了它们与0的位置有时候会改变外，因为0的位置是先定好的)，比如按照顺时针方向看，5的前面是6，后面是4，因此，第二轮我们还是安排5的前面是6，后面是4，0我们假设它不存在，于是第二轮的第一、二场比赛就是: 0 – 5 6 – 4 那其他怎么办呢，照旧轮呗，就像排球的轮转一样，于是第二轮就是 0 – 5 6 – 4 7 – 3 1 – 2 其他依次类推。 无论比赛队是单数还是双数，最后一轮时，必定是“0”或最大的一个代号在右上角，“1”在右下角。 根据参赛队的个数不同，应按规定的间隔数移动(见表)。 间隔移动 参赛队数 间隔数 轮转次数 4队以下 0 1 5~6队 1 2 7~8队 2 3 9~10队 3 4 11~12队 4 5 根据上面所讲，我们可以得到如下模型:将参赛选手(以7人为例，8为虚拟选手)，按图一排 列,根据连线进行比赛，得第一天比赛安排，然后将除8外的数字按顺时针(或逆时针旋转，此时n 取8)n/2-1个位置，如图二，即得第二天的比赛安排，以此类推，直至第n-1天， 比赛完成。 8 8 1 4 顺 时2 7 5 3 针 旋 转3 6 6 2 3 个4 5 7 1 位 图一 图二 置 (采用C语言代码)代码如下: #include #define MAXSIZA 32 //最大参赛队伍个数 void main() { int m,n,i; int a[MAXSIZA][MAXSIZA]; //用于日程表存储 //输入处理 printf("请输入参赛队伍个数(2-%d):",MAXSIZA); scanf("%d",&m); while(m>MAXSIZA || m<2) { printf("输入数据有误，请重新输入参赛队伍个数(2-%d):",MAXSIZA); scanf("%d",&m); } //奇数个选手，虚拟一个选手，使之成为偶数 n=m+m%2; //给选手编号，存储在数组第一列 for(i=0;i