Если вы пытались решить задачу о турнире по настольному теннису «в лоб», составляя различные варианты таблиц розыгрыша турнира с 37 участниками, то, должно быть, заметили, что независимо от способа составления таблицы число участников, переходящих в следующий круг без игры, всегда равно 4. В общем случае число участников, для которых в очередном круге не хватает партнера, есть функция от числа n всех участников турнира. Кате установить, сколько участников вынуждены будут перейти в следующий круг без игры?
При заданном n число участников, остающихся без партнера, можно определить следующим образом. Вычтем из n наименьшую степень числа 2, которая больше или равна n. Полученную разность запишем в двоичной системе. Число единиц в двоичной записи и будет равно числу участников турнира, вынужденных перейти в следующий круг без игры из-за нехватки партнера. В нашей задаче мы вычтем 37 из 64 (то есть из 26) и получим разность, равную 27. Десятичное число 27 в двоичной системе имеет вид 11011. Поскольку в его записи 4 единицы, то за весь турнир без игры в следующий круг перейдут 4 игрока. Обоснование этого алгоритма для определения числа участников, которым не хватает партнера, мы предоставляем читателю в качестве интересного упражнения.
Описанный в задаче тип турнира иногда называют «игрой на вылет». Он аналогичен алгоритму, который вычислители, работающие на современных ЭВМ, используют для нахождения наибольшего элемента в множестве из n элементов: наибольший элемент находят, сравнивая попарно элементы множества и отбрасывая при очередном сравнении тот из двух элементов, который не больше другого. Как мы уже знаем, чтобы найти наибольший элемент, достаточно произвести ровно n − 1 попарных сравнений. При автоматической сортировке сравнивать можно не только по 2, но и по 3, 4 и т. д. элемента.
Автоматическая сортировка играет важную роль в вычислительной математике и в информатике. Ей посвящено немало книг. Каждый из нас без труда назовет длинный перечень примеров применения автоматической сортировки. Подсчитано, что примерно четверть машинного времени в научных и в технических расчетах затрачивается на решение задач, связанных с сортировкой данных.