Следующий круг

Cтраница 3

Сравнение 11: 10, таким образом, - это сравнение, использующее победителя первого круга, и оно является первым из сравнений второго круга. Позиция 11 практически пропустила первый круг. Это автоматически поднимет пропущенную вершину на следующий уровень дерева, где она используется в первом сравнении следующего круга. В этот момент список будет иметь вид такой, как на рис. 5.9, а дерево будет расти так, как там указано. [31]

Дерево и память после первого круга. [32]

Новый круг начинается, как только при сравнении используется элемент из предшествующей позиции. Поскольку в узле 4 находится ключ 3, который попал туда в результате сравнения 9: 8, сравнение 5: 4 на втором круге использует узел, расположенный в дереве выше. В результате сравнения 5: 4 в позицию 2 попадает ключ. Победитель сравнения 5: 4 на самом деле переходит в следующий круг, и, таким образом, формируется новый уровень дерева. Сравнение 3: 2 является финалом, в котором победитель - наименьший ключ в списке - помещается в корневой узел. Список на рис. 5.5 соответствует содержимому рабочей области после первого просмотра. Запись, представляющая корневой узел, помещается в область вывода, а в позицию, которую занимал победитель в начале просмотра, помещается ключ ( 2), наибольший среди всех ключей, какие могут встретиться в сортируемых данных. Остальные вершины остаются без изменения, даже несмотря на то, что некоторые ключи встречаются в разных местах. [33]

Это утверждение не столь очевидно, как может показаться на первый взгляд. Почему число кругов в турнире не увеличивается от того, что из любого круга в следующий могут перейти без игры сразу несколько команд. Как мы только что убедились, иногда в последних кругах нет ни одной команды, которая переходила, бы в следующий круг без игры, а по мере приближения к финалу число участников турнира быстро убывает. [34]

Перейти без игры в следующий круг могла лишь 1 команда и то при условии, что число команд-участниц данного круга нечетно. Тому, кто не знаком с решением задачи 87 ( которое, как мы знаем, остается в силе и в том случае, когда проводятся все встречи и при нехватке стадионов), на первый взгляд может показаться странным, что число проведенных игр не зависит от того, в каких условиях, обычных ( когда проводятся все календарные игры) или необычных ( когда часть матчей срывается из-за отсутствия стадионов и обе команды, которые должны были встретиться между собой, без игры переходят в следующий круг), проводится турнир на приз ПЛЮСа, хотя трудно сказать, что эти способы проведения турнира ничем не отличаются. [35]

Теперь надо найти соответствующий операнд для сравнения. Если элемент, определяемый этим пакетом, меньше, чем элемент на регистрах, то адрес в списке заменяется в пакете, и ранее проигравший становится победителем. Однако в ячейке 0 находится ключ 10, так что ключ 22 опять проигрывает. Выбор его NLPA для сравнения с ключом 10 продвигает ключ 10 в следующий круг. [36]

Следующий шаг состоит в том, чтобы с одной и той же базой данных - провести турниры по швейцарской системе и с немедленным выбыванием. Для разбиения - соиер ков а лары в каждом из этих турниров берутся результаты кругавого турнира. Заметьте, что в обоих турнирах два соперника могут встретиться лишь однажды. Швейцарская классификация - это упорядочение после заключительного круга ( всего п кругов), причем все оставшиеся неясности разрешаются в соответствии с начальным упорядочением. В классификации по выбыванию победитель финальной встречи идет первым, побежденный - вторым, и, вообще, проигравшие в i - м круге располагаются перед ранее выбывшими и после всех победивших в i - м и следующих кругах. Внутри группы побежденных в i - м круге соперники располагаются в соответствии с итоговыми местами победивших их команд. [37]

Страницы: 1 2 3