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

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

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

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

  • Вы должны найти правильный этаж (не возможный диапазон)
  • Мрамор гарантированно сломается на одном этаже
  • Предположим, что для смены пола вам понадобится ноль времени - учитывается только количество мраморных капель
  • Предположим, правильный этаж случайным образом распределен в здании
9.08.2008 02:23:27
Вероятно, лучше не предполагать, что правильный этаж распределен случайным образом, а просто придумать решение, чтобы минимизировать наихудший случай.
Dave L. 16.09.2008 16:43:56
Это имеет довольно большое "ага!" фактор для тех, кто не изучал математику. Вопросы с "ага!" фактор исключительно плох для интервью.
Brad Wilson 25.09.2008 15:34:17
@Brad Wilson: это полностью зависит от собеседования ... это отличный вопрос, чтобы проверить логическое мышление и навыки математического решения.
Karoly Horvath 21.10.2012 17:10:22
В заголовке вопроса четко не указано: нужно ли нам найти максимальный этаж, с которого мы можем уронить мрамор без его разбивания, или, как следует из ответа, минимальное количество попыток достичь этого этажа ...? !
Sayan 22.10.2012 11:59:59
Вам нужен алгоритм для эффективного поиска пола (который должен привести вас как к максимальному количеству падений, требуемому для вашего подхода, так и к ряду шагов для того, как это сделать).
Matt Sheppard 23.10.2012 21:41:16
10 ОТВЕТОВ
РЕШЕНИЕ

Интересно, что вы можете сделать это с наименьшим количеством капель. Переход на 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 Требуется ли максимальное количество капель?

51
10.08.2008 03:28:23
не могли бы вы объяснить причину уравнения n+(n-1)+(n-2)+...1 <=100?
Geek 22.04.2015 07:07:47
@ Говорите, что n - худший из возможных результатов. Таким образом, вы пытаетесь сделать этот худший случай худшим для каждого из нескольких сегментов. Чтобы поддерживать этот максимальный наихудший случай для каждого тестируемого сегмента, вы должны использовать на 1 меньшее падение для каждого тестируемого сегмента. Проверьте первый сегмент при этом значении n, если он сломает вас, затем протестируйте от 1 до n-1. Таким образом, ваш окончательный максимум падает 1 + (n-1) = n. Если он не сломался при n, но при 2n, то вы уже выполнили 1 бросок при n, так что, если придерживаться наихудшего случая n падений, у вас останется только n-1. На 3n, вы уже сделали 2 капли, поэтому, чтобы придерживаться наихудшего случая, осталось n-2 капли.
Davos 8.08.2017 15:34:45
Логично, что мрамор падает на землю тем сильнее, чем выше вы поднимаетесь, поэтому начинаете низко и поднимаетесь. Таким образом, сегменты начинаются с низкого уровня, а также повышаются. Чем больше сегментов вы тестируете, тем меньше остается дропов, поэтому более высокие сегменты вынуждены становиться все меньше и меньше. Нижний сегмент самый большой, равный n. Каждый шаг на ступеньку меньше, потому что вы продвигаетесь вверх.
Davos 8.08.2017 15:38:22
Тогда цель состоит в том, чтобы минимизировать n. Вы можете запустить через это вручную, прокладывая результаты каждого из них: n=100, n+(n-1)=100, n+(n-1)+(n-2)=100, n+(n-1)+(n-2)+(n-3)=100и т.д. и т.п. Перестановка каждый из этих уравнений к n=100, n=101/2, n=103/3, n=106/4. Продолжайте, значение n будет уменьшаться, пока не достигнет минимума, а затем станет выше. Это минимальное решение является оптимальным. Решение 13.64, но нет 13.64 этажа, поэтому 14. Количество требуемых сегментов совпадает с количеством терминов, чтобы найти минимум, например n+(n-1), 2 термина ...
Davos 8.08.2017 15:46:20
Я не могу редактировать этот первый комментарий. Эта часть неверна: «если она не сломалась при n, но при 2n». Извините, 2n не прав, это должно быть "но в n + (n-1)"
Davos 8.08.2017 15:49:31

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

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

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

2
9.08.2008 02:29:48

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

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

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

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

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

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

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

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

1
9.08.2008 02:37:41

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

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

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

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

1
9.08.2008 03:49:02

Бросьте первый мрамор с 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 <x, с тем предостережением, что у вас может быть больше x капель? ?

0
9.08.2008 09:44:03

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

2
9.08.2008 14:46:21

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

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

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

-3
25.09.2008 15:42:09
Даже если вы хотите использовать очень простой алгоритм, используйте хотя бы всю информацию, приведенную в вопросе. У вас есть 2 шарика, но вы все еще используете только 1. Не позволяйте другому мрамору сидеть и плакать «Я пришел в этот мир, чтобы изменить ситуацию, а вы тратите мое существование :(»
Vikram Singh 20.12.2012 05:55:15

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

Наблюдение:

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


Подход:

Первая попытка: предположим, что мы бросили мрамор с 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 шагов.


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

13
23.05.2017 12:25:57
Не могли бы вы прокомментировать обоснование уравнения в шаге 5 выше?
Geek 22.04.2015 07:30:53
@Geek Вам просто нужно покрыть все 100 диапазонов декрементными диапазонами. Мы хотели сделать его сбалансированным, чтобы прыжки были на этажах: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95. Каждый раз увеличивается на один этаж меньше. Таким образом, даже если мы отбрасываем первый 10 раз, нам нужно всего 4 капли больше. 10 + 4 = 14, как если бы он сломался на первом этаже.
borjab 27.08.2015 11:13:28
«Чтобы это было так, поскольку каждая капля Marble1 делает еще один шаг, Marble2 допускается на один шаг меньше». , Я не понимаю эту часть. Не могли бы вы объяснить?
Dinaiz 8.01.2017 15:14:21
@Dinaiz Totaldrops = Marble1Drops + Marble2Drops. Если вы хотите, чтобы значение TotalDrops оставалось неизменным (наихудший случай), то при увеличении Marble1Drops Marble2Drops должен уменьшаться. Например, предположим, что TotalDrops = 10. Если Marble1Drops = 1, то Marble2Drops = 9. Если Marble1Drops = 2, то Marble2Drops = 8 и так далее.
Davos 8.08.2017 15:56:41
@Geek Вы можете начать с предположения о худшем x=100, т.е. вы собираетесь сделать 100 капель. Это не может быть хуже, чем 100, потому что есть только 100 этажей для тестирования. Следующим шагом будет попытка разделить пространство пополам. т.е. бросьте один примерно на полпути. Так что вроде как 2x=100, но не совсем. Это действительно x+(x-1)=100, второй сегмент - х-1, потому что этажи - это два сегмента, которые будут тестироваться снизу вверх. Если мрамор не сломан для первого сегмента, вы использовали 1 каплю, так что имейте еще один для верхнего сегмента. Чем больше сегментов, тем больше использованных капель. Они становятся меньше, когда вы поднимаетесь.
Davos 8.08.2017 16:14:43

Это можно сделать лучше всего с 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 этажей.

-1
20.07.2014 14:34:34
Это было бы совсем другой проблемой.
borjab 27.08.2015 11:15:34
Проблема с вашим ответом состоит в том, что это НЕ гарантирует, что если яйцо сломается, скажем, с 43-го этажа, то вы не будете знать, был ли пороговый этаж 38-м, 39-м ... 42-м. Также, посмотрите это
ABcDexter 25.06.2016 09:07:51

Если вам нужно общее решение, которое даст вам результат для N этажей (в вашем случае N = 100), то вы можете просто решить квадратное уравнение $ x ^ 2 + x-2 \ cdot (N-1) = 0 $ и Результатом является потолок положительного корня.

Который:

$$ F (N) = потолок \ Bigg (\ гидроразрыва {-1+ \ SQRT {1 + 4 \ cdot2 \ CDOT (N-1))}} {2} \ Bigg) $$

1
27.03.2019 11:15:10