Сложность: Средняя, ​​Вопрос: Google, Amazon

Постановка задачи

Есть 25 лошадей, среди которых нам нужно найти 3 самых быстрых лошадей. В каждой гонке одновременно могут участвовать только 5 лошадей, потому что всего 5 дорожек. Какое минимальное количество скачек требуется, чтобы найти 3 самых быстрых лошадей без использования секундомера?

Идея решения и шаги

Мы можем решить эту проблему, используя идею исключения. Есть 25 лошадей, и мы можем включить в скачку только 5 лошадей. Чтобы узнать относительную скорость каждой лошади, нам нужно включить всех лошадей хотя бы в одну гонку. Думать! Вот пошаговая стратегия определения трех самых быстрых лошадей.

Шаг 1. Мы разделили 25 лошадей на группы по 5 лошадей.

Шаг 2. Первые 5 заездов

Теперь мы проводим скачки в каждой группе, чтобы узнать относительную скорость лошадей в каждой группе. Для этого потребуется 5 гонок. Давайте рассмотрим лидеров A1, B1, C1, D1 и E1 в этих 5 гонках.

Шаг 3: 6-я гонка

Теперь мы можем легко определить более быструю лошадь, которая будет самой быстрой среди победителей каждой группы. Итак, мы создаем группу из 5 этих лошадей (A1, B1, C1, D1, E1 ) и проводим среди них скачки. Победителем этой гонки становится самая быстрая лошадь в целом. Итак, после 6 скачек мы знаем самую быструю лошадь. Предположим, результат равен A1 › B1 › C1 › D1 › E1. Теперь мы идем вперед, чтобы найти 2-е и 3-е места быстрее всего.

Шаг 4. Седьмая гонка

Теперь о второй позиции: B1 и A2 будут потенциальными кандидатами. Аналогично, для 3-й позиции: A2, B1, C1, B2 и A3 являются потенциальными кандидатами. В целом, на 2-ю и 3-ю позиции потенциальными кандидатами являются A2, B1, C1, B2 и A3.

  • B1 и A2 могут быть вторыми или третьими
  • C1 или B2 ИЛИ A3 может быть третьим

В группе из этих 5 лошадей победителем будет вторая самая быстрая лошадь, а лошадь, пришедшая второй в гонке, будет третьей самой быстрой!

Таким образом, используя эту процедуру, нам нужно 7 гонок, чтобы определить 3 самых быстрых лошадей. Но главный вопрос: почему минимум 7 гонок? Давай подумаем!

  • Чтобы найти самую быструю, нам нужно запустить все 25 лошадей хотя бы один раз, а поскольку вы можете участвовать в гонках только на 5 лошадях за раз, вам нужно как минимум 25/5 = 5 скачек.
  • Затем нам нужно сравнить победителей этих гонок, а значит необходима 6-я гонка.
  • Чтобы найти второго и третьего самых быстрых, нам нужен хотя бы еще один заезд, чтобы сравнить относительную скорость лошадей.

Еще один важный вопрос: можем ли мы обобщить эту стратегию на n² лошадей и n дорожек, где мы хотим найти k самых быстрых лошадей (k ‹ n)? Давай подумаем!

Наслаждайтесь обучением, наслаждайтесь мышлением!