网球循环赛算法剖析

设有n个运动员要进行网球循环赛。设计一个满足下列条件的比赛日程表：

• 每个选手必须与其他n-1个选手各赛一次
• 每个选手一天只能赛一次
• 当n是偶数时，循环赛进行n-1天
• 当n是奇数时，循环赛进行n天

程序运行说明

编译运行源代码，提示输入参赛者的数目，以9个参赛者为例，显示如下：

Please input the number of contestants:
9
File "result.dat" created.
复制代码

表示程序运行完毕，输出结果在可执行文件相同目录下的 result.dat 文件中

此时， result.dat 文件中输出结果如下：

The tournament shall be arranged as follow:
选手编号:    1    2    3    4    5    6    7    8    9    
第1  天:     2    1    8    5    4    7    6    3    0    
第2  天:     3    5    1    9    2    8    0    6    4    
第3  天:     4    3    2    1    0    9    8    7    6    
第4  天:     5    7    4    3    1    0    2    9    8    
第5  天:     6    4    5    2    3    1    9    0    7    
第6  天:     7    8    9    0    6    5    1    2    3    
第7  天:     8    9    0    6    7    4    5    1    2    
第8  天:     9    0    6    7    8    3    4    5    1    
第9  天:     0    6    7    8    9    2    3    4    5       
复制代码

其中，其中一行代表一天，每一列代表一个选手，即第i行j列表示第i天第j个选手的对手编号，行号列号从1开始计（第零行为选手编号，不算在表格中，从第一天开始为第一行）

若参赛者为奇数个，则会出现数字0，代表该参赛者当天没有比赛

算法设计说明

写在前面

本算法核心参考链接在此，但在原作者的算法上做了一定修改

一些函数和写法的解释

在参考链接中作者提供的算法之中有一些本人之前没见过或者没用过的写法和巧妙的运算方法、函数等，在此先加以罗列

1. setw()函数：包含在 iomanip 头文件中，为固定设置字符宽度的函数，默认控制右对齐，若想要进行左对齐需要加入left控制符号，如下：

   outfile << left << setw(17) << "选手编号: ";
   复制代码

2. ceil()函数：包含在 cmath 头文件中，是一个向上取整的函数，即 ceil(n) 返回不小于n的最小整数。需要特别注意的是，这个函数在头文件中定义时返回值类型为double型，故实际使用时，若涉及到整数的传参需要把返回类型强制转换成int型，如下：

   tournament((int)ceil(n / 2.0),table);
   复制代码

   还需要注意的一点是，ceil的输入也是double型的，这意味着对于整数n，上面函数中若写为 ceil(n/2) ，则括号内部为整数除法，返回的值是整数除法的结果，自然也是整数，而不是double，此时会引起错误。故应写为 ceil(n/2.0)
3. 符号"&"的用法：如下面这个实例中：

   if(n & 1){
        for (int i = 1; i <= total_days;i++){
            for (int j = 1; j <= n;j++){
                if (table[i][j]==n+1)
                    table[i][j] = 0;
            }
        }
    }
   复制代码

   符号"&"单个使用时表示按位与，在上面的例子（是程序源码的一部分）中的含义即，将n转变为二进制，之后再和1按位与。显然，当n为奇数的时候表达式为1，否则为0，故这个语句可以作为判断n是否是奇数的判断语句，非常简洁
4. 此外，在写算法的时候发现，对于二位数组和二重指针的参数传递来说，二者并不是等效的，即在下面这段代码中

   int **table = new int *[n + 2];
    for (int i = 0; i < n + 2;i++)
        table[i] = new int[n + 2];
   
    tournament(n, table);
   复制代码

   其中tournament函数定义为：

   void tournament(int n,int **table)
   复制代码

   在这种情况下必须使用二重指针动态分配内存的方式来初始化table，而不能直接建立一个二维数组 table[n+2][n+2]

算法描述

先贴上完整代码

#include<fstream>
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;

void Show_Result(int n,int **table)//将结果按行（即按天）输出到文件中
{
    ofstream outfile;
    outfile.open("result.dat");
    outfile << "The tournament shall be arranged as follow:" << endl;
    int total_days = n & 1 ? n : n - 1;
    outfile << left << setw(17) << "选手编号: ";
    for (int i = 0; i <= total_days;i++){
        if(i)
            outfile << "第" << left << setw(3) << i << left << setw(9) << "天:";
        for (int j = 1; j <= n;j++){
            if (!i)
                table[0][j] = j;
            // cout << table[i][j] << "\t";
            outfile << setw(5) << table[i][j];
        }
        // cout << endl;
        outfile << endl;
    }
        outfile.close();
}

void merge(int n,int **table)
{
    int m = (int)ceil(n / 2.0);//m中记录n/2向上取整的值，注意一定是2.0而不能是2，因为如果是2则括号内部为整数除法
    int total_days = n & 1 ? n : n - 1;
    int merged_days = m & 1 ? m : m - 1;//已经排好日常表的天数，注意当m为奇数和偶数时情况的不同

    for (int i = 1; i <= merged_days;i++){//先列后行地横向构造出n个选手前merged_days天的日程表
        for (int j = m+1; j <= n; j++){//从第m+1列开始构造，直到n列结束
            if (table[i][j-m])    //在第i天时，先检查某个选手的对应构造选手（即第j-m个选手）当天对手是否为0号（即当天没有比赛），若不是，正常赋值
                table[i][j] = table[i][j - m] + m;
            else{//若是，则这一天让他俩比赛
                table[i][j] = j - m;
                table[i][j - m] = j;
            }
        }
    }

    //继续构造从第merged_days+1到第total_days的情况
    for (int i = merged_days + 1; i <= total_days;i++){//先构造第1列，数据按行依次加1
        table[i][1] = table[i - 1][1] + 1;
        table[i][table[i][1]] = 1;//一定要注意构造第一行的时候把后面的对应比赛对手的数据也改了！！！
    }
    for (int i = merged_days + 1; i <= total_days;i++){//紧接着修改从第2列到第merged_days的数据，同时修改对应对手的数据
        for (int j = 2; j <= m;j++){
            //先计算对手，这里对手的序号的计算公式不太好想
            //应该是以m+1为基础，依赖于m、这一行的第一个数、该运动员的编号，三者所共同决定
            int rival = m + 1 + (table[i][1] - (m + 1) + (j - 1)) % m;
            //修改自己的值为对手，并修改对手的值为自己
            table[i][j] = rival;
            table[i][rival] = j;
        }
    }

    //如果总人数是奇数，则会出现虚拟的一个人，要把所有和这个虚拟的对手比赛的运动员，对应位置置成0，即没有比赛
    if(n & 1){//符号"&"是按位与的意思，即将n转变为二进制，之后再和1按位与，显然当n为奇数的时候表达式为1，否则为0
        for (int i = 1; i <= total_days;i++){
            for (int j = 1; j <= n;j++){
                if (table[i][j]==n+1)
                    table[i][j] = 0;
            }
        }
    }
}

void tournament(int n,int **table)
{
    if (n==2){//当问题划分为2个运动员时，使两人相互比赛
        table[1][1] = 2;
        table[1][2] = 1;
        // cout << table[1][2];
    }
    else{//若剩余待排日程表人数超过两人，则先解决（n/2向上取整）规模的子问题，之后再将子问题合并
        tournament((int)ceil(n / 2.0),table);
        // Show_Result(n, table);
        merge(n, table);
        // Show_Result(n, table);
    }
}


int main()
{
    int n;
    cout << "Please input the number of contestants:" << endl;
    cin >> n;
    //建立一个存储日程表的二维数组table，其中一行代表一天，从第一列开始每一列代表一个选手
    //即第i行j列表示第i天第j个选手的对手编号
    int **table = new int *[n + 2];
    for (int i = 0; i < n + 2;i++)
        table[i] = new int[n + 2];

    tournament(n, table);
    Show_Result(n, table);//生成的循环赛表格输出到文件中
    cout << "File \"result.dat\" created." << endl;
}
复制代码

实际上算法的设计思路已经都写在注释中了，如果仔细看很快就能看懂算法的架构，在此再简要叙述一下：

1. 先拆分问题，对于用户指定的n，考虑规模为 m = ceil(n/2.0) 的问题，并解决这个子问题，有两种情况
   1. 子问题是偶数，继续重复上面的动作
   2. 子问题是奇数，补充一个虚拟选手m+1，这样一共有偶数个选手，于是继续重复上面的动作
2. 不断拆分直到只剩下两个人，让他们互相比赛即可
3. 回过头来从子问题构造母问题，采取先横向构造、再纵向构造的方法，有两种情况
   1. 子问题是偶数，开开心心地正常构造
   2. 子问题是奇数，由于之前我们扩充了一个虚拟选手使得问题变为了偶数个选手，这时候我们需要把这个虚拟选手清除，并且把所有与他比赛的人，相应的位置编号由m+1变为0，表示这天没有比赛（原本和不存在的人比赛那当然相当于没有比赛了）
4. 重复以上的构造方法，直到问题恢复到n的规模，此时问题解决完毕

其中，“正常构造”是如何操作的还需要详细说明一下： 以6个选手为问题规模举例说明：

选手编号:    1    2    3    4    5    6    
第1  天:     2    1    6    5    4    3    
第2  天:     3    5    1    6    2    4    
第3  天:     4    3    2    1    6    5    
第4  天:     5    6    4    3    1    2    
第5  天:     6    4    5    2    3    1    
复制代码

在这个问题中，实际上算法里的数组长成这个样子：

2    1    6    5    4    3    
3    5    1    6    2    4    
4    3    2    1    6    5    
5    6    4    3    1    2    
6    4    5    2    3    1    
复制代码

其中，最上面一行为算法table二维数组的第1行，同理最左边一列为table中的第一列 在计算这个问题的时候，先完成规模为3的问题的计算，为了完成规模为3的问题，需要先完成规模为2的问题，此时让两个人相互比赛，即：

2    1
复制代码

当试图解决规模为3的问题的时候，我们发现它是奇数，故扩充一个虚拟对手，变为构造一个四个选手的日程表问题，所以接下来我们看一下如何从2个选手构造4个选手： 我们先横向构造，将多的两个人第一天的赛程和前两人对称，比赛对手的编号加2，即：

2    1    4    3  
复制代码

之后再纵向构造，首先，将第一列即第一号选手的对手按照每天增加1构造出来，同时修改对手的信息，即：

2    1    4    3    
3    X    1    X    
4    X    X    1
复制代码

之后，构造前2列（对于规模为n的问题应该是前m列，m定义见上），从还未安排好日常表的那行开始，按照先行再列依次填写前两列中上表中标注为"X"的位置，填写的规则为： 最小的数是m+1，最大的数是n，从这一行第一列的数开始依次循环填写，同时将对应对手的值作以修改 在本例中，即最小的数为3，最大数为选手个数4，第二行第一列为3，则第二行第二列填4，同时第二行第四列填2，表示第二天2号和4号相互对战；之后填写第三行，第三行第一列为4，则填写第三行第二列为3，同时修改第三行第3列为2，如下：

2    1    4    3    
3    4    1    2    
4    3    2    1
复制代码

由于实际上我们需要解决的是3个选手的问题，故我们把多余的去掉，相应位置置0：

2    1    0        
3    0    1       
0    3    2   
复制代码

继续从3个选手构造6个选手 先横向构造，此时我们可以看到和之前的不同在于有数字0的出现，这时先不管0，其余按照之前法则正常横向构造：

2    1    0    5    4    0    
3    0    1    6    0    4    
0    3    2    0    6    5    
复制代码

其实其中的0代表当天这个选手没有比赛，故我们直接让这一天都没有比赛的两个人互相比赛即可

2    1    6    5    4    3    
3    5    1    6    2    4    
4    3    2    1    6    5 
复制代码

接着按照上面的法则，先构造完第一列

2    1    6    5    4    3    
3    5    1    6    2    4    
4    3    2    1    X    X    
5    X    X    X    1    X    
6    X    X    X    X    1  
复制代码

按照之前说的法则依次构造每一行

2    1    6    5    4    3    
3    5    1    6    2    4    
4    3    2    1    6    5    
5    6    4    3    1    2    
6    X    X    X    X    1
复制代码

2    1    6    5    4    3    
3    5    1    6    2    4    
4    3    2    1    6    5    
5    6    4    3    1    2    
6    4    5    2    3    1  
复制代码

最终完成了整个日程表的构造 其余规模的日程表构造同理

写在最后

1. 网球赛日程表的算法从了解算法，查找资料，写算法，到写说明文档，前前后后花费了十个小时左右的时间，在这个过程中收获了很多，比如说判断奇偶的小技巧、调整行宽的函数，等等，当然更重要的是了解了分治问题的架构方法、整体构造思路
2. 循环赛日程表的建立实际上应该还有别的算法，日后有时间希望能继续了解
3. 此算法一定还有很多不足之处，若有任何意见或建议欢迎联系: Ethan_Lee@bupt.edu.cn