原文地址：https://ericpengshuai.github.io/suan-fa/cd0cd01e2295.html

例题
设有N个运动员要进行网球循环赛，设计一个满足以下要求的比赛日程表
（1）每个选手必须与其他n-1个选手各赛一次；
（2）每个选手一天只能赛一次；
（3）当n 是偶数，循环赛进行n-1简单天，当n是奇数，循环赛进行n天。

分析

1. 首先考虑简单问题（n = 2^k）
这个我先上一个图大家应该就可以明白：

应该很容易想到分治法，有如下规律：对于任意一个正方形区域（包括4、16……个小方块）左上角和右下角相等，右上角和左下角相等（如果懒得看汉字就直接看上面几种颜色的方块吧）
然后这个代码也很容易：

• 非递归（k是2上面的次数）

void SetTable(int **a, int k)
{
    //初始化左上角数
    a[0][0] = 1;
    a[0][1] = 2;
    a[1][0] = 2;
    a[1][1] = 1;
    //然后分治安排
    for(int i = 2; i <= k; i++)
    {
        int len = 1 << i;   //len = 2^i
        int half = len / 2; 
        //左下角子表就是左上角子表加上half
        for(int row = half; row < len; row ++)
        {
            for(int col = 0; col < half; col ++)
            {
                a[row][col] = a[row - half][col] + half; 
            }
        }
        //右上角子表就是左下角子表
        for(int row = 0; row < half; row ++)
        {
            for(int col = half; col < len; col ++)
            {
                a[row][col] = a[row + half][col - half];
            }
        }
        //右下角子表就是左上角子表
        for(int row = half; row < len; row ++)
        {
            for(int col = half; col < len; col ++)
            {
                a[row][col] = a[row - half][col - half];
            }
        }
    }
}

• 递归（n是比赛总人数，这里先考虑简单的n = 2^k）

void tourna(int n, int **a)
{
    if(n == 1)
    {
        a[0][0] = 1;
        return;
    }
    tourna(n/2, a);
    copy(n, a);
}
void copy(int n, int **a)
{
    int m = n / 2;
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < m; j++)
        {
            a[i + m][j + m] = a[i][j];  //右下角
            a[i + m][j] = a[i][j] + m;  //左下角
            a[i][j + m] = a[i + m][j];  //右上角
        }
    }
}

2.衍生到一般的偶数（如果n不是2的次方）
举一个例子（n=6），既然是分治法，按照大的思路，我们把tourna(6, a)问题转换成tourna(3, a)【这里的你们就先看成是上面的tourna函数】，那么问题又来了，n=3怎么解决呢？（自然引出了奇数的问题，那我们直接考虑下面的奇数问题，这里大家可以直接跳到第三种情况看，看完之后回看这一点）
我们可以将6分为（1 2 3）和（4 5 6）我们且看两者单独考虑的赛程：
（1 2 3）（4 5 6）

考虑到（1 2 3）（4 5 6）“1和4”的第四列（第三天），只有一号选手和四号选手没比赛，那就让他们比，同理还有2和5，3和6，推出如下图【左图】：
再来分析【右图】，第一行由于（1 5）（1 6）没比赛，后面就填他们，对应的也有（5 1）（6 2），再看第二行可以是（2 4）（2 6），由于6在第五天和1比赛了，所以应该是先填（2 6）然后（2 4），对应的也有（6 2）（4 2）；后面同理。
【其实我感觉这个就是找规律好吗，和分治法有“桃子”关系 】

3.n为奇数
考虑到题目中有n天时间比赛，自然想到n = 4 的情况（看下图）
这个是4个人比赛3天的情况，现在如果只有3个人，那么岂不是正好是3天，我们仅仅需要将其中的4改变为0（看下图），代表选手那天空闲就可

其实对于一般的奇数，我们都可以转换成相应的n + 1，变成偶数再分治求解，最终递归到尽头就是n = 3（然后我们回到第二问）

最终代码整理如下

# include <iostream>
using namespace std;

void output(int **a, int n)
{
    if(n % 2 == 1)  //n为奇数时候的输出
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n + 1; j++)
            {
                if(a[i][j] == n + 1)
                    cout << 0;
                else  cout << a[i][j];
                if (j == n)
                    cout << endl;
                else
                    cout << ' ';
            }
        }
    else    //n为偶数时候的输出
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cout << a[i][j];
                if (j == n - 1)
                    cout << endl;
                else
                    cout << ' ';
            }
        }
}

void copy(int n, int **a)
{
    int m = n / 2;
    //cout << m << endl;
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < m; j++)
        {
            a[i + m][j + m] = a[i][j];  //右下角
            a[i + m][j] = a[i][j] + m;  //左下角
            a[i][j + m] = a[i + m][j];  //右上角
        }
    }
}

void copyodd(int n, int **a)
{
    int m = n / 2;
    int *b = new int[n];
    for(int i = 0; i < m; i++)
    {
        b[i] = m + i + 1;   // 4 5 6
        b[m + i] = b[i];    // 4 5 6
    }
    for(int i = 0; i < m; i ++)
    {
        for(int j = 0; j < m+1; j ++)   //改写左上角和填写右下角
        {   //这里如果你硬要说什么解释的话，我也说不出啥来，我看来就是找规律
            if(a[i][j] > m) 
            {
                a[i][j] = b[i];
                a[m + i][j] = (b[i] + m) % n;
            }
            else a[m +i][j] = a[i][j] + m;
        }
        for(int j = 1; j < m; j++)  //填写右上角和对应的右下角
        {   //这里我当时是把 n = 6作为特例带进去一个一个是试出规律来的
            a[i][m + j] = b[i + j];
            a[b[i + j] - 1][m + j] = i + 1;
        }
    }
}

void makecopy(int n, int **a)
{
    if((n/2 > 1) && ((n/2)%2 == 1)) copyodd(n, a);
    else copy(n, a);
}

void tourna(int n, int **a)
{
    if(n == 1)
    {
        a[0][0] = 1;
        return;
    }
    if(n % 2 == 1) 
    {
        tourna(n+1, a); //奇数+1变成偶数
        return;
    }
    tourna(n/2, a); //分治
    makecopy(n, a);
}

int main()
{
    int n;
    cin >>n;
    int **a = new int *[2*n];
    for(int i = 0; i < 2*n; i++)	//分配空间
        a[i] = new int[2*n];
    tourna(n, a);
    output(a, n);
    for(int i = 0; i < 2*n; i ++)	//delete空间
        delete []a[i];
    delete []a;
    return 0;
}