Раунды, необходимые для ликвидации турнира

Question

Мне просто интересно, есть ли у кого-нибудь формула для оценки количества раундов в соревновании в одиночном исключении на основе: - количество задействованных команд (может быть> 2) - количество квалифицированных команд для следующего раунда.

Это очень просто для 1v1 или 1v1v1v1 с 2-мя командами квалифицироваться на матч каждый раундов, но я застрял на 1v1v1 с 1 или 2-х квалифицированных команд ...

Спасибо!

В соответствии с просьбой, примерами:

давайте начнем с 32 игроками, которые играют COD 4, в то время на «бесплатно для все» режима (каждый игрок в одиночку против других).

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

Здесь мы хотим знать, сколько раундов потребуется пойти на финальный матч с 4-х игроков, если мы выбираем держать 1 или 2 или даже 3 BESTS игроков в каждом из матчей.

первый случай: если держать 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 

Enjoy: D

Answer 1

Для 1 победитель в k -tournament (например.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) ) 

Answer 2

В выбывание турнира каждый матч исключает один абитуриент, по определению. Поэтому, если есть N абитуриентов, и турнир завершается, производя M победителей, то по определению турнира одиночного исключения были проведены N-M матчи. Обычно бывает, что M тождественно 1, и, следовательно, должно быть выполнено соответствие N-1.

Аналогичным образом каждый раунд может быть проанализирован, и если матч состоит из двух участников, играющих для определения одного победителя, то раунд с участием 2 * N и оставшимися в живых N должен иметь 2 * N - N = N совпадений. Если в раунд было 2 * N + 1 абитуриентов, с одним участником, имеющим свидание, то есть выжившие N + 1 раунда и снова должны были сыграть 2 * N + 1 - (N + 1) = N матчей ,

Работая в обратном направлении от требуемого одного победителя, отметив ограничение, что для каждого раунда каждый игрок играет только одну игру, тем самым устраняя только один участник, то максимальное число участников, поддерживаемых выбывание турнир K раундов 2^k.