Этюды для программистов | страница 25

*Баяковский Ю. М., Мишакова С. Т. Автоматизированная система подготовки публикаций и документов (АСПИД), ИПМ АН СССР им. М. В. Келдыша. Препринт № 19, 1977.

Система АСПИД написана на Фортране и на машине БЭСМ-6 тратит на подготовку страницы вывода также около 2 с.

Едва ли не каждый из нас в свое время был болельщиком местной, чуть ли не самой сильной команды. Состоявшийся в конце сезона турнир должен был выявить чемпиона города, округа, штата, страны, мира или Вселенной. Но какое невезение — местные герои проиграли будущему победителю уже в первом круге турнира с немедленным выбыванием. Игра оказалась малоинтересной — никто даже не успел размяться. И ведь как обидно: самые настоящие слабаки в итоге занимают место, которое по праву должно принадлежать нашим парням, а болельщиков вместо волнующей борьбы в финале ждет убогое зрелище.

А виноват во всем турнир с немедленным выбыванием. Пусть имеется 2^>n команд, n > 0. Тогда в первом круге команда 1 играет с командой 2, команда 3 с командой 4, …, команда 2^>n − 1 с командой 2^>n. Проигравшие вылетают, а победители выходят в следующий круг.

Рисунок 5.1. Простой турнир с немедленным выбыванием. Окончательное упорядочение, как это определено в тексте, имеет вид 1, 3, 5, 2, 8, 6, 4, 7.

На рис. 5.1 изображен турнир восьми команд. Если предположить, что более сильная команда всегда выигрывает (т. е. что не бывает срывов), лучшая команда, очевидно, завоюет первое место. Однако второй участник финальной игры может занимать в общей табели о рангах лишь место 2^>n−1 + 1 при условии, что все более сильные команды оказались в одной группе с победителем. Победитель по мере своего продвижения выведет из розыгрыша хорошие команды, и слабой команде достанутся совсем никудышные соперники. Избежать подобной ситуации можно несколькими способами. Во-первых, команды (в дальнейшем будем называть их соперниками) можно рассеять, чтобы сильные соперники (оценка дается по итогам предыдущих выступлений) разместились по всей турнирной сетке. Например, самый сильный соперник попадает в позицию 1, второй по силе — в 2^>n−1 + 1, третий — в 2^>n−1 + 2^>n−2 + 1, четвертый — в 2^>n−2 + 1 и т. д. Если предварительная оценка была достаточно точной, сильные соперники не выбьют друг друга в первых кругах. Во-вторых, можно устроить турнир с отложенным выбыванием, когда выбывают после двух поражений. Но на самом деле идеальным решением (хорошо бы еще и практичным!) был бы