乒乓球循环赛日程表设计

问题描述

设计一个乒乓球循环赛的日程表，满足以下条件：

1. 每个选手必须与其他所有 $ n-1 $ 个选手各赛一次。
2. 每个选手一天只能参赛一次。
3. 循环赛在 $ n-1 $ 天内结束。
4. 参赛选手的人数必须是 $ 2^k $ 个。

输入格式

输入一个整数 $ N $，表示参加循环赛的运动员数量。

输出格式

输出一个二维数组，以矩阵的形式展示每个运动员的比赛对手。其中，第一列代表每个运动员的选手号，之后的每一列代表每一天与其进行比赛的对手。

示例

输入示例： [8]

输出示例： [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]

解题思路

根据输出样例，可以观察到循环赛日程表存在以下规律：

• 当我们将所有的选手分成两组（即 $ n/2 $），赛程表可以被分割成四个 $ n/2 \times n/2 $ 的子赛程表。在这四个子赛程表中，左上角的赛程表与右下角的相同；而左下角的赛程表与右上角的相同。
• 进一步地，如果再次将每组选手再分成一半（即 $ n/2/2 $），那么每个 $ n/2 \times n/2 $ 的赛程表又可以被进一步分割为四个 $ n/4 \times n/4 $ 的子赛程表。对于这些 $ n/4 \times n/4 $ 的子赛程表，左上角的与右下角的相同；而左下角的与右上角的相同。

因此可以使用分治策略解决以上问题。

解题代码（递归方法）

#include<iostream>
#include<vector>
using namespace std;

void copy(vector<vector<int>>& a, int i1, int j1, int i2, int j2, int n);
void table(vector<vector<int>>& a, int i, int j, int n);

int main() {
    int size;
    cout << "选手数量(2的n次幂):";
    cin >> size;
    vector<vector<int>> a(size, vector<int>(size, 0));
    for (int i = 0; i < size; i++) { // 根据递归算法，应先给第一列赋值
        a[i][0] = i + 1;
    }
    cout << "----------------------------------------" << endl;
    table(a, 0, 0, size);
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

void table(vector<vector<int>>& a, int i, int j, int n) {
    if (n == 0) return;
    table(a, i, j, n / 2);           // 先处理左上方表格
    table(a, i + n / 2, j, n / 2);  // 再处理左下方表格
    copy(a, i, j, i + n / 2, j + n / 2, n / 2); // 左上方表格复制到右下方
    copy(a, i + n / 2, j, i, j + n / 2, n / 2); // 左下方表格复制到右上方
}

void copy(vector<vector<int>>& a, int i1, int j1, int i2, int j2, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            a[i2 + i][j2 + j] = a[i1 + i][j1 + j];
        }
    }
}
非递归解法
#include<iostream>
#include<vector>
using namespace std;

void table(vector<vector<int>>& a, int size);

int main() {
    int size;
    cout << "选手数量：";
    cin >> size;
    cout << "-----------------------------------------------------" << endl;
    vector<vector<int>> a(size, vector<int>(size, 0));
    for (int i = 0; i < size; i++) {
        a[i][0] = i + 1;
    }
    table(a, size);
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

void table(vector<vector<int>>& a, int size) {
    for (int j = 1; j < size; j *= 2) {
        for (int i = 0; i < size - j; i += 2 * j) {
            for (int k = i; k < i + j; k++) {
                for (int l = 0; l < j; l++) {
                    a[k + j][l + j] = a[k][l];
                }
            }
            for (int k = i + j; k < i + 2 * j; k++) {
                for (int l = 0; l < j; l++) {
                    a[k - j][l + j] = a[k][l];
                }
            }
        }
    }
}