Алгоритмы для турнирных скобок (NCAA и т.д.)

Ответ 1

Цитата @Yuck, которая отлично ответила на первый вопрос.

Код С# для первой части вашего вопроса:

// N = Initial Team Count
// R = Zero-Based Round #
// Games = (N / (2 ^ R)) / 2
public double GamesPerRound(int totalTeams, int currentRound) {
    var result = (totalTeams / Math.Pow(2, currentRound)) / 2;

    // Happens if you exceed the maximum possible rounds given number of teams
    if (result < 1.0F) throw new InvalidOperationException();

    return result;
}

Переходя к второму вопросу:

//G = current game.
//T = total teams
//Next round game = (T / 2) + RoundedUp(G / 2)
//i. e.: G = 2, T = 8
       //Next round game = (8 / 2) + RoundedUp(2 / 2) = 5
public int NextGame(int totalTeams, int currentGame) {
    return (totalTeams / 2) + (int)Math.Ceiling((double)currentGame / 2);
}

Ответ 2

Код С# для первой части вашего вопроса:

// N = Initial Team Count
// R = Zero-Based Round #
// Games = (N / (2 ^ R)) / 2
public double GamesPerRound(int totalTeams, int currentRound) {
    var result = (totalTeams / Math.Pow(2, currentRound)) / 2;

    // Happens if you exceed the maximum possible rounds given number of teams
    if (result < 1.0F) throw new InvalidOperationException();

    return result;
}

Следующий шаг в решении части (2) - знать минимальный номер игры для данного раунда. Интуитивный способ сделать это будет через цикл for, но, вероятно, лучший метод:

var totalTeams = 8;
var selectedRound = 2;
var firstGame = 1;
// If we start with round 1, this doesn't execute and firstGame remains at 1
for (var currentRound = 1; currentRound < selectedRound; currentRound++) {
    var gamesPerRound = GamesPerRound(totalTeams, currentRound);
    firstGame += gamesPerRound;
}

Ответ 3

Я действительно работал над этим довольно недавно и наткнулся (то есть, я работал, но, вероятно, был обнаружен раньше) аккуратное рекурсивное решение.

Вы начинаете со своего списка игроков в списке, отсортированном по порядку посева. Это будет важно позже.

Общий алгоритм состоит из разбиения списка игроков на два, а затем создания двух суб-турниров. Победители двух суб-турниров в конечном итоге выйдут в финальный турнир.

Обязательные объекты

• Игрок
  • Имя
  • Seed
• Match
  • Домашний проигрыватель
  • Away Player
  • Следующее совпадение (указатель на совпадение победителя)

Разделение списков

В большинстве турниров игрок, занявший первое место, помещал игрока, занявшего первое место, в первом раунде. Для этого я использовал следующий алгоритм, но вы могли бы просто поместить первых игроков n / 2 в один список, а остальные в другом списке - создать турнир, где семена 1 и 2 будут разыгрываться в первом раунде (и семя 3 играет 4, 5 пьес 6 и т.д.).

Замечу здесь, что аккуратная вещь о том, что верхнее семя имеет начальное семя, заключается в том, что с помощью этого алгоритма, если у вас нет мощности двух игроков, верхнее семя (ов) получит свидание в ранние раунды.

• Возьмите первого игрока и поместите его в "левый" список
• Возьмите следующих двух игроков (или последнего игрока) и поместите их в "правый" список
• Возьмите следующих двух игроков и поместите их в "левый" список
• Повторяйте с шага 2, пока больше игроков не будет.

Конечно, если в списке есть только два игрока, вы просто создаете совпадение между ними и возвращаете.

Построение турнира

Итак, вы начинаете с списка, скажем, из 64 игроков. Вы разделили его на два списка из 32 игроков и рекурсивно создали два суб-турнира. Методы, которые вы называете рекурсивно, должны возвращать матчи, которые представляют финальный финальный турнир суб-турнира (полуфинал вашего общего турнира). Затем вы можете создать матч, который станет финальным финалом вашего общего турнира, и установите nextMatch полуфинальных матчей на этот грандиозный финал.

Что следует учитывать

• Вам нужно будет вырваться из рекурсии, если в список вошли только два игрока.
• Если ваш раскол дает вам список одного, не следует с ним переписываться. Просто создайте суб-турнир с другим списком (у него должны быть только два игрока, поэтому он будет возвращен с совпадением сразу), установите домашнюю команду как одиночный игрок и nextMatch суб-турнира.
• Если вы хотите отслеживать раунды, вам нужно передать целочисленное значение глубины рекурсии - увеличьте его при создании суб-турнира.

Надеюсь, что это поможет, дайте мне знать, если вам нужно разъяснение:)

Ответ 4

Итак, в основном это победа.

Так что просто список.

Алгоритм всегда ставит первую и вторую команды вместе, если количество команд равно. Затем вы увеличиваете счетчик на два и повторяете.

Если количество команд нечетное, делайте довольно много, кроме того, что вы случайно выбираете победителя "первого круга" и помещаете его против нечетной команды.

После первого раунда вы повторяете алгоритм таким же образом.

А + 1 С + 1 ...

Например, у меня есть скобка типа это с 8 элементами (A, B, C, D, E, F, G, H)

Вы должны иметь возможность выяснить, как это разбирать. Это кажется домашним вопросом.

Ответ 5

Рассмотрим перенумерацию игр (вы всегда можете перенумеровать их назад)

если финал равен 1 полуфабрикаты 2,3 проблема тогда имеет хорошо изданные решения: ahnentafel (немецкий для таблицы предков) долгое время использовался генеалогами - http://en.wikipedia.org/wiki/Ahnentafel

одной интересной частью этого является двоичная нотация игры #, которая дает много информации о структуре турнира и где в дереве соответствует матч.

Также обратите внимание, что, поскольку каждое совпадение выбивает 1 участника, для n участников будет n-1 совпадений