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

Ответ 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
n = 14 Требуется максимальное снижение

Ответ 2

Эта проблема рассматривается в задаче 6.5 из книги "" Cracking the Coding Interview (5th)" с решениями, представленными ниже:

Замечание:

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

Подход:

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

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

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

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

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

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

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

• Для расширения до N мрамора, M этажей, проверьте Глава 12: Пазл из яиц и полов.

Ответ 3

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

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

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

Ответ 4

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

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

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

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

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

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

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

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

Ответ 5

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

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

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

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

Ответ 6

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

Ответ 7

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

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

Продолжить.

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

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

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

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

и др.

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

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

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

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

Ответ 8

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

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

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

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

Ответ 9

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

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

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