🐎 Самая быстрая лошадь на скачках
Говорят, эту задачку дают на собеседованиях Microsoft.
У вас есть 25 лошадей и 5 беговых дорожек. При этом заранее неизвестно, какая лошадь быстрее другой, а секундомера нет — после каждого забега можно определить только порядок участников на финише.
Задача: найти тройку самых быстрых лошадей за минимально возможное количество забегов.
Попробуйте сначала решить самостоятельно и посчитать, сколько гонок вам понадобится 👀
Ответ — ниже 👇
Первые 5 забегов нужны, чтобы разделить всех 25 лошадей на пять групп и определить порядок внутри каждой.
Затем проводим 6-й забег между победителями пяти групп. Допустим, результат такой:
A1 > B1 > C1 > D1 > E1
После него круг претендентов сильно сужается. На место в тройке всё ещё могут рассчитывать только:
A1, A2, A3, B1, B2 и C1.
Почему? Например, C2 уже точно медленнее C1, B1 и A1 — значит, в топ-3 она не попадёт. По той же логике исключаем остальных.
A1 уже гарантированно самая быстрая лошадь.
Остаётся провести 7-й забег между:
A2, A3, B1, B2 и C1.
Две самые быстрые лошади в этом забеге вместе с A1 и составят итоговую тройку победителей.
🏁 Ответ: минимально нужно 7 забегов.
А у вас получилось решить без подсказки?
Говорят, эту задачку дают на собеседованиях Microsoft.
У вас есть 25 лошадей и 5 беговых дорожек. При этом заранее неизвестно, какая лошадь быстрее другой, а секундомера нет — после каждого забега можно определить только порядок участников на финише.
Задача: найти тройку самых быстрых лошадей за минимально возможное количество забегов.
Попробуйте сначала решить самостоятельно и посчитать, сколько гонок вам понадобится 👀
Ответ — ниже 👇
Первые 5 забегов нужны, чтобы разделить всех 25 лошадей на пять групп и определить порядок внутри каждой.
Затем проводим 6-й забег между победителями пяти групп. Допустим, результат такой:
A1 > B1 > C1 > D1 > E1
После него круг претендентов сильно сужается. На место в тройке всё ещё могут рассчитывать только:
A1, A2, A3, B1, B2 и C1.
Почему? Например, C2 уже точно медленнее C1, B1 и A1 — значит, в топ-3 она не попадёт. По той же логике исключаем остальных.
A1 уже гарантированно самая быстрая лошадь.
Остаётся провести 7-й забег между:
A2, A3, B1, B2 и C1.
Две самые быстрые лошади в этом забеге вместе с A1 и составят итоговую тройку победителей.
🏁 Ответ: минимально нужно 7 забегов.
А у вас получилось решить без подсказки?