一、循环赛日程表问题

《算法设计与分析（第5版）》-王晓东，第35页

１. 问题描述

设有n=2^k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：

1. 每个选手必须与其他n-1个选手各赛一次；
2. 每个选手一天只能参赛一次；
3. 循环赛在n-1天内结束。

2. 问题分析

按此要求，我们可以将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。

3. 算法思想

1. 按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。
2. 递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。
3. 这时只要让这两个选手进行比赛就可以了。

例如： 8个运动员的网球循环赛日程表：

• 如下图，所列出的正方形表是8个选手的比赛日程表。
• 其中左上角与左下角的两小块分别为选手 1 至选手 4 和选手 5 至选手 8 前3天的比赛日程。
• 据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。
• 依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。
  

4. 算法步骤

以k=3，即n=8 为例：

1. 填写第一行为1，2，3，4，5，6，7，8；
2. 将问题分为3(k)部分：前2(2¹)行、前4(2²)行、前8(2³)行；
   1. 第 1 部分：前 2 行；根据 前1行 填写 后1行；
      • 将前2行再以2列为单位分为四份，每一份中第二行按照对角线规则填写第一行对应位置的值；
   2. 第 2 部分：前 4 行；根据 前2行 填写 后2行；
      • 将前4行再以4列为单位分为两份，每一份中第三、四行按照对角线规则填写第一、二行对应位置的值；
   3. 第 3 部分：前 8 行；根据 前4行 填写 后4行；
      • 将前8行再以8列为单位分为一份，每一份中第五、六、七、八行按照对角线规则填写第一、二、三、四行对应位置的值；
3. 实际填充方式如下图所示：
   

二、分治算法实现

1. 编写程序代码

// 循环赛日程表
#include<iostream>
#include<cmath>
using namespace std;

void schedule(int k, int n, int** array);

int main()
{
    int k;  // 运动员的人数n=2^k
    cout << "运动员的人数为n（n=2^k），请输入k的值：";
    cin >> k;
    int n = pow(2, k);  // 运动员的人数n=2^k

    int** array = new int* [n+1]; // 循环赛日程表
    for (int i = 0;i < n+1;i++) 
        array[i] = new int[n+1];

    // 填充日程表
    schedule(k, n, array);
    
    // 输出日程表
    cout << "\n循环赛日程表为：\n";
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= n;j++)
            cout << array[i][j] << " ";
        cout << "\n";
    }
    
    // 删除二维数组
    for (int i = 0;i < n + 1;i++)
        delete[] array[i];
    delete[] array;
    return 0;
}

void schedule(int k, int n, int** array)   // 数组下标从1开始
{
    for (int i = 1;i <= n;i++)  // 第一行排1-n
        array[1][i] = i;
    
    int m = 1;  // 用来控制每一次填表时i行j列的起始填充位置
    
    for (int s = 1;s <= k;s++)  // k指分成k大部分进行填充日程表；s指第几大部分
    {
        n = n / 2;
        for (int t = 1;t <= n;t++)  // 第s部分内的循环
        {
            for (int i = m + 1;i <= 2 * m;i++) // 行
            {
                for (int j = m + 1;j <= 2 * m;j++) // 列
                {
                    array[i][j + (t - 1) * m * 2] = array[i - m][j + (t - 1) * m * 2 - m];       //左上角等于右下角的值
                    array[i][j + (t - 1) * m * 2 - m] = array[i - m][j + (t - 1) * m * 2];       //左下角等于右上角的值
                }

            }

        }
        m *= 2;
    }

}

2. 运行结果展示

三、友情链接~

• 其它一些常见算法请参阅此链接~

---

最后，非常欢迎大家来讨论指正哦！