Два мрамора и 100-этажное здание

Question

Один из тех классических вопросов по программированию ...

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

Дополнительная информация

• Вы должны найти правильный этаж (невозможный диапазон)
• Мрамор гарантированно разбивается на одном этаже
• Предположим, что для смены этажей требуется ноль времени - учитывается только количество мраморных капель
• Предположим, что в здании случайным образом распределен правильный этаж

Answer 1

Интересно то, как вы можете сделать это с наименьшим количеством капель. Переход на 50-й этаж и опускание первого будет катастрофическим, если разбитый этаж будет 49-м, в результате чего нам придется сделать 50 капель. Мы должны бросить первый шарик на пол n, где n - максимальное количество необходимых капель. Если мрамор разбивается на полу n, нам, возможно, придется сделать n-1 капель после этого. Если мрамор не разбивается, мы поднимаемся на этаж 2n-1, а если он разбивается, нам приходится бросать второй мрамор n-2 раза в худшем случае. Мы продолжаем в том же духе до 100-го этажа и пытаемся разбить его на 3n-2, 4n-3 ....
и n + (n-1) + (n-2) + ... 1 <= 100 <br> n = 14 Требуется ли максимальное количество капель

Answer 2

Эта проблема описана в проблеме 6.5 из книги " Взлом кодового интервью (5-е) ", решения которой кратко изложены следующим образом:

Замечание:

Независимо от того, как мы отбрасываем Marble1, Marble2 должен выполнять линейный поиск. Например, если мрамор1 перерывы между этажами 10 и 15, мы должны проверить каждый этаж между мрамором2

---

Подход:

Первая попытка: Предположим, мы сбрасываем мрамор с 10-го этажа, затем с 20-го,…

• В первых Мраморных перерывах на первой капле (Этаж 10) у нас получается не более 10 капель.
• Если первый Мрамор разбивается на последней капле (Этаж 100), то у нас получается не более 19 капель. (этажи с 1 по 100, затем с 91 по 99).
• Это довольно хорошо, но все, о чем мы думаем, это абсолютно худший случай. Мы должны выполните некоторое «распределение нагрузки», чтобы сделать эти два случая более равномерными.

Цель: Создать систему для сбрасывания Marble1 так, чтобы максимально необходимое количество капель было одинаковым, независимо от того, разбился ли Marble1 при первой или последней капле.

1. Система с идеально сбалансированной нагрузкой будет такой, в которой Drops of Marble1 + Drops of Marble2 всегда одинаков, независимо от того, где Marble1 сломался.
2. Для этого, поскольку каждая капля Marble1 делает еще один шаг, Marble2 разрешен на один шаг меньше.
3. Поэтому мы должны уменьшить количество шагов, которые потенциально могут потребоваться для Marble2, на один бросить каждый раз. Например, если Marble1 упал на 20-м этаже, а затем на 30-м этаже, Marble2 будет потенциально требуется предпринять 9 шагов. Когда мы снова отбрасываем Marble1, мы должны уменьшить потенциальные шаги Marble2 до 8. Например, мы должны отбросить Marble1 на 39 этаже.
4. Мы знаем, поэтому, что Marble1 должен начинаться с этажа X, затем подниматься на этажи X-1, затем X-2,…, пока не достигнет 100.
5. Решить для X + (X-1) + (X-2) +… + 1 = 100. X (X + 1) / 2 = 100 -> X = 14

Мы идем на 14-й этаж, затем на 27, затем на 39 ... Это занимает максимум 14 шагов.

---

Код и расширение:

• Для реализации кода вы можете проверить здесь .

• Для расширения до N мрамора, M этажа, посмотрите Глава 12: Загадка о яйцах и полу .

Answer 3

Бросьте первый мрамор на этаж 10, 20, 30 и т. Д., Пока он не сломается, затем прыгайте назад на последний известный хороший этаж и начинайте сбрасывать с него мрамор по одному этажу за раз. В худшем случае 99 - это Волшебный пол, и вы всегда можете найти его в 19 каплях или меньше.

Answer 4

Каждый из них ломается при падении с одной высоты или они разные?

Если они одинаковые, я иду на 50-й этаж и бросаю первый мрамор. Если он не сломается, я иду на 75-й этаж и делаю то же самое, пока он не сломается, я продолжаю расти на 50% от того, что осталось. Когда он сломается, я возвращаюсь на один уровень выше, чем был раньше (поэтому, если он сломался на 75-м этаже, я возвращаюсь на 51-й этаж), опускаю второй мрамор и поднимаюсь на пол за раз, пока он не сломается в этот момент я знаю самый высокий этаж, с которого я могу упасть без мраморной поломки.

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

Answer 5

Я думаю, реальный вопрос в том, насколько точен вы хотите получить ответ. Потому что ваша эффективность будет зависеть от этого.

Я согласен с Джастином, если вы хотите 100% точности на мраморах, то после того, как разбит первый мрамор, вам придется подниматься на 1 этаж от последнего известного «хорошего» этажа, пока вы не узнаете какой этаж является «победителем». Возможно, даже добавьте статистику и начните с 25-го этажа вместо 50-го, чтобы наихудший сценарий был 24 вместо 49.

Если ваш ответ может быть плюс или минус один или два этажа, то возможны некоторые оптимизации.

Во-вторых, идет ли вверх / вниз по лестнице на вашу эффективность? В этом случае всегда бросайте оба шарика и подбирайте оба шарика в каждой поездке вверх / вниз.

Answer 6

Я лично не очень большой поклонник таких вопросов-головоломок, я предпочитаю практические упражнения по программированию в интервью.

Тем не менее, во-первых, это будет зависеть от того, смогу ли я сказать, сломаны они или нет с пола, на который я их бросаю. Я предполагаю, что могу.

Я бы поднялся на второй этаж и уронил первый мрамор. Если бы это сломалось, я попробовал бы первый этаж. Если бы это сломалось, я бы знал, что это не пол.

Если бы первый не сломался, я бы поднялся на 4-й этаж и уехал оттуда. Если бы это сломалось, я бы спустился вниз и взял другой мрамор, затем упал бы на 3-й этаж, разбив или нет, я бы знал, какой предел.

Если бы ни один не сломался, я бы взял и то и другое, и сделал бы тот же процесс, на этот раз начиная с 6-го этажа.

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

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

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

Answer 7

Это можно сделать лучше всего с 7 шариками.

Итак, после того, как проголосовали, скажем, мрамор разбит как минимум на 49-м этаже.

1. 50-й этаж -> перерывы (ответ от 1 до 50 включительно)
2. 25 этаж -> не ломается (от 26 до 50)
3. 37 этаж -> не ломается (от 38 до 50)
4. 43-й этаж -> не ломается (от 44 до 50)
5. 46 этаж -> не ломается (от 47 до 50)
6. 48 этаж -> не ломается (49 или 50)
7. 49-й этаж -> перерывы (49-й, этот шаг действительно необходим, потому что, возможно, это был минимальный этаж для разбивания мрамора на 50-м)

Это можно представить как бинарный поиск в отсортированном наборе для некоторого k, где мы наполовину уменьшаем пространство решения при каждой попытке. Для 100 этажей нам нужно log2 100 = 6,644 (7 попыток). С 7 мраморами мы можем быть уверены, что это минимальный этаж, на котором мрамор может разбиться до 128 этажей.

Answer 8

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

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

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

Answer 9

Бросьте первый мрамор с 3-го этажа. Если он сломается, вы знаете, что это 1 или 2 этаж, поэтому бросьте другой мрамор со 2 этажа. Если он не сломается, вы обнаружили, что 2 этаж самый высокий. Если он сломается, вы обнаружите, что этаж 1 самый высокий. 2 капли.

Если падение с 3-го этажа не сломает мрамор, упасть с 6-го этажа. Если он сломается, вы знаете, что 4-й или 5-й этаж - самый высокий. Бросьте второй мрамор с 5 этажа. Если он не сломается, вы обнаружили, что 5 - самый высокий. Если это так, этаж 4 является самым высоким. 4 капли.

Продолжить.

3 этажа - максимум 2 капли

6 этажей - максимум 4 капли

9 этажей - максимум 6 капель

12 этажей - максимум 8 капель

и т.д.

3x этажа - максимум 2x капли

Так что для 99-этажного здания у вас будет максимум 66 капель. И это максимум. Скорее всего, у вас будет меньше капель. Да, и 66 - максимум для 100-этажного здания. Вам понадобится только 66 капель, если пол разрыва был 98 или 97 этаж. Если пол разрыва был 100, вы бы использовали 34 капли.

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

Часть проблемы заключается в том, как вы определяете эффективность. Является ли более «эффективным» всегда иметь решение в количестве менее x капель, или же более эффективно иметь хороший шанс иметь решение в виде капель y, где y