Как выбросить 2 яйца из здания и найти этаж F с помощью бросков ~ c * sqrt (F)?

Я читаю книгу Роберта Седжвика по алгоритмам 4-го издания, и перед ним стоит следующая задача:

Предположим, у вас есть N-этажное здание и 2 яйца. Предположим также, что яйцо разбито, если оно брошено с этажа F или выше, и не разбито в противном случае. Ваша модель затрат - это количество бросков. Разработайте стратегию определения F так, чтобы количество бросков ~ c √ F для некоторой константы c.

Первая часть задачи - найти F за 2 √ N шагов, и вот решение для этого:

Решение части 1:

  • Чтобы получить 2 * sqrt (N), бросьте яйца на этажи sqrt (N), 2 * sqrt (N), 3 * sqrt (N), ..., sqrt (N) * sqrt (N). (Для простоты мы предполагаем, что sqrt (N) является целым числом.)
  • Предположим, что яйцо разбилось на уровне k * sqrt (N).
  • Затем со вторым яйцом вы должны выполнить линейный поиск в интервале от (k-1) * sqrt (N) до k * sqrt (N).
  • Всего вы сможете найти этаж F не более чем за 2 * sqrt (N) испытаний.

Он также дает подсказку для части ~ c √ F (часть 2):

Подсказка для Части 2: 1 + 2 + 3 + ... k ~ 1/2 k ^ 2.

Итак, каков алгоритм, чтобы сделать это за ~ c √ F шагов?


search algorithm dynamic-programming binary-search divide-and-conquer
person Pavel    schedule 30.04.2015    source источник
comment
Вот вопрос, обсуждающий общий случай первой части, но с использованием кошек вместо яиц. stackoverflow.com/questions/3974077/ < / а>   -  person Klas Lindbäck    schedule 30.04.2015
comment
@ KlasLindbäck, спасибо!   -  person Pavel    schedule 30.04.2015
comment
Это популярный вопрос для интервью в Bay Area 10 лет назад. даже Google тоже задает этот вопрос кандидатам. :)   -  person BufBills    schedule 30.04.2015
comment
@BufBills, спасибо, вы понимаете, как работает алгоритм принятого ответа? Я правда не понимаю, почему дает 14 на 100 этажей и 2 кота, разве не 51? Мы можем сначала посмотреть на этаж 50, затем с этажа 51 и выше нам нужно выполнить только линейный поиск, потому что у нас осталась только 1 кошка ..   -  person Pavel    schedule 30.04.2015
comment
n + (n-1) + (n-2) + (n-3) + (n-4) +… + 1 ›= 100 Это суммирование, как многие узнают, является формулой для треугольных чисел ( имеет смысл, поскольку мы уменьшаем шаг на единицу при каждой сделанной капле) и может быть упрощено до: n (n + 1) / 2 ›= 100 Это квадратное уравнение с положительным корнем из 13,651 (что мы имеем округлить до 14. Это не фильм Джона Малковича!).   -  person BufBills    schedule 30.04.2015
comment
@BufBills нет, я про другой вопрос! Я хотел спросить Класа Линдбека, прости   -  person Pavel    schedule 01.05.2015
comment
@ KlasLindbäck, понимаете ли вы, как работает алгоритм принятого ответа (в присланной вами ссылке)? Я правда не понимаю, почему дает 14 на 100 этажей и 2 кота, разве не 51? Мы можем сначала посмотреть на этаж 50, затем с этажа 51 и выше нам нужно выполнить только линейный поиск, потому что у нас осталась только одна кошка.   -  person Pavel    schedule 01.05.2015
comment
Допустим, у вас 14 попыток. Какую высоту вы можете перекрыть? Бросьте первое яйцо с этажа 14 (оставление 13 пытается покрыть этажи 1-13, если яйцо разбивается). Затем сбросьте его с этажа 14 + 13 = 27 (оставив 12 попыток покрыть промежуточный этаж). Тогда продолжай так. С 14 попытками вы можете покрыть здание высотой до (14 + 13 + 12 + 11 + 10 + 9 + ... + 1 =) 105 этажей. Формула на самом деле является общей, поэтому с помощью k попыток вы можете покрыть здание высотой до (1 + 2 + ... + k =) k*(k+1)/2 этажей.   -  person Klas Lindbäck    schedule 03.05.2015
comment
@ KlasLindbäck, спасибо, а как ты это понял?   -  person Pavel    schedule 03.05.2015
comment
Читая (фактически просматривая) связанную страницу, Хенрикс отвечает на этот вопрос, а затем размышляет о том, что у них общего (и чем они отличаются). Как видите, в обоих случаях фигурирует сумма 1 + 2 + 3 + 4 + ...! Обратите внимание, что навыки решения проблем зависят от способностей, образования и практики, так что продолжайте практиковаться! Как улучшить свои навыки решения проблем, это хорошая тема для сообщения в блоге ...   -  person Klas Lindbäck    schedule 04.05.2015
comment
@ KlasLindbäck да, я участвую в соревнованиях codeforces.ru каждую неделю, но я еще не так хорош   -  person Pavel    schedule 04.05.2015

Ответы (1)


arrow_upward
6
arrow_downward

Бросьте первое яйцо с этажей 1, 3, 6, ... (частичные суммы 1, 2, 3, ...). Затем выполните линейный поиск между двумя последними этажами.

person Henrik    schedule 30.04.2015