Как решить задачу на Поиск граничного элемента? Есть следующая задача, если написать алгоритм для нахождения F с скоростью lg N не составляет никакого труда и все решается обычным бинарным поиском, то алгоритм способный решить такую задачу за lg F я ни как не могу придумать, как и алгоритм который бы решал задачу за 2√N. Мне не нужен код, просто подскажите пожалуйста с чего начать и как подступиться к реализации этих алгоритмов
===== Сама задача =====
Имеется здание из N этажей и неограниченное количество яиц. Будет считать, что яйцо разбивается, если оно падает с этажа F или выше. Если яйцо падает с этажа ниже, то оно остается целым и может быть использовано повторно. Требуется реализовать алгоритм поиска значения F при условии, что можно разбить примерно lgN яиц и выполнить примерно lg N попыток.
Модернизируйте алгоритм поиска таким образом, чтобы количество попыток было примерно lgF при условии, что N много больше F.
Дополнительно. Решите задачу при условии, что имеется всего два яйца. Реализуйте алгоритм поиска F с количеством попыток, не превышающем 2(√N). Попробуйте уменьшить стоимость поиска до C(√N) для некоторой константы C.
Как решить задачу на Поиск граничного элемента? Есть следующая задача, если написать алгоритм для нахождения F с скоростью lg N не составляет никакого труда и все решается обычным бинарным поиском, то алгоритм способный решить такую задачу за lg F я ни как не могу придумать, как и алгоритм который бы решал задачу за 2√N. Мне не нужен код, просто подскажите пожалуйста с чего начать и как подступиться к реализации этих алгоритмов
===== Сама задача =====
Имеется здание из N этажей и неограниченное количество яиц. Будет считать, что яйцо разбивается, если оно падает с этажа F или выше. Если яйцо падает с этажа ниже, то оно остается целым и может быть использовано повторно. Требуется реализовать алгоритм поиска значения F при условии, что можно разбить примерно lgN яиц и выполнить примерно lg N попыток.
Модернизируйте алгоритм поиска таким образом, чтобы количество попыток было примерно lgF при условии, что N много больше F.
Дополнительно. Решите задачу при условии, что имеется всего два яйца. Реализуйте алгоритм поиска F с количеством попыток, не превышающем 2(√N). Попробуйте уменьшить стоимость поиска до C(√N) для некоторой константы C.
===== Сама задача =====
Имеется здание из N этажей и неограниченное количество яиц. Будет считать, что яйцо разбивается, если оно падает с этажа F или выше. Если яйцо падает с этажа ниже, то оно остается целым и может быть использовано повторно. Требуется реализовать алгоритм поиска значения F при условии, что можно разбить примерно lgN яиц и выполнить примерно lg N попыток.
Модернизируйте алгоритм поиска таким образом, чтобы количество попыток было примерно lgF при условии, что N много больше F.
Дополнительно. Решите задачу при условии, что имеется всего два яйца. Реализуйте алгоритм поиска F с количеством попыток, не превышающем 2(√N). Попробуйте уменьшить стоимость поиска до C(√N) для некоторой константы C.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для решения данной задачи можно воспользоваться методом динамического программирования.
Для начала рассмотрим случай, когда у нас есть всего два яйца. Для этого можно воспользоваться методом проб и ошибок. Начните с броска яйца с первого этажа, затем второго, третьего и т.д., пока яйцо не разобьется. Таким образом, вы найдете значение F в худшем случае за O(F) попыток, что соответствует 2(√N).
Для случая с бесконечным количеством яиц можно воспользоваться методом дихотомии. Разобьем диапазон этажей на интервалы определенной длины (например, корень из общего числа этажей). Затем начнем бросать яйца, начиная с нижнего конца каждого интервала. Как только одно из яиц разобьется, мы будем знать, что F находится в предыдущем интервале. Перейдем к броскам в этом интервале с шагом 1, пока не найдем точное значение F. Таким образом, мы найдем значение F за lgF попыток.
Чтобы добиться стоимости поиска до C(√N) для некоторой константы C, можно воспользоваться случаем с двумя яйцами и улучшить его, например, применив более точные методы определения второго яйца, которое будет разбиваться.
Надеюсь, это поможет вам начать работу над алгоритмами для решения данной задачи.