byes %4的双重淘汰竞赛算法

Question

我正在尝试编写一个双淘汰锦标赛，其中括号是基于mod 4。第一轮应该处理所有的告别，这样在第二轮之后就不会有更多的告别。我很难弄清楚决定我所需的告别量背后的实际数学。如果有人能帮助我解决这背后的数学问题，我将非常感激。

对于任何mod 4 (0, 1,2,3 )，我需要处理1，2，3的byes，有4种可能的答案。

我的意思是13个玩家的例子(13%4=1)，所以第一轮应该是1vs2vs3 3vs4 4vs5 5vs6

第二轮是7vs赢家8vs赢家9vs赢家赢家vs赢家然后你就有了失败者组

基本上，如果你熟悉网站挑战，我想生成我的括号类似于他们，但我不能计算出他们背后的数学决定是。

如果有人做过类似的事情，我将非常感谢他的帮助。

Answer 1

其中N是参赛者的数量，轮数为：

nRounds = Math.Ceiling( Math.Log( N, 2 ) );

第一轮的插槽数量为：

firstRoundSlots = Math.Pow( 2, nRounds );

排名靠前的参赛者获得通过，因此在您的示例中，在16轮比赛中有13名参赛者，因此排名前3的参赛者获得了通过。换句话说，byes的数量是firstRoundSlots - N。

比赛的顺序有点复杂。基本上，总决赛是最好的竞争者与第二好的竞争者的较量。在半决赛中，最好的选手与第三名选手对阵，第二名选手与第四名选手对阵。以此类推。因此，从决赛开始向后工作来生成订单是最容易的。

然而，如果你想知道一种反向生成回合顺序的算法(即从第一轮开始，一直到决赛)，我在这里写了一篇关于这方面的博客文章：

http://blogs.popart.com/2012/02/things-only-mathematicians-can-get-excited-about/

Answer 2

我会告诉你我是如何解决这个问题的。

你想要在第二轮的玩家数量是2的幂。

第二轮的玩家数量是：(matches in round 1)/2 + byes)

设P是玩家的数量。

2^n = (P-byes)/2 + byes
2^(n+1) = P-byes + 2*byes
2^(u) = P + byes

所以找一个最小的u s.t。2^u >= P，然后是2^u-P byes。

示例案例:7 -> 2^u=8 -> (8-7) -> 1 bye

1再见，3与-> 4玩家在第2轮比赛

这不是模块4，将9个玩家与13: 9 -> 2^u=16 -> (16-9) -> 7 byes 13 -> 2^u=16 -> (16-13) -> 3 byes进行比较

一个更有趣的问题是，如何安排最少的告别次数，允许在第一轮之外的其他回合中进行一些。

Answer 3

我能想到的最简单的算法：

_

1. _

_

1. _

_

1. _那么这个人就会被淘汰出局，直到锦标赛中只剩下一名选手为止