Впервые я прочитал эту проблему в Руководстве по разработке алгоритмов Стивена Скиены (упражнение 8.15). Далее следовала глава о динамическом программировании, но вам не нужно знать динамическое программирование, чтобы доказать точные границы стратегии . Сначала постановка задачи, а затем приведенное ниже решение.
Яйца разбиваются при падении с достаточно большой высоты. Учитывая n-этажное здание, должен быть этаж f, чтобы яйца падали с пола f, но яйца, сброшенные с пола f-1, выживают. (Если яйцо разбивается с любого пола, мы скажем f = 1. Если яйцо выживет с любого пола, мы скажем f = n + 1).
Вы пытаетесь найти критический этаж f. Единственная операция, которую вы можете выполнить, это сбросить яйцо с пола и посмотреть, что произойдет. Вы начинаете с k яиц, и стараетесь бросать яйца как можно меньше раз. Разбитые яйца нельзя использовать повторно (неповрежденные яйца могут). Пусть E (k, n) будет минимальным количеством помета яиц, которого всегда будет достаточно.
- Показать, что E (1, n) = n.
- Показать, что
E(k,n) = Θ(n**(1/k))
.
- Найдите повторение для E (k, n). Каково время работы динамической программы для поиска E (k, n)?
только 1 яйцо
Если сбросить яйцо с каждого этажа, начиная с первого, найдется критический этаж в (в худшем случае) n операций.
Нет более быстрого алгоритма. В любое время в любом алгоритме, пусть g самый высокий этаж, с которого было замечено, что яйцо не разбилось. Алгоритм должен проверять этаж g + 1 перед любым верхним этажом h> g + 1, иначе, если яйцо оторвется от пола h, он не сможет различить f = g + 1 и f = h.
2 яйца
Сначала рассмотрим случай k = 2 яиц, когда n = r ** 2 - идеальный квадрат. Вот стратегия, которая занимает O (sqrt (n)) время. Начните с того, что опустите первое яйцо с шагом r этажа. Когда первое яйцо разбивается, скажем, на этаже ar
, мы знаем, что критический этаж f должен быть (a-1)r < f <= ar
. Затем мы бросаем второе яйцо с каждого этажа, начиная с (a-1)r
. Когда второе яйцо разбивается, мы нашли критический этаж. Мы отбрасывали каждое яйцо не более r раз, поэтому этот алгоритм выполняет в худшем случае 2r операций, что равно is (sqrt (n)).
Когда n не является идеальным квадратом, возьмите r = ceil(sqrt(n)) ∈ Θ(sqrt(n))
. Алгоритм остается Θ (sqrt (n)).
Доказательство того, что любой алгоритм требует как минимум sqrt (n) времени. Предположим, есть более быстрый алгоритм. Рассмотрим последовательность этажей, с которых оно сбрасывает первое яйцо (пока оно не разбивается). Так как он падает меньше, чем sqrt (n), интервал должен быть не менее n / sqrt (n), который равен sqrt (n). Когда f находится в этом интервале, алгоритм должен будет исследовать его со вторым яйцом, и это должно быть сделано поэтапно, напоминая случай с 1 яйцом. ПРОТИВОРЕЧИЕ.
k яиц
Алгоритм, представленный для 2 яиц, может быть легко расширен до k яиц. Отбрасывайте каждое яйцо с постоянными интервалами, которые следует принимать в качестве степеней k-го корня n. Например, для n = 1000 и k = 3, ищите интервалы в 100 этажей с первым яйцом, 10 с вторым яйцом и 1 с последним яйцом.
Аналогично, мы можем доказать, что ни один алгоритм не является более быстрым Θ(n**(1/k))
, индуцируя из доказательства k = 2.
Точное решение
Мы выводим рецидив, оптимизируя, куда бросить первое яйцо (пол g), предполагая, что мы знаем оптимальные решения для меньших параметров. Если яйцо разбивается, у нас есть этажи g-1 ниже, чтобы исследовать с яйцами k-1. Если яйцо выживет, у нас есть n-g этажей для исследования с k яйцами. Дьявол выбирает худшее для нас. Таким образом, для k> 1 повторение
E(k,n) = min(max(E(k,n-g), E(k-1,g))) minimised over g in 1..n