循环赛日程安排 – 170521328 赵英博

问题背景（自定）

设有n=2^k个选手要进行循环赛，设计一个满足以下要求的比赛日程表：

• 每个选手必须与其他n-1个选手各比赛一次
• 每个选手一天只能比赛一次

问题分析

每个选手必须与其他选手比赛一次，那么就设计一个n×(n-1)的二维表，其中，(i, j)表示和第i个选手在第j天比赛的选手。

我们可以对这个二维表进行分割，分割成两个部分，譬如n＝2^k个选手的日程表就可以分成两个n/2＝2^(k-1)的日程表

在进行递归分割

分割直到只剩下两个选手

比赛日程表在这个时候就很简单了，让这两个人直接进行比赛就好了

假设有八个人比赛

整个求解过程是自底向上的迭代过程，其中表格c左上角和左下角分别为选手1到选手8前三天的比赛日程

将左上角复制到右下角，将左下角复制到右上角，就安排了选手1到选手8后四天的比赛日程

• 表格a

1	2
2	1

• 表格b

1	2	3	4
2	1	4	3
3	4	1	2
4	3	2	1

• 表格c

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

将求解2^k个选手比赛日程规划分解为2^1，2^2，2^k个选手的比赛日程问题，通过迭代的方法将问题解决

流程描述

每次迭代中，将问题划分为了四部分

左上角

是2^(k-1)个选手在前半程的比赛日程

左下角

是另外2^(k-1)个选手在前半程的比赛日程

右上角

左下角复制得来，是2^(k-1)个选手在后半程的比赛日程

右下角

左上角复制得来，是另外2^(k-1)个选手在后半程的比赛日程

代码实现

使用语言Javascript

// 根据人员数创建合适大小的空数组
function createArray(k) {
  let arr = new Array(k).map(item => return new Array(k))
  return arr
}
// 主函数需要传入选手参数数k
function gameTable(k) {
  // n=2^k(k≥1)个选手参加比赛
  let table = createArray(k)
  let n = 2;
  //求解2个选手比赛日程，得到左上角元素
  table[0][0]=1; table[0][1]=2;   
  table[1][0]=2; table[1][1]=1;
  // 如果k 就是1，那么直接返回
  if(k == 1) return table
  // 其余情况进行迭代运算
  for(let time = 1; time < k; time++) {
    //迭代处理，依次处理2^2, …, 2^k个选手比赛日程
    temp=n; n=n*2;   
    //填左下角元素
    for (i=temp+1; i<=n; i++ )
          for (j=1; j<=temp; j++)
                table[i][j]=table[i-temp][j]+temp;
    //左下角元素和左上角元素的对应关系
    //填右上角元素
    for (i=1; i<=temp; i++) 
          for (j=temp+1; j<=n; j++)
                table[i][j]=table[i+temp][(j+temp)% n];
    //填右下角元素
    for (i=temp+1; i<=n; i++)
          for (j=temp+1; j<=n; j++)
                table[i][j]=table[i-temp][j-temp];
  }
  // 返回整个时间表
  return table
}

---