Вопрос :

Есть здание 100 этажей

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

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

Выведите минимальное количество капель, необходимое для вычисления N.

Решение :

Первая мысль, которая приходит нам в голову, это использовать бинарный поиск, сначала бросаем Яйцо №1 с 50-го этажа, если оно не разбивается, то пробуем середину второй половины, если разбивается, то пробуем каждый этаж первой половины. Но это даст в худшем случае количество дропов, равное 50 (если он тормозит на 50-м этаже, тогда мы должны последовательно пробовать от 1 до 49 этажей). в этом случае наихудшее время будет (100/x)+(x-1). в худшем случае, когда яйцо №1 разобьется на 100-м этаже, тогда мы должны попробовать яйцо №2 с (100-х)-го по 99-й этажи. В уравнении (100/x) + (x-1) с увеличением x 100/x уменьшается, а (x-1) увеличивается, поэтому мы можем минимизировать его, когда 100/x = (x-1), это дает x ~ 10, что дает число в худшем случае 19 капель.

Но увеличивать пол каждый раз на x — не очень хорошая идея, так как с каждым новым увеличением выпадения яйца № 1 мы должны уменьшать выпадение яйца № 2, чтобы минимизировать число в худшем случае. так что, если мы сначала бросим яйцо №1 с x-го этажа, то на следующем ходу мы должны попробовать x + (x-1)-й этаж (чтобы оставить число в худшем случае таким же).
Таким образом, мы можем сказать X + (x -1) + (x-2)…1 = 100
X(X+1)/2 = 100 => X=14.

Таким образом, мы должны сбросить яйцо № 1 с 14-го, затем 27-го, затем 39-го и так далее.

Спасибо за чтение

Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и попадать в замечательные компании.

Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.