分治法:

列出人数为的情况:

K = 1

其中第一列是选手的序号,之后n列代表着选手的对手

K = 2

可以看出,k=4的情况就是将格子分成四个部分,然后将人数为  的结果放在左上角和右下角的格子,然后再将人数结果加上再放在左下角和右上角的格子中去。

因此可以得出以下分治算法:

void fun()

{

       if(n==1)

       {

              tables[0][0] = 1;

              return;

}

       fun(n/2);

       get_table(n);

}

  1. 递归时 (fun(n/2)函数)

当n/2为偶数的时候,继续递归

当n/2为奇数的时候要进行修正。

  1. 返回求值时:(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

排列完毕。

03-13 12:56