Ежедневная задача кодирования 24  Добро пожаловать обратно с еще одной проблемой, которую нужно решить! Сегодня мы имеем дело с яйцами, падающими с крыш, с этой действительно интересной проблемой, которая предполагает два возможных решения: довольно наивное и более умное. Последнее также даст нам возможность поговорить о довольно известном алгоритме.  Как всегда, сегодняшнюю проблему представляет замечательный информационный бюллетень.  , на который вы можете бесплатно подписаться, чтобы получать ежедневные задания по программированию. Проверьте это и попробуйте решить свои проблемы!   Ежедневная проблема с кодированием  Тогда хватит разговоров; посмотрим проблему!  Проблема  Эту проблему задал Goldman Sachs на собеседовании. Давайте посмотрим на проблему.      одинаковых яиц и доступ к зданию с   этажами. Ваша задача — найти самый нижний этаж, на котором яйцо разобьется, если его уронить с этого этажа. Если яйцо разобьется, его уже нельзя будет уронить. Если яйцо разбивается при падении с   этажа, можно предположить, что оно также разобьется при падении с любого этажа, превышающего   . Вам даны N k xth x   Напишите алгоритм, который находит минимальное количество пробных падений, которое потребуется в худшем случае для идентификации этого этажа.      и   , нам нужно будет попытаться сбросить яйцо на каждом этаже, начиная с первого, пока мы не достигнем пятого этажа, поэтому наше решение будет   . Например, если N = 1 k = 5 5  Итак, нам даны яйца, которые нужно кидать с разных этажей здания. Нам грустно, что с определенного этажа (который мы назовем   ) выброшенные яйца не разбиваются при падении на землю. targetFloor  От этого этажа до каждого этажа ниже яйца не разобьются, если их выбросить из окна. Нас просят найти эффективный метод поиска   . targetFloor  Как и ожидалось, мы увидим два метода решения этой проблемы: очень простой, который приведет к перебору решения, но не будет эффективным. Второй будет гораздо эффективнее и попытается решить задачу, преодолев наименьшее количество шагов.  Это также даст нам возможность поговорить об действительно известном и важном алгоритме; один из тех, которые вам нужно знать, чтобы сделать… в общем, что угодно!  Настройка среды  Для начала нам нужно настроить среду, а именно здание и   . Чтобы создать здание, мы просто создаем массив, содержащий номера этажей, от первого до второго этажа. Затем мы генерируем случайное число, которое будет нашим   . targetFloor targetFloor  Мы еще раз напишем эту задачу на Go: достаточно просто, чтобы ее можно было прочитать, но достаточно сложно, чтобы понять внутреннюю механику.   https://gist.github.com/NicolaM94/85ae34f01e7de8cd00264276b385e137?embedable=true#file-main-go  Сначала мы создаем массив, который будет служить нашим зданием: мы можем придать ему нужный размер, чем больше размер, тем выше будет здание. После этого мы создаем экземпляр   , используя модуль   встроенный в Go. targetFlor math/rand  По сути, мы создаем новое случайное целое число от 0 до высоты здания (… длины массива :D), используя в качестве источника текущее время.  Решение грубой силы  Конечно, самым простым решением было бы выбросить каждое яйцо на каждом этаже, чтобы увидеть, на каком этаже яйца начнут разбиваться. Поскольку у нас есть переменная, содержащая эту информацию, можно просто выполнить цикл for, чтобы решить проблему:   https://gist.github.com/NicolaM94/dd49b3b44a8938c40d0539512fd613cb?embedable=true#file-main-go  Хотя это самое простое решение, оно, к сожалению, крайне неэффективно. Представьте себе, если правый этаж является верхним: чтобы решить задачу, нужно разбить 100 000 яиц: это будет огромный омлет, но это пустая трата!  Вообще говоря, это решение имеет временную сложность O(n), поскольку сложность решения растет линейно со сложностью входной задачи. Однако это не самое эффективное решение, которое мы могли придумать.  Эффективное решение  Тогда давайте подумаем об эффективном решении. Вместо того, чтобы ходить этаж за этажом, разбивая каждое яйцо на каждом этаже, мы могли бы сделать предположение и на основе результата этого предположения скорректировать следующее предположение.  Вот пример: предположим, что у нас есть здание в 10 этажей, а   — это 7-й этаж (мы этого, конечно, не знаем). Мы могли бы сделать следующие предположения:  targetFloor  По сути, мы предполагаем, что   — это средний этаж здания. Мы бросаем яйцо оттуда, и возможных исходов два: targetFloor  яйцо разбивается, а это значит, что мы слишком высоко. Мы можем отказаться от этажа выше этого и продолжить наши предположения.  Яйцо не разбивается, а это значит, что мы находимся слишком низко или на правильном этаже. Мы отбрасываем каждый этаж ниже этого, включая  Учитывая это, мы теперь делаем еще одно обоснованное предположение о среднем этаже или «оставшемся» здании и применяем ту же стратегию, что и выше. Мы можем продолжать использовать этот подход, пока у нас не останется один этаж.  Если вам знаком этот подход, вы совершенно правы: это просто   , примененный к проблеме «реального мира». Бинарный поиск — это простой и аккуратный алгоритм   , означающий, что на каждом этапе размер проблемы уменьшается вдвое, пока мы не найдем решение. бинарный поиск «разделяй и властвуй»  Это означает, что этот алгоритм по сравнению с предыдущим работает намного быстрее. Давайте посмотрим код!   https://gist.github.com/NicolaM94/79d625ecef07cb26a7a8d9bcdb6143fd?embedable=true#file-main-go  Давайте посмотрим глубже. Функция двоичного поиска принимает 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)  Это означает, что временная сложность этого алгоритма равна   . Чтобы дать вам некоторое сравнение между линейным решением и этим последним: если в здании 100 этажей, линейный алгоритм в худшем случае требует 100 итераций, а алгоритм двоичного поиска требует log₂100 = 6,64, то есть 7 итераций. O(log(n))  Кроме того, последний метод становится все более эффективным, чем линейный, поскольку чем больше растет здание, тем эффективнее бинарный поиск. Для здания с 1 000 000 000 этажей линейный требует 1 000 000 000 шагов, а двоичный — log₂1 000 000 000 = 29,9, то есть 30 шагов. Огромное улучшение!   Заключение  Это оно! Надеюсь, статья вам понравилась так же, как и мне было весело, пытаясь решить задачу! Если да, пожалуйста, оставьте пару хлопков, это будет отличной поддержкой! Если вам нравятся статьи такого типа и вы хотите увидеть больше, подписывайтесь на эту страницу, поскольку я публикую контент такого типа каждый раз, когда могу.  Наконец, если вы нашли эту статью интересной или полезной и хотели бы внести свой вклад, предложив кофе, не стесняйтесь сделать это на моем сайте.  страница!   Ко-фи  И, как всегда, спасибо за прочтение!   Никола   Также опубликовано  здесь

Read My Stories

Этот звук создан на языке оригинала истории!

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

About Author

КОММЕНТАРИИ

БИРКИ

ЭТА СТАТЬЯ БЫЛА ПРЕДСТАВЛЕНА В

Related Stories

Valhalla Флоки станет ассоциированным спонсором индийского тура по Шри-Ланке

Цифровые кочевники слушают: что нужно знать о новой визе DTV в Таиланде

Модель Bitcoin UTXO, обеспечивающая работу уникальной экосистемы

Утечка информации о системе Claude Sonnet 3.5: судебно-медицинский анализ

Valhalla Флоки станет ассоциированным спонсором индийского тура по Шри-Ланке

Цифровые кочевники слушают: что нужно знать о новой визе DTV в Таиланде

Модель Bitcoin UTXO, обеспечивающая работу уникальной экосистемы

Утечка информации о системе Claude Sonnet 3.5: судебно-медицинский анализ

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps