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

https://stackoverflow.com/questions/6547

08-06-2019
|

Вопрос

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

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

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

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

Решение

Самое интересное здесь то, как вы можете сделать это за наименьшее количество капель.Подняться на 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 должен выполнять линейный поиск.Например, если Мрамор1 разрывается между этажами 10 и 15, мы должны проверить каждый промежуточный этаж с помощью Мрамора2

Подход:

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

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

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

Идеально сбалансированная по нагрузке система - это система, в которой Drops of Marble1 + Drops of Marble2 всегда одинакова, независимо от того, где сломался Marble1.
Чтобы это было так, поскольку каждая капля мрамора1 занимает на один шаг больше, допускается использование мрамора2 на один шаг меньше.
Поэтому мы должны сократить количество шагов, потенциально требуемых Marble2, на одну каплю каждый раз.Например, если шарик 1 упал на этаж 20, а затем на этаж 30, шарику 2 потенциально потребуется сделать 9 шагов.Когда мы снова отбросим Marble1, мы должны уменьшить потенциальные шаги Marble2 всего до 8.например, мы должны сбросить Мрамор1 с 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:Головоломка из яиц и полов .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Продолжайте.

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

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

9 этажей - максимум 6 перепадов

12 этажей - максимум 8 спусков

и т.д.

3x этажей - максимум 2 перепада высот

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow