Два мрамора и 100-этажное здание
Один из тех классических вопросов по программированию...
Вам дают два шарика и говорят, что они сломаются при падении с определенной высоты (и, по-видимому, не будут повреждены при падении с высоты ниже этой высоты). Затем вас переводят в 100-этажное здание (предположительно, выше определенной высоты) и просят найти самый высокий этаж, с которого вы можете уронить мрамор, не разбив его настолько эффективно, насколько это возможно.
Дополнительная информация
- Вы должны найти правильный этаж (не возможный диапазон)
- Мрамор гарантированно сломается на одном этаже
- Предположим, что для смены этажей вам понадобится ноль времени - учитывается только количество мраморных капель
- Предположим, правильный этаж случайным образом распределен в здании
9 ответов
Интересно то, как вы можете сделать это с наименьшим количеством капель. Переход на 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 Требуется ли максимальное количество капель
Эта проблема описана в проблеме 6.5 из книги " Взлом собеседования по кодированию (5-е)", решения которой кратко изложены следующим образом:
Наблюдение:
Независимо от того, как мы отбрасываем Marble1, Marble2 должен выполнять линейный поиск. Например, если Marble1 сломается между 10 и 15 этажами, мы должны проверить каждый этаж между Marble2
Подход:
Первая попытка: предположим, что мы бросили мрамор с 10-го этажа, затем с 20-го, …
- В первых Мраморных перерывах на первой капле (Этаж 10) у нас получается не более 10 капель.
- Если первый Мрамор разбивается на последней капле (Этаж 100), то у нас получается не более 19 капель (этажи с 1 по 100, затем с 91 по 99).
- Это довольно хорошо, но все, о чем мы думаем, это абсолютно худший случай. Мы должны сделать некоторую "балансировку нагрузки", чтобы сделать эти два случая более равномерными.
Цель: Создать систему для сбрасывания Marble1 так, чтобы максимально необходимое количество капель было постоянным, независимо от того, разбит ли Marble1 при первой капле или последней капле.
- Система с идеально сбалансированной нагрузкой будет такой, в которой Drops of Marble1 + Drops of Marble2 всегда одинаковы, независимо от того, где сломался Marble1.
- Чтобы это было так, поскольку каждая капля Marble1 делает еще один шаг, Marble2 допускается на один шаг меньше.
- Поэтому мы должны уменьшить количество шагов, которые потенциально могут потребоваться для Marble2, на одну каплю каждый раз. Например, если Marble1 упал на 20-м этаже, а затем на 30-м этаже, Marble2 потенциально должен сделать 9 шагов. Когда мы снова отбрасываем Marble1, мы должны уменьшить потенциальные шаги Marble2 только до 8. Например, мы должны сбросить Marble1 на этаже 39.
- Поэтому мы знаем, что Marble1 должен начинаться с этажа 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: головоломка с яйцами и полами.
Я думаю, что реальный вопрос в том, насколько точен вы хотите получить ответ. Потому что ваша эффективность будет зависеть от этого.
Я согласен с Джастином, если вы хотите 100% точности по мрамору, то после того, как разбит первый мрамор, вам придется подниматься на 1 этаж от последнего известного "хорошего" этажа, пока вы не узнаете, какой этаж победитель." Возможно, даже добавьте статистику и начните с 25-го этажа вместо 50-го, чтобы в худшем случае было 24 вместо 49.
Если ваш ответ может быть плюс или минус один или два этажа, то могут быть некоторые оптимизации.
Во-вторых, идет ли вверх / вниз по лестнице на вашу эффективность? В этом случае всегда бросайте оба шарика и подбирайте оба шарика в каждой поездке вверх / вниз.
Лично я не очень большой поклонник таких загадочных вопросов, я предпочитаю практические упражнения по программированию в интервью.
Тем не менее, сначала это будет зависеть от того, смогу ли я сказать, сломаны они или нет с пола, на который я их бросаю. Я предполагаю, что могу.
Я бы поднялся на второй этаж и уронил первый мрамор. Если бы это сломалось, я попробовал бы первый этаж. Если бы это сломалось, я бы знал, что это не пол.
Если бы первый не сломался, я бы пошел на 4-й этаж и уехал оттуда. Если бы это сломалось, я бы спустился вниз и взял другой мрамор, затем упал бы на 3-й этаж, разбив или нет, я бы знал, какой предел.
Если бы ни один не сломался, я пошел бы получить оба, и сделать тот же процесс, на этот раз начиная с 6-го этажа.
Таким образом, я могу пропустить каждый второй этаж, пока не получу мрамор, который сломается.
Это было бы оптимизировано, если мрамор сломается рано... Я полагаю, что есть оптимальное количество этажей, которое я мог бы пропустить, чтобы получить максимум для каждого пропуска... но тогда, если один сломается, мне придется проверять каждый этаж индивидуально со второго этажа над последним известным этажом... что, конечно, было бы больно, если бы я пропустил слишком много этажей (извините, сейчас я не найду оптимального решения).
В идеале я хотел бы получить целую сумку шариков, тогда я мог бы использовать алгоритм бинарного поиска и делить число этажей пополам с каждой каплей... но тогда это был не вопрос, не так ли?
Каждый из них ломается при падении с одной высоты или они разные?
Если они одинаковые, я иду на 50-й этаж и бросаю первый мрамор. Если это не сломается, я иду на 75-й этаж и делаю то же самое, пока оно не ломается, я продолжаю расти на 50% от того, что осталось. Когда он сломается, я возвращаюсь на один уровень выше, чем был раньше (поэтому, если он сломался на 75-м этаже, я возвращаюсь на 51-й этаж), опускаю второй мрамор и поднимаюсь на пол за раз, пока он не сломается, в этот момент я знаю самый высокий этаж, с которого я могу упасть без мраморной поломки.
Наверное, не самый лучший ответ, мне любопытно посмотреть, как ответят другие.
Бросьте первый мрамор на 10, 20, 30 и т. Д., Пока он не сломается, затем прыгайте обратно на последний известный хороший пол и начинайте сбрасывать с него мрамор по одному этажу за раз. В худшем случае 99 - это Волшебный пол, и вы всегда можете найти его в 19 каплях или меньше.
If you want a general solution which will give you the result for N floors (in your case N=100) then you can just solve quadratic equation $x^2+x-2\cdot(N-1)=0$ and the result is a ceiling of a positive root.
Which is:
$$f(N)=ceiling\bigg(\frac{-1+\sqrt{1+4\cdot2\cdot(N-1))}}{2}\bigg)$$
Бросьте первый мрамор с 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
Это можно сделать лучше всего с 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 этажей.
Первое, что я хотел бы сделать, это использовать мертвый простой алгоритм, который начинается на первом этаже, и сбрасывает мрамор по одному этажу за раз, пока он не достигнет 100 или пока мраморы не сломаются.
Тогда я спрашиваю, зачем мне тратить время на его оптимизацию, пока кто-то не покажет, что это будет проблемой. Слишком часто люди зацикливаются на поиске идеального сложного алгоритма, когда гораздо более простой решит проблему. Другими словами, не оптимизируйте вещи, пока они не понадобятся.
Это может быть вопрос с подвохом, чтобы увидеть, если вы один из тех людей, которые могут сделать гору из холма крота.