algorithm - 淘汰赛所需回合数

Question

我只是想知道是否有人有一个公式来评估单败淘汰赛的回合数，基于:- 参与的团队数量(可以>2)- 下一轮晋级队伍的数量。

这对于 1v1 或 1v1v1v1 很容易，每轮每场比赛有 2 支球队晋级，但我被 1v1v1 困住了，只有 1 或 2 支晋级球队...

谢谢!

根据要求，示例:

让我们从 32 名玩家开始，他们在“全民免费”模式下同时玩 4 人的 COD(每个玩家单独对抗其他玩家)。

1st round : 32 players distributed in 8 matches of 4 players 

这里我们想知道如果我们选择在每场比赛中保留 1 名或 2 名甚至 3 名最佳球员，需要多少轮才能进入 4 名球员的决赛。

第一种情况:如果我们保留每场比赛中最好的 2 场比赛:

2nd round : 16 players distributed in 4 matches of 4 players 

第二种情况:如果我们只保留第一种情况

2nd round : 8 players distributed in 2 matches of 4 players 

(在第二种情况下，我们可以预见到一个问题，因为在下一轮我们将只剩下 2 名玩家，这不足以填满一局游戏)

我的想法是找到一个数学公式，用以下变量给出必要的回合数:

 * NumberOfPlayers                 : the quantity of initial participants
 * NumberOfPlayersInAGame          : the quantity of participants in a game
 * NumberOfPlayersQualifiedInAGame : the quantity of participants qualified for the next round in after a game 

享受:D

Answer 1

对于 k 锦标赛中的 1 获胜者(例如，k = 3 表示 1v1v1)和 N 玩家，其中 N 元素 k^x 和 x 是一个正整数，它需要 g 游戏(java 代码):

public int countGames(int players, int k) {
    if (players <= 1) {
       return 0;
    } else {
       players = players / k;
       // the number of remaining players per round is the same as the number of games
       return players + countGames(players, k);
    }
}

或者数学上:

g = sum(i from 1 to logk(N), k^(i-1))                           ( logK(N) = ln(N) / ln(k)  )