Когда нужно бросать яйца с крыши: ежедневная проблема с программированием

Ежедневная задача кодирования 24

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

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

Тогда хватит разговоров; посмотрим проблему!

Проблема

Эту проблему задал Goldman Sachs на собеседовании. Давайте посмотрим на проблему.

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

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

Например, если N = 1 и k = 5 , нам нужно будет попытаться сбросить яйцо на каждом этаже, начиная с первого, пока мы не достигнем пятого этажа, поэтому наше решение будет 5 .

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

От этого этажа до каждого этажа ниже яйца не разобьются, если их выбросить из окна. Нас просят найти эффективный метод поиска targetFloor .

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

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

Настройка среды

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

Мы еще раз напишем эту задачу на Go: достаточно просто, чтобы ее можно было прочитать, но достаточно сложно, чтобы понять внутреннюю механику.

Сначала мы создаем массив, который будет служить нашим зданием: мы можем придать ему нужный размер, чем больше размер, тем выше будет здание. После этого мы создаем экземпляр targetFlor , используя модуль math/rand встроенный в Go.

По сути, мы создаем новое случайное целое число от 0 до высоты здания (… длины массива :D), используя в качестве источника текущее время.

Решение грубой силы

Конечно, самым простым решением было бы выбросить каждое яйцо на каждом этаже, чтобы увидеть, на каком этаже яйца начнут разбиваться. Поскольку у нас есть переменная, содержащая эту информацию, можно просто выполнить цикл for, чтобы решить проблему:

Хотя это самое простое решение, оно, к сожалению, крайне неэффективно. Представьте себе, если правый этаж является верхним: чтобы решить задачу, нужно разбить 100 000 яиц: это будет огромный омлет, но это пустая трата!

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

Эффективное решение

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

Вот пример: предположим, что у нас есть здание в 10 этажей, а targetFloor — это 7-й этаж (мы этого, конечно, не знаем). Мы могли бы сделать следующие предположения:

По сути, мы предполагаем, что targetFloor — это средний этаж здания. Мы бросаем яйцо оттуда, и возможных исходов два:

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

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

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

Если вам знаком этот подход, вы совершенно правы: это просто бинарный поиск , примененный к проблеме «реального мира». Бинарный поиск — это простой и аккуратный алгоритм «разделяй и властвуй» , означающий, что на каждом этапе размер проблемы уменьшается вдвое, пока мы не найдем решение.

Это означает, что этот алгоритм по сравнению с предыдущим работает намного быстрее. Давайте посмотрим код!

Давайте посмотрим глубже. Функция двоичного поиска принимает 4 аргумента:

• overArray — массив целых чисел, который представляет собой здание, по которому мы проходим цикл;

• bottom — нижний индекс здания;

• top — индекс верхнего этажа здания;

• breakFloor — переменная, содержащая targetFloor , чтобы проверить, сможем ли мы найти его в здании.

После этого мы проходим по зданию, пока bottom находится ниже top : при двоичном поиске, когда два позиционных аргумента переплетаются и меняются местами, это означает, что искомый элемент не найден.

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

Мы вычисляем элемент middlePoint как нижний предел между bottom и top и проверяем, есть ли middlePoint == breakFloor . Если это так, мы возвращаем в качестве результата middlePoint .

Если это не так, мы соответствующим образом корректируем bottom или top : если middlePoint больше, чем breakFloor , это означает, что мы находимся слишком высоко на здании, поэтому мы снижаем наш прогноз, устанавливая top возможный этаж на middlePoint — 1 .

Если middlePoint меньше, чем breakFloor , мы корректируем bottom , установив значение middlePoint+1 .

Теперь, чтобы все проверить, в main функции мы, как и раньше, генерируем среду и создаем новую переменную с именем bsFloor , которая будет хранить наш результат.

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

Временная сложность

Как мы и предполагали ранее, этот алгоритм намного быстрее линейного. Поскольку на каждом этапе мы делим здание пополам, мы можем найти правильный этаж в log₂(n), где n равно len(building) .

Это означает, что временная сложность этого алгоритма равна O(log(n)) . Чтобы дать вам некоторое сравнение между линейным решением и этим последним: если в здании 100 этажей, линейный алгоритм в худшем случае требует 100 итераций, а алгоритм двоичного поиска требует log₂100 = 6,64, то есть 7 итераций.

Кроме того, последний метод становится все более эффективным, чем линейный, поскольку чем больше растет здание, тем эффективнее бинарный поиск. Для здания с 1 000 000 000 этажей линейный требует 1 000 000 000 шагов, а двоичный — log₂1 000 000 000 = 29,9, то есть 30 шагов. Огромное улучшение!

Заключение

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

Наконец, если вы нашли эту статью интересной или полезной и хотели бы внести свой вклад, предложив кофе, не стесняйтесь сделать это на моем сайте. Ко-фи страница!

И, как всегда, спасибо за прочтение!

Никола

Также опубликовано здесь