У нас есть 25 скриптов, которые выполняют одну и ту же задачу, и нам нужно выбрать три самых быстрых из них. Но нельзя пользоваться ни секундомером, ни какими-то ещё инструментами подсчёта времени. Можно только одновременно прогнать скрипты на пяти разных машинах — по одному на каждой.
Какое минимальное количество таких запусков нужно произвести, чтобы определить три самых быстрых скрипта?
Начнём с того, что разделим наши скрипты на пять групп по пять скриптов в каждой. Пусть наши группы называются А, Б, В, Г и Д. Скрипты тоже назовём условно: А1, А2, А3, А4 и А5 в первой группе, Б1, Б2, Б3, Б4 и Б5 — во второй и так далее.
Запустим по очереди каждую группу скриптов на наших пяти компьютерах. Запишем, в каком порядке скрипты в каждой группе завершили работу. Представим, что у нас получились такие результаты — от самого медленного до самого быстрого скрипта:
- Группа А: А3, А1, А2, А4, А5.
- Группа Б: Б4, Б3, Б5, Б1, Б2.
- Группа В: В2, В5, В4, В3, В1.
- Группа Г: Г5, Г2, Г1, Г3, Г4.
- Группа Д: Д1, Д4, Д5, Д2, Д3.
Теперь у нас есть пять скриптов-лидеров. Запустим их — это будет уже шестой раз, когда мы производим запуск. Скрипт, который завершит работу раньше остальных, — это самый быстрый скрипт из 25, что у нас есть. Он быстрее в своей группе и быстрее лидеров других групп. Представим, что первым был скрипт с названием Д3, вторым — А5, третьим — Б2, четвёртым — В1, а пятым — Г4.
Теперь сформируем наши группы скриптов заново. Раз среди скриптов-лидеров первым завершил работу Д3, переименуем его в А1, следующий за ним по скорости в изначальной группе Д — в А2 и так далее. Сделаем то же самое с остальными скриптами и их изначальными группами от самого медленного до самого быстрого:
- Новая группа А: А5, А4, А3, А2, А1.
- Новая группа Б: Б5, Б4, Б3, Б2, Б1.
- Новая группа В: В5, В4, В3, В2, В1.
- Новая группа Г: Г5, Г4, Г3, Г2, Г1.
- Новая группа Д: Д5, Д4, Д3, Д2, Д1.
Мы знаем, какой из 25 скриптов самый быстрый, — это А1 (бывший Д3). Теперь нам нужно найти второй и третий по скорости работы. Сделать это нужно так, чтобы у нас получилось как можно меньше запусков. Для этого проанализируем наши результаты.
Поскольку лидер-скрипт из нашей новой группы Д завершил работу позже остальных лидеров из других групп, можно сделать вывод, что вся группа Д — самые медленные скрипты из 25. Это значит, что мы можем не рассматривать скрипты из этой группы:
По такому же принципу мы можем сделать вывод, что все скрипты группы Г тоже медленнее, чем скрипты в группах А, Б и В. Поэтому мы можем исключить вероятность, что в группе Г могут быть второй и третий самые быстрые скрипты из 25:
Все скрипты в группе В, за исключением В1, тоже будут медленнее, чем скрипты в группах А и Б. Их тоже исключаем из возможных кандидатов:
Теперь проанализируем скрипты из группы Б. Мы явно можем не рассматривать скрипты Б5, Б4 и Б3 — они медленнее, чем Б2 и Б1:
Осталось проанализировать группу А. Это самая быстрая группа скриптов, но мы точно можем исключить из дальнейшего сравнения скрипты А5 и А4:
Таким образом, у нас осталось шесть скриптов, из которых нам нужно определить второй и третий по скорости работы. Но мы можем исключить из этой шестёрки скрипт А1 — мы уже точно знаем, что он самый быстрый. Это значит, что у нас осталось пять скриптов, среди которых будут такие, которые завершили бы работу вслед за А1:
Если мы запустим скрипты А2, А3, Б1, Б2 и Г1, мы найдём второй и третий самые быстрые скрипты из 25. И это будет седьмой запуск. Получается, что минимальное количество запусков, которое нужно, чтобы найти три самых быстрых скрипта, — семь.
