分治法:
列出人数为的情况:
K = 1
其中第一列是选手的序号,之后n列代表着选手的对手
K = 2
可以看出,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
排列完毕。