100 Этажей 2 яйца

Задачки, 30 января 2015 в 16:31

Дано 100-этажное здание. Если яйцо сбросить с высоты N-го этажа (или с большей высоты), оно разобьется. Если его бросить с любого меньшего этажа, оно не разобьется. У вас есть два яйца. Найдите N за минимальное количество бросков.

Обратите внимание, что независимо от того, с какого этажа мы бросаем яйцо №1, бросая яйцо №2, необходимого использовать линейный поиск (от самого низкого до самого высокого этажа) между этажом «повреждения» и следующим наивысшим этажом, при броске с которого яйцо останется целым. Например, если яйцо №1 остается целым при падении с 5-го по 10-й этаж, но разбивается при броске с 15-го этажа, то яйцо №2 придется (в худшем случае) сбрасывать с 11-го,12-го,13-го и 14-го этажей.

Предположим, что мы бросаем яйцо с 10-го этажа, потом с 20-го…

• Если яйцо №1 разбилось на первом броске (этаж 10-й), то нам в худшем случае приходится проделать не более 10 бросков.
• Если яйцо №1 разбивается на последнем броске (100-й этаж), тогда у нас впереди в худшем случае 19 бросков (этажи 10-й, 20-й, …, 90-й, 100-й, затем с 91-го до 99-го).

Это хорошо, но давайте уделим внимание самому плохому случаю. Выполним балансировку нагрузки, чтобы выделить два наиболее вероятных случая.

1. В хорошо сбалансированной системе значение Drops(Egg1) + Drops(Egg2) будет постоянным, независимо от того, на каком этаже разбилось яйцо №1.
2. Допустим, что за каждый бросок яйцо №1 «делает» один шаг (этаж), а яйцо №2 перемещается на один шаг меньше.
3. Нужно каждый раз сокращать на единицу количество бросков, потенциально необходимых яйцу №2. Если яйцо №1 бросается сначала с 20-го, а потом с 30-го этажа, то яйцу №2 понадобится не более 9 бросков. Когда мы бросаем яйцо №1 в очередной раз, то должны снизить количество бросков яйца №2 до 8. Для этого достаточно бросить яйцо №1 с 39 этажа.
4. Мы знаем, что яйцо №1 должно стартовать с этажа X, затем спуститься на X-1 этажей, затем — на X-2 этажей, пока не будет достигнуто число 100.
5. Можно вывести формулу, описыващее наше решение: X + (X – 1) + (X – 2) + … + 1 = 100 -> X = 14.

Таким образом, мы сначала попадаем на 14-й этаж, затем на 27-й, затем 39-й. Так что 14 шагов — худший случай.

Как и в других задачах максимизации/минимазиции, ключом к решению является «балансировка худшего случая».

Головоломки и задачи на сообразительность

воскресенье, 3 апреля 2011 г.

Два яйца и небоскрёб

Ещё одна довольно известная задача, которую включают почти во все сборники задач с собеседований в Гугл.

У вас есть доступ в 100-этажный небоскрёб и 2 идентичных яйца неизвестной птицы. Никаких данных о прочности скорлупы нет: яйцо может разбиться, упав с первого этажа, а может остаться целым, упав с сотого.

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

Решение
Пусть мы знаем, что минимальное число бросков в худшем случае K.

Очевидно, что для того, чтобы сделать не более K бросков, первый бросок должен быть не выше чем с K-го этажа. В самом деле, если мы сбросим первое яйцо с этажа M>K, и оно разобьётся, у нас не будет иного выхода кроме как методично проверять все этажи подряд начиная с первого и заканчивая M-1. В худшем случае мы проверим M-1 этажей, что в сумме с первым броском даст M>K бросков. Очевидно также, бросать в первый раз ниже чем с K-го этажа нет смысла.

Итак, в первый раз мы бросаем с этажа K. Если яйцо разбилось, то за K-1 попыток мы проверим все K-1 нижних этажей. Если же нет, у нас останется K-1 бросок в запасе на верхние этажи.

Рассуждая аналогично, мы должны будем совершить второй бросок с этажа K+(K-1). Если яйцо разобьётся, нам нужно будет проверить этажи с K+1 по 2*K-2, которых всего K-2, что в сумме с двумя первыми бросками даст искомые K бросков.

Понятно, что если первое яйцо не разобьётся, третий бросок мы будем делать с этажа K+(K-1)+(K-2), четвёртый — с K+(K-1)+(K-2)+(K-3) и так далее. Самый последний бросок мы можем сделать с этажа K*(K+1)/2.

Следовательно, для того чтобы небоскрёб из N этажей можно было проверить за K бросков, должно выполняться условие K*(K+1)/2>=N. В случае N=100 получается K>=14.

Таким образом, нам нужно сделать в худшем случае 14 бросков. До тех пор, пока первое яйцо не разбивается, мы бросаем его с этажей 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100. Если оно разбивается, например, на 69-м этаже, мы начинаем бросать второе яйцо со всех этажей начиная с 61-го, т.е. с первого непроверенного.

Когда у тебя в руках молоток, все задачи кажутся гвоздями.

Абрахам Маслоу (Авраам Маслов)

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

Далее, можно не открывать спойлер, если не решали этой задачи. Можно конечно открыть и увидеть весь ужасный путанный опыт решения задачи.

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

Если идти с конца, то мы можем разбить яйцо на 100 этаже, но так и не узнаем с какого же этажа оно разбивается. Зато, зато мы задействовали два яйца.

Немного лучше чем первый вариант, но в самом плохом случае нам понадобится сделать 50 бросков, что бы узнать где бьется яйцо.

Ухожу поспать и в голове рождается план, что с 12 бросками все станет гораздо лучше, т.е. во сне приходит решение. Это Менделееву приходит правильное видение таблицы, а мне лишь 5 * 12 = 100. Потом я конечно понимаю свою ошибку, но уже поздно.

4. Пробы и ошибки. Копаем до истины.

Начинается подбор решений для разных случаев, что бы потом их перенести на наш случай

Если этажа 2, то нужно бросить через один этаж.
Если этажа 4, то нужно бросать на втором этаже.
Если этажей 8, то нужно бросать на третьем этаже. (Потому что если бросить на четвертом, то в худшем случае придется бросать пять раз, а не четыре).

И вот тут начинается интересное, что (а мне пригодится математика? нет, она нужна только умным детям). А вот умные решают так с самого начала.

И вот тут бы пригодилось знание логарифма, как раз здесь мы видим как идет приращение числа. Тогда получается, что бросить яйцо надо с такого этажа, что бы количество бросков внутри этого шага было не больше наихудшего варианта.
В итоге получится, что K*(K+1)/2>=N, где N число этажей, а К — число бросков. Для 100 этажей К = 14, что на 5 единиц лучше, чем для варианта с увеличением на 10, и почти в 10 раз быстрее, чем подниматься с 1-го до 100-го этажа.