Задача «Неразбивающееся яйцо»

Вы работаете в здании, где 100 этажей. Вам дают 2 одинаковых яйца. Вы должны определить самый высокий этаж, с которого можно сбросить яйцо, и оно не разобьется. В ходе эксперимента разрешается разбить оба яйца. Сколько бросков вам потребуется, чтобы получить ответ?

Здание и яйца являются воображаемыми.

Правильный ответ: 14 бросков — максимум.

Самый простой вариант

Начните с нижнего этажа и продолжайте бросать яйцо до тех пор, пока оно не разобьется. Это можно назвать «медленным алгоритмом». В худшем случае вам понадобится 99 попыток.

Оба яйца останутся целы.

Более оптимальный вариант 1

Сбросьте первое яйцо с любого произвольного этажа N. В зависимости от того, разобьется оно или нет, у вас есть две возможности. Т.к. нам нужно посчитать броски при самом неблагоприятном варианте, рассмотрим его.

Если яйцо разбилось, спуститесь на этаж 1 и воспользуйтесь «медленным алгоритмом». Опробуйте каждый этаж, поднимаясь вверх по зданию до тех пор, пока яйцо не разобьется. В худшем случае вам потребуется 50 попыток — если вы сбросите первое яйцо с 50-го этажа, оно разобьется, а максимальный этаж для «безопасного сброса яиц» окажется 49-м.

Тут не нужна интуиция программиста, чтобы понять, что это подход не самый продуктивный.

Более оптимальный вариант 2

Гораздо лучше сбросить 1-е яйцо с более низкого этажа. Если мы начнем, скажем, с 10-го, и яйцо разобьется, нам потребуется 10 бросков максимум. Это важный вывод: если яйцо разбивается при первом сбрасывании с этажа N, потребуется не более N сбрасываний, чтобы определить нужный этаж.

Насколько эффективна эта процедура? Самый худший сценарий в этом случае — попробовать этажи 10, 20, 30 и так вплоть до 100-го, при сбрасывании с которого яйцо разбивается. После этого вы спускаетесь на 91-й этаж, а затем двигаетесь вверх. В конце концов вам, возможно, потребуется 19 экспериментов, чтобы определить правильный этаж — 99-й.

Описанный вариант является неплохим, но он и не лучший.

Ответ в Google

При поиске хорошего решения очень важная роль отводится первому яйцу. Даже при единственном падении это яйцо может исключить из тестирования множество этажей. Вопрос — сколько?

В идеальном алгоритме Google для решения этой задачи есть ограничение — максимальное число бросков. Назовем это число D. Для примера допустим, что это число равно 10. Тогда, если вы сбросите яйцо с 10-го этажа и оно не разобьется, максимальный этаж, на который вы сможете подняться — 19-й, потому что у вас осталось только 9 попыток.

Этажи, которые вы протестировали (если считать, что после серии экспериментов яйцо осталось целым), образуют простую серию:

10

10 + 9 = 19

10 + 9 + 8 = 27

10 + 9 + 8 + 7 = 34

и т.д. до последней, десятой попытки:

10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55. 

Иными словами, этот способ подходит только для 55-этажного здания. Но вспомним, что мы выбрали число 10 в качестве D просто для примера, из воздуха. Вернемся к числовому обозначению. Самый высокий этаж при оптимальном методе, который можно достичь, равен:

D + (D - 1) + (D - 2) + (D - 3) + … + 3 + 2 + 1

И эта сумма должна быть равна или превышать 100.

Далее идут простые алгебраические вычисления. Сумма, приведенная выше, равняется D плюс каждое целое число, меньше, чем D. В математике такое число называется треугольным. Представьте полочку с бильярдными шарами. На ней лежат 5 + 4 + 3 + 2 + 1 шаров. Может быть, вы помните, что их сумму можно вычислить, умножив 5 на (5 + 1) и разделив произведение на 2. При таком простом подсчете вы получите (5 * 6)/2 = 15, и именно это число шаров находится на полке.

В нашем случае сумма D и всех остальных целых чисел, меньших D, равна:

D * (D + 1) / 2 ≥ 100 

Умножим обе части на 2, раскроем скобки и получим:

D^2 + D ≥ 200

Сфокусируемся на D^2 и пока проигнорируем гораздо меньшее значение D. Из этого уравнения следует, что D^2 по крайней мере близко по своей величине к 200. Квадратный корень из 200 чуть больше 14. Проверим, подходит ли это число для D:

14^2 + 14 = 196 + 14 = 210 ≥ 200 

Чтобы убедиться, попробуем и 13:

13^2 + 13 = 169 + 13 = 182. 

Не подходит, потому что меньше 200. А вот 14 подходит в полной мере.

Итак, вот алгоритм: сначала бросьте яйцо с 14-го этажа. Если оно разобьется, спуститесь на 1-й этаж и двигайтесь «медленным алгоритмом». При таком подходе потребуется не более 14 бросков.

Если же при первом броске яйцо не разбилось, поднимитесь на этаж 27 (13 = 14 -1, добавленные к первым 14 этажам) и проведите эксперимент снова. Если на этот раз яйцо разобьется, вам придется спуститься на 15-й этаж и, поднимаясь вверх, тестировать остальные этажи. В этом варианте вы опять же получите ответ максимум за 14 попыток.

Приведем одну рекомендацию, которая часто бывает полезной при ответах на такие алгоритмические вопросы. Начните с самой простой версии. Когда в вопросе упоминается большое число, вроде 100 этажей, подумайте, как бы вы подошли к решению этой задачи в ее простейшем варианте, а затем усложняйте: одноэтажное здание, двухэтажное и т.д. После этого ответ обычно становится очевидным. Затем используйте ваш подход для более крупных значений. В ходе этого увеличения масштаба вы выявите интересующую вас закономерность.