网球循环赛赛程安排（分治策略） 循环赛, 网球, 赛程

Beverly

一、问题描述：       设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表：
       （1）每个选手必须与其他n-1个选手各赛一次；
       （2）每个选手一天只能赛一次；
       （3）当n是偶数时，循环赛进行n-1天。当n是奇数时，循环赛进行n天。
二、问题分析和算法设计：
       按分治策略，可以将所有的选手对分为两组（如果n是偶数，则直接分为n/2每组，如果n是奇数，则取（n+1）/2每组），n个选手的比赛日程表就可以通过为（n/2或（n+1）/2）个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。
下图给出的是六个选手的比赛日程表，其中第一列表示1-6个选手，第二列到第六列表示各个选手在第一天到第五天的所遇到的选手。
1   2   3   4   5   6
      2   1   5   3   6   4
      3   6   1   2   4   5
      4   5   6   1   2   3
      5   4   2   6   3   1
      6   3   4   5   1   2
       在这里算法设计的难点就是分开治理后的合并问题。这里我就结合上面给出的6个选手的示例来进行表述。首先，将6个选手分为对等的两组，每组3个选手。然后再递归的将3个选手分为对等两组，每组2个选手。
       在2个选手情况下，这两个选手比赛。可以得到两个选手的日程安排表是：
1   2
      2   1
       接下来的任务是合并这两组2个选手的日程表得到3个选手的日程安排表，这里我先假设有4个选手参加比赛则：
1   2
      2   1
      3   4
      4   3
接下来的比赛里，第二天让1和3比赛，2和4比赛；第三天让1和4比赛，2和3比赛，即让前一组的选手，循环的和后一组的选手比赛，可得到比赛日程安排表是：
       1   2   3   4
      2   1   4   3
      3   4   1   2
      4   3   2   1
这里要得到的是3个选手的日程安排表，则第4个选手是假想的选手将其用0来表示则得到3个选手的日程安排表：
1   2   3   0
2   1   0   3
3   0   1   2
接下来的任务是合并这两个3个选手的日程安排表得到6个选手的日程安排表，这里我们的两组选手前3天的比赛情况如下：

1   2   3   0
2   1   0   3
3   0   1   2
4   5   6   0
5   4   0   6
6   0   4   5
其中第一天选手3和选手6都没有对手，让他们两个比赛；第二天选手2和选手5没有对手，让他们两个比赛，；第三天选手1和选手4没有对手，让他们两个比赛。这就可以得到合并后6个选手前三天的比赛日程安排表：
1   2   3   4
2   1   5   3
3   6   1   2
4   5   6   1
5   4   2   6
6   3   4   5
将在前三天比过赛的两组的选手对应的列出来：
1     2     3
4     5     6
在这里可以看到合并的两组中3和6，2和5，1和4都已经比过了，这里就跳过这些选手的比赛，然后两个组循环比赛即：
       1     2     3
       5     6     4
和
       1     2     3
       6     4     5
这样就得到了6个选手的比赛完整的日程安排表：
1   2   3   4   5   6
      2   1   5   3   6   4
      3   6   1   2   4   5
      4   5   6   1   2   3
      5   4   2   6   3   1
      6   3   4   5   1   2
三、证明算法的正确性：
（1）       在n=2时，就这两个选手比赛，比赛只进行一天，这也是算法的初始情况，算法成立。
（2）       在n=k时，如果k为偶数，则将k个选手分为k/2的两组，这样按问题的要求k个选手共比赛k-1天，k/2个选手如果是偶数则比赛（k/2）-1天，在合并的时候两组k/2个选手循环比赛需要k/2天，则先分组后合并共需要（k/2）-1+（k/2）=k-1天；k/2个选手如果是奇数则比赛k/2天，在合并的时候两组中每个选手都相对应的比赛过了一次，所以两组k/2个选手循环比赛需要（k/2）-1天，则先分组后合并共需要（k/2）+（k/2）-1=k-1天。
（3）       k为奇数的情况和k为偶数的情况类似。

canhui87

/*循环赛日程表*/
/*递归法*/
#include "stdio.h"
#include "conio.h"

int a[100][100]={0};            /*数组a为全局变量*/
int b[100]={0};

/*n为偶数复制*/
void copy(int n)
{
    int i,j,m=n/2;
    for(i=0;i<m;i++)
        for(j=0;j<m;j++)
        {
            a[j+m]=a[j]+m;    /*左下角相对左上角同列元素加n/2*/
            a[i+m][j]=a[j+m];    /*右上角复制左下角*/
            a[i+m][j+m]=a[j];    /*右下角复制左上角*/
        }
}
/*n为奇数复制*/
void copyodd(int n)
{
    int i,j,m=n/2;
    for(i=0;i<m;i++)
    {
        b=m+i;b[m+i]=b;
    }
    for(i=0;i<m;i++)
    {
        for(j=0;j<m+1;j++)
        {
            if(a[j]>m){a[j]=b;a[m+i][j]=(b+m)%n;}
            else a[m+i][j]=a[j]+m;
        }
        for(j=1;j<m;j++)
        {
         a[m+j]=b[i+j-1];
         a[b[i+j-1]][m+j]=i;
        }
    }
}
/*复制函数*/
void makecopy(int n)
{
    if(n/2>1&&n%2==1)copyodd(n);
    else copy(n);
}

/*划分函数*/
void tournament(int n)
{
    if(n==1){a[0][0]=1;return;}
    else if(n%2==1){tournament(n+1);return;}
    tournament(n/2);
    makecopy(n);
}



void main()
{

    int i,j,n=6;

    tournament(n);
    for(i=0;i<n;i++)            /*输出日程表*/
    {
        for(j=0;j<n;j++)
        {
            printf("%5d",a[j]);
        }
        printf("\n");
    }

    getch();
}


这是课本的算法
程序执行结果不是想要的
不过对其中的当n为奇数的复制函数不明白

yellow

你这样不认真的程序员会给别人带来很到损失

yellow

代码你输错了好多地方