Задача про 25 скриптов и скорость
easy

Задача про 25 скриптов и скорость

Определяем лидеров на глаз

У нас есть 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 скриптов и скорость

Мы знаем, какой из 25 скриптов самый быстрый, — это А1 (бывший Д3). Теперь нам нужно найти второй и третий по скорости работы. Сделать это нужно так, чтобы у нас получилось как можно меньше запусков. Для этого проанализируем наши результаты.

Поскольку лидер-скрипт из нашей новой группы Д завершил работу позже остальных лидеров из других групп, можно сделать вывод, что вся группа Д — самые медленные скрипты из 25. Это значит, что мы можем не рассматривать скрипты из этой группы:

Задача про 25 скриптов и скорость

По такому же принципу мы можем сделать вывод, что все скрипты группы Г тоже медленнее, чем скрипты в группах А, Б и В. Поэтому мы можем исключить вероятность, что в группе Г могут быть второй и третий самые быстрые скрипты из 25:

Задача про 25 скриптов и скорость

Все скрипты в группе В, за исключением В1, тоже будут медленнее, чем скрипты в группах А и Б. Их тоже исключаем из возможных кандидатов:

Задача про 25 скриптов и скорость

Теперь проанализируем скрипты из группы Б. Мы явно можем не рассматривать скрипты Б5, Б4 и Б3 — они медленнее, чем Б2 и Б1:

Задача про 25 скриптов и скорость

Осталось проанализировать группу А. Это самая быстрая группа скриптов, но мы точно можем исключить из дальнейшего сравнения скрипты А5 и А4:

Задача про 25 скриптов и скорость

Таким образом, у нас осталось шесть скриптов, из которых нам нужно определить второй и третий по скорости работы. Но мы можем исключить из этой шестёрки скрипт А1 — мы уже точно знаем, что он самый быстрый. Это значит, что у нас осталось пять скриптов, среди которых будут такие, которые завершили бы работу вслед за А1:

Задача про 25 скриптов и скорость

Если мы запустим скрипты А2, А3, Б1, Б2 и Г1, мы найдём второй и третий самые быстрые скрипты из 25. И это будет седьмой запуск. Получается, что минимальное количество запусков, которое нужно, чтобы найти три самых быстрых скрипта, — семь.

Редактор:

Инна Долога

Обложка:

Алексей Сухов

Корректор:

Ирина Михеева

Вёрстка:

Маша Климентьева

Соцсети:

Юлия Зубарева

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
easy