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

Question

Я пытаюсь реализовать скобку в моей программе (используя C # /. NET MVC), и я застрял, пытаясь выяснить какой-то алгоритм.

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

Я пытаюсь выяснить, есть ли алгоритмический способ для

1. в зависимости от количества записей, найдите количество игр за раунд

2. в зависимости от количества записей, для конкретной игры #, что такое соответствующая игра # вследующий раунд?

Например, в этом случае для 8 записей, например:

1. для 1 раунда, есть 4 игры.Раунд 2, 2 игры.Раунд 3, игра 1
2. , игра 2 в раунде 1 соответствует игре 5 в раунде 2.

Я также думал о сохранении этой информации в таблице, но она кажется излишней, поскольку онаникогда не меняется, но здесь все равно:

Любая помощь будет принята с благодарностью!

Приветствия,

Дин

Answer 1

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

// 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;
}

Answer 2

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

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

// 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);
}

Answer 3

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

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

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

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

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

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

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

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

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

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

Создание турнира

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

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

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

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

Answer 4

Так что в основном это конкурс на выбывание.

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

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

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

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

А + 1 С + 1 ...

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

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

Answer 5

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

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

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

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