网球循环赛思路 – 分治法求解(无代码)
- 2021 年 3 月 13 日
- 笔记
分治法：
列出人数为的情况：
K = 1
|
1 |
2 |
|
2 |
1 |
其中第一列是选手的序号，之后n列代表着选手的对手
K = 2
|
1 |
2 |
3 |
4 |
|
2 |
1 |
4 |
3 |
|
3 |
4 |
1 |
2 |
|
4 |
3 |
2 |
1 |
可以看出，k=4的情况就是将格子分成四个部分，然后将人数为 的结果放在左上角和右下角的格子，然后再将人数结果加上再放在左下角和右上角的格子中去。
因此可以得出以下分治算法：
void fun()
{
if(n==1)
{
tables[0][0] = 1;
return;
}
fun(n/2);
get_table(n);
}
- 递归时 (fun(n/2)函数)
当n/2为偶数的时候，继续递归
当n/2为奇数的时候要进行修正。
- 返回求值时：(get_table()函数)
如果n为奇数，则计算n+1的情况，将最后一个选手当做虚拟选手。
虚拟选手的处理方法：将与虚拟选手比赛的选手视为轮空
如果n为偶数：
当n/2为偶数时，直接复制即可。
当n/2为奇数时，要进行修正。
修正方法为：
将n/2情况中的虚拟选手序号（虚拟选手序号大于当前的所有选手）全部变成当前选手序号加上n/2，然后将对应的虚拟选手赛程变成当前选手。不是虚拟选手的处理和情况相同（然后可以得到左上角和左下角的所有情况）。之后将除第一列以外剩余n/2列复制到右半边，之后再讲对应选手按序号排序即可。
如：n=6时，n/2=3：
1 2 3 4
2 1 4 3
3 4 1 2
在上述情况中4是虚拟选手，因为其序号大于3
将虚拟选手的序号变成当前选手序号加上n/2
1 2 3 4
2 1 5 3
3 6 1 2
然后将虚拟选手的对手匹配
1 2 3 4
2 1 5 3
3 6 1 2
4 1
5 2
6 3
再正常填入：
1 2 3 4
2 1 5 3
3 6 1 2
4 5 6 1
5 4 2 6
6 3 4 5
最后将除第一列以外的所有元素左下角复制到右上角，左上角复制到右下角
2 3 4 5 6 1
1 5 3 4 2 6
6 1 2 3 4 5
5 6 1 2 3 4
4 2 6 1 5 3
3 4 5 6 1 2
最后再按序号顺序从上到下排列整齐：
1 5 3 4 2 6
2 3 4 5 6 1
3 4 5 6 1 2
4 2 6 1 5 3
5 6 1 2 3 4
6 1 2 3 4 5
排列完毕。
