循环比赛日程表-分治法.doc

比赛日程表
本题由分治法求出循环比赛的日程表。其满足的条件为:
(1)每个选手必须与其他n-1个选手各赛一次;
(2)每个选手一天只能赛一次;
(3)循环赛一共进行n-1天。
按分治策略,将所有的选手分为两半,n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割,直到只剩下2个选手时,比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了
其c语言实现代码如下:
#include <>
#include <>
void gametable(int k);
void main()
{
int k;
printf("比赛选手的个数为n(n=2*k),请输入参数K(k>0):\n");
scanf("%d",&k);
if(k!=0)
gametable(k);
}
void gametable(int k)
{
int a[100][100];
int n,temp,i,j,p,t;
n=2; //k=0两个参赛选手日程可以直接求得
a[1][1]=1;
a[1][2]=2;
a[2][1]=2;
a[2][2]=1;
for(t=1;t<k;t++) //迭代处理,依次处理2^1....2^k个选手的比赛日程
{
temp=n;
n=2*n;
for(i=temp+1;i<=n;i++) //填左下角元素
{
for(j=1;j<=temp;j++)
{
a[i][j]=a[i-temp][j]+temp; //左下角和左上角元素的对应关系
}
}
for(i=1;i<=temp;i++) //将左下角元素抄到右上角
{
for(j=temp+1;j<=n