循环赛日程表

问题描述:
设有n(n = 2^k)位选手参加网球循环赛，循环赛共进行n-1天，每位选手要与其他n-1位选手比赛一场，且每位选手每天必须比赛一场，不能轮空。试按此要求为比赛安排日程:
 (1) 每个选手必须与其他n-1个选手各赛一场；
 (2) 每个选手一天只能赛一场；
 (3) 循环赛一共进行n-1天。

选手
第一天
第二天
第三天
第四天
第五天
第六天
第七天
1
2
3
4
5
6
7
8
2
1 
4
3
6
5
8
7
3
4
1
2
7
8
5
6
4
3
2
1
8
7
6
5
5
6
7
8
1
2
3
4
6
5
8
7
2
1
4
3
7
8
5
6
3
4
1
2
8
7
6
5
4
3
2
1

#include<stdio.h>

const int N=8;
int mat[N][N];

void print(int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            printf("%4d",mat[i][j]);
        printf("\n");
    }
    printf("***********************************\n");
}

void evaluate(int n)                                    
{
    int m=n/2;
    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
        {
            mat[i+m][j]=mat[i][j]+m;                    
            mat[i][j+m]=mat[i+m][j];                    
            mat[i+m][j+m]=mat[i][j];                    
        }
    print(N);
}

void solve(int n)
{
    if(n==1)
    {
        mat[0][0]=1;
        return;
    }

    solve(n/2);
    evaluate(n);
}

int main()
{
    
    solve(N);
    //print(N);


    return 0;
}

 

算法思路：

将正方形等分成四个子正方形，左上方的子正方形可以容易地画出，左下方的子正方形与左上方的子正方形性质一样（可认为两者相互独立），但为了区别选手，就可以只在左上方的子正方形的每个选手编号加上固定的偏移量m得到左下方的子正方形，然后在正方形的右边放置颠倒的正方形的左边，即右上方、右下方的子正方形分别放置左下方、左上方的子正方形，这样放置恰好满足题目要求。