分治法实现循环赛算法笔记

发表于 | 分类于

前言

没有前言，rt

正文

上周算法设计课的老师布置了这个作业，完成了之后就打算顺便记录下来，以后也会陆续放一些算法设计课的作业和笔记。

题目

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

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

简单情况

这个题目要求n没有限制，其实是有一点难度的，我们可以先考虑一种简单的情况，限制$n=2^k$.
这样在进行二分实现的时候，可以均匀划分，然后通过对子问题的解直接复制，可以容易的构造出原问题的解，如图
循环赛示意图

容易发现，在$n=2^k$的情况下，将子问题的解直接复制到対角问题就可以直接得到原问题的解。

进一步理解问题，可以发现，其实对能够直接复制子问题到对角的情况的限制并不是原问题的规模一定满足是2的k次冪，而是满足原问题与子问题的规模都是偶数，换句话说，只要原问题能够分割为两个规模大小相等且子问题的规模为偶数，就可以将两个子问题的解通过复制得到原问题的解。

还有一个值得注意的地方，当原问题及其子问题均为偶数规模时，两个子问题可以看作镜像关系，考虑上图左半部分，将其继续分割为两部分，可以看作原问题[1:8]分解为[1:4]和[5:8]两个子问题，子问题的规模为4,可以通过将子问题[1:4]中的排列，每一位加上4得到另一个子问题的解。姑且将这种关系理解为镜像关系（规模为2n的问题中，i与i+n互为镜像，i<=n）吧。

先贴上限制情况的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<cstring>
using namespace std;

int arrange (int**  arr,int len){
    if(len == 1){   //规模为1，置初值
        arr[1][1] = 1;
        return 0;
    }
    arrange(arr,len / 2);
    //扫描子问题[1:len/2][1:len/2]
    for (int i = 1; i <= len/2; i++){
        for (int j = 1; j <= len / 2; j++){ //完成对镜像问题和对角位置的复制
            arr[i][j + len / 2] = arr[i + len / 2][j] = arr[i][j] + len / 2;
            arr[i + len / 2][j + len / 2] = arr[i][j];
        }
    }
    return 0;
}

int main(){
    int k = 0;
    cout << "input num of player: ";
    cin >> k;
    int **arr = new int *[k + 1];
    for (int i = 0; i <= k; i++)
        arr[i] = new int[k + 1];
    memset(arr, 0, sizeof(arr));
    arrange(arr, k);
    for (int i = 1; i <= k; i++){
        for (int j = 1; j <= k;j++){
            cout << arr[i][j];
            cout << (j == 1 ? ": " : " ");
        }
        cout << endl;
    }
    return 0;
}

这段代码要求传入原问题规模严格为2的n次冪，否则程序应该很可能大概率会崩掉，不过不重要不重要。。
经过上面的分析，理解这段代码应该是没有太大问题的，这里就不过多赘述了。

完整情况

上面的讨论有严格的限制条件，现在来讨论无限制情况下，如何利用上面的分析结果完成循环赛的安排。这里分别讨论博主解决问题时想到的几种思路。

第0种思路

考虑分解原问题过程中，如果遇到原问题的规模为奇数$2k-1$，则求解问题规模为$2k$的问题，进一步将其分割为两个规模为$k$的子问题。如果按照上面的讨论，将其简单拼接，得到的原问题的解就会超过要求的$2k-1$，读者可自行用规模为5的原问题代入验证。

第1种思路

通过对第一种思路的思考，可以知道，面对原问题或子问题为奇数的情况不能简单应用复制子问题和镜像问题的解，需要做特别处理。
具体处理奇数规模的办法博主最后还是没想出来，但是在网上找到了解法，最后看了几遍代码，感觉挺有道理的，但是数学功底不够，没法完全证明该方法是对的。接下来的讨论就是对网上找到的处理方法的分析。

抄来的思路

  1. 首先从解决原问题开始
  • 如果原问题规模是偶数2k，就递归分治求解原问题一半规模的子问题
  • 如果原问题规模是奇数2k-1，就改为求解规模为2k的原问题（称为凑偶后的原问题），递归求解规模为k的子问题，求解过程中引入编号为2k的虚选手
  • 对于子问题而言，原问题和凑偶的原问题等价
  • 注意，虚选手是对应当前子问题和其原问题而言
  1. 子问题的递归求解结束后，开始通过对子问题的解合并处理得到原问题的解
    • 若子问题的规模为偶数2k，那么不存在引入虚选手的情况，只需要如简单情况中，对子问题[1:k]进行直接复制即可
    • 若子问题的规模为奇数(2k-1)，则对应原文题规模为4k-2,此时对于原问题而言，编号2k的选手为需要忽略的虚选手
  2. 区别处理的方法是按顺序取余（下文具体讲）

觉得上面讲的比较抽象的话，可以看下面的示意图，以规模为6的原问题为例
规模为6的示意图1
规模为6的示意图2

  1. 图1为规模为6的原问题（红色部分仅为坐标，无意义），此时传入规模为3的子问题进行求解，如图2
  2. 规模为3时，需要凑偶为规模为4的原问题，接着对规模为2的子问题求解，如图3
  3. 得到规模为2的问题的解后，应用简单情况的做法，将图3中绿色部分的解复制得到图4中黄色部分。黄色部分与绿色部分即为问题规模为4的问题的解。其中编号4的选手为虚选手，即图中标x位置为额外引入
  4. 得到规模为4的子问题的解后（图5），对于规模为6的原问题需要解决对剩余部分的填充。
  5. 对于规模为6的原问题，分割所得的两个规模为3的子问题，在简单情况中，[1:3]和[4:6]还是互为镜像的两部分，可使用复制的镜像元素的方法覆盖[4:6][1:3]区域，如图6
  6. 接着对之前引入的虚选手进行消除，对第i列的x位置，填入选手i的镜像选手如第一天（蓝色第二列），在蓝色第三行x中填入3的镜像选手6,在蓝色第六行x中填入6的镜像选手3。如图7
  7. 最后需要解决剩余两列的安排，经过前面的分析可以知道，对于规模为2(2k-1)的问题，i(i<=2k-1)号选手与1~2k-1位选手及其镜像选手(i+2k-1)的比赛已经在前(2k-1)天安排完。意味着，对于第i位选手，在剩余的第2k~2(2k-1)-1天需要安排其与2k～2(2k-1)中除去i的镜像选手的2k-2位选手的比赛。代入规模为6,即第1～3号选手之间的比赛与其中任一选手与其镜像选手的比赛已在前三天安排完毕，1～3号选手中每人需要与4～6号选手中除去对应镜像选手后剩余两位选手比赛。
  8. 对剩余两位选手的比赛就需要用顺序取余的办法安排。对于i(i<=2k-1)号选手，令其在第2k天与其镜像选手的下一顺位选手{i+[2k-1]+1)%(2k-1) + (2k-1)}比赛，以此类推。
  9. 对第1～2k-1位选手的剩余比赛安排后，如图8绿色部分。最后再将该绿色部分复制到下半部分对应镜像选手中即可得到规模为6的原问题的解（最后一张图就不放啦）

贴上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>

using namespace std;

void arrange(int** arr,int len)
{
    if (len == 1){
        arr[1][1]=1;
        return ;
    }
    if(len&1) 
        len++;                          //len为奇数，转化为求解len+1的情况
    int half_len=len/2;
    arrange(arr, half_len);             //已完成规模为half_len的排列，即矩阵[1：half_len][1：half_len+1]，表示对half_len位选手在第2～half_len天内的安排
    for(int i=1;i<=half_len;i++)
        for(int j=1;j<=half_len+1;j++){
            if(arr[i][j]>half_len){     //当前位置为第i位选手对阵第half_len+1号选手（虚选手），表示该位置对i选手空闲
                arr[i+half_len][j]=i;   //对当天的两个空位进行填补，由于矩阵[half_len+1:len][1:half_len+1]为[1:half_len][1:half_len+1]的镜像
                arr[i][j]=i+half_len;   //可使互为镜像的两个选手在当天（第1-half_len天内空闲的一天）比赛

                int c=i+half_len+1;     //c为与i为镜像的选手的下一顺位选手，i与其镜像选手的比赛在第1～half_len天已安排
                for(int k=half_len+2;(half_len&1)&&k<=len;k++,c++){
                    //k为[half_len+2:len]循环，安排i选手与其他非镜像选手的比赛
                    if(c==i+half_len)  c++;    //若c为当前排列选手的镜像选手，则按顺位取下一位选手
                    if(c>len) c-=half_len;     //对t在范围[half_len+1:len]中取余
                    arr[i][k]=c;        
                    arr[c][k]=i;
                }
            }
            else{                                           //当前与第i号选手比赛的是1～half_len号，互不为镜像选手
                arr[i+half_len][j]=arr[i][j]+half_len;      //复制第i位选手的安排成为其镜像选手的比赛安排
                if((half_len%2==0)||half_len==1){           //对于子规模为偶数的情况，复制子问题[1:half_len][1:half_len]至[1:len][1:len]
                    arr[i+half_len][j+half_len]=arr[i][j];
                    arr[i][j+half_len]=arr[i+half_len][j];
                }
            }
        }
}

int main()
{
    int k;
    char blank = 'x';
    cout << "input num of player: ";
    cin >> k;
    int **arr = new int *[k + 2];
    for (int i = 1; i <= k+1; i++)
        arr[i] = new int[k + 2];
    memset(arr,0,sizeof(arr));
    if(k&1)
        arrange(arr, k + 1);
    else
        arrange(arr, k);
    for (int i = 1; i <= k; i++)
    {
        for(int j=1;j<=k+(k&1);j++)
        {
            if(arr[i][j]>k)
                cout << 'x';
            else
                cout << arr[i][j];
            cout << (j == 1 ? ": " : " ");
        }
        cout<<endl;
    }
}

结语

打算把这篇博客当作实验报告交上去hhh

用钱砸我