本文主要是介绍F：循环赛日程，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
F : 循环赛日程表
看了一下网上其他人写的，感觉思路都不太清晰，不是很好懂。
我按照我的理解写了一个自认为很好懂的思路。
Description
n = 2_k_个选手（编号1 ∼ n）进行循环赛，日程表要求：
- 每个选手必须与其他𝑛−1个选手各赛一次；
- 每个选手一天只能赛一次；
- 循环赛一共进行𝑛−1天.
设计一个𝑛行𝑛−1列的表，第𝑖行第𝑗列填入第𝑖个选手第𝑗天的对手.
Input
多组测试数据，每组给出选手个数_n_. 其中_n_ ≤ 32
Output
给出_n_行_n_ − 1列的日程表.
Sample Input
8
Sample Output
2 3 4 5 6 7 8
1 4 3 6 5 8 7
4 1 2 7 8 5 6
3 2 1 8 7 6 5
6 7 8 1 2 3 4
5 8 7 2 1 4 3
8 5 6 3 4 1 2
7 6 5 4 3 2 1
思路
这道题只要思路会了，循环条件可以理清，就可以很轻松写出来。
分治
这个分治是怎么分治的？
举个例子，n=8，也就是有8个选手
将分治的三个过程列出来：
- 分解：4个“𝑛/2个选手比赛日程”的子问题
(1)1 ~ 4号的第1 ~ 4天，对手1 ~ 4号；
(2)1 ~ 4号的第5 ~ 8天，对手5 ~ 8号；
(3)5 ~ 8号的第1 ~ 4天，对手5 ~ 8号；
(4)5 ~ 8号的第5 ~ 8天，对手1 ~ 4号。
而1~4号选手又可以分解为：1 ~ 2和3 ~ 4号 - 解决：递归到只有一位选手的时候，之间返回即可
- 合并：要搞清楚这四个子问题之间的关系，关系如下：
（3）可以由（1）分别加“n/2”得到
（4）等于（1）
（2）等于（3）
这么说可能会有点绕，可以看图；
右下蓝色部分 = 左上蓝色部分
左下白色部分 = 左上蓝色部分 + 4（8/2）
右上白色部分 = 左下白色部分
可以看到颜色相同的部分是一样的，不同颜色的表格之间则差了n/2。
那么根据这思路我们可以列出以下代码：
int addval = n/2;//前n/2的选手与后n/2的选手的号数之差
for (int i = 0; i < n/2; ++i) { for (int j = 0; j < n/2; ++j) { //左上角与右下角一致 table[i+addval][j+addval] = table[i][j]; //左下角是左上角+addval table[i+addval][j]=table[i][j]+addval; //右上角等于左下角 table[i][j+addval]=table[i+addval][j]; }
}
这里比较难理解的是，为什么i、j的范围是到n/2？
可以自己举个例子测试一下：
当选手只有两位（n=2）时
i、j只会到0，也就是只需要一个模板去填值。
当选手有四位时
模板便是红色圈住部分。
以此类推，可以发现模板的大小总是n/2。
完整代码如下：
#include "iostream"
#define max 32
using namespace std;
int table[max][max]; void schedule(int n)
{ if (n==1) //当只有1个选手的子问题，直接返回 return; schedule(n/2); //递归int addval = n/2;//前n/2的选手与后n/2的选手的号数之差 for (int i = 0; i < n/2; ++i) { for (int j = 0; j < n/2; ++j) { //左上角与右下角一致 table[i+addval][j+addval] = table[i][j]; //左下角是左上角+addval table[i+addval][j]=table[i][j]+addval; //右上角等于左下角 table[i][j+addval]=table[i+addval][j]; } } }
void print(int num)
{ for (int i = 0; i < num; ++i) { for (int j = 1; j < num; ++j) { cout<<table[i][j]<<" "; }cout<<endl; }
}
int main()
{ int n; cin>>n; table[0][0]=1; //最开始的模板schedule(n); print(n); return 0;
}
这篇关于F：循环赛日程的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
