Три яйца

Я просто читал "Проблема с двумя яйцами":

Проблема с двумя яйцами

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

Если яйцо ломается при падении с пола n, то оно также сломается с любого пола над ним. Если яйцо выживет осенью, то оно выдержит любое падение ниже этого.

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

Я следовал за ним до тех пор, пока раздел "Смотри, что я могу сделать три". Автор утверждает, что после разрыва первого яйца он деградирует в проблему с 2 яйцами и может быть решен рекурсивно.

Это здорово, но разве мы не хотим выбирать большие размеры шага при использовании 3 яиц вместо 2 (для первого яйца)? С какого пола мы бросаем первое яйцо?

С 1 яйцом мы должны начать с 1-го этажа.
С 2 яйцами мы решаем для n(n+1)/2=k и округляем вверх, где n - начальный этаж, а k - количество этажей.
С 3... У меня проблемы с формулой.

Размышляя об этом немного больше, с двумя яйцами, максимальное количество капель равно числу пола, из которого мы отбрасываем наше первое яйцо. Например, с 2 яйцами и 100 этажами, решение равно 14, что означает, что мы бросаем первое яйцо с пола 14, и если оно ломается, нам приходится выпадать до 13 раз, для этажей 1-13.

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

Если мы снова выбросимся с пола 14, и он сломается, тогда мы рекурсируем. n(n+1)/2=k где k теперь 13... но это дает нам 4.815, если мы потопим и что и добавим наше предыдущее падение, получим 6, что ниже фактического решения, поэтому что-то здесь неправильно...

Ответ 1

Если мы снова выбросимся с пола 14, и он сломается, тогда мы рекурсируем. n (n + 1)/2 = k, где k теперь 13... но это дает нам 4.815, если мы потопим и что и добавим наше предыдущее падение, получим 6, что ниже фактического решения, поэтому что-то здесь неправильно...

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

Скажем, вы уроните первое яйцо с 50- ^го этажа. Если он сломается, у вас есть проблема с двумя яйцами с 49 этажами, которая занимает до 10 дополнительных капель. Таким образом, это даст вам худший случай из 11 капель (поскольку, если он не сломается, 50-этажная проблема с тремя яйцами занимает не более 7 дополнительных капель).

Если вы выбираете 37- ^й этаж для первой капли, если он ломается, у вас есть 36-этажная проблема с двумя яйцами, требующая до 8 дополнительных капель. Если он не сломается, у вас осталась 63-этажная проблема с тремя яйцами. Вы хотите решить эту проблему не более чем на 8 капель, поэтому, если следующая капля разрывает яйцо, оставшаяся проблема с двумя яйцами должна быть разрешена не более 7 капель, таким образом, самый высокий этаж, который вы можете выбрать для второй капли, составляет 37 + 28 + 1 = 66, так как 28 этажей - это самое высокое, что вы можете решить, максимум 7 капель и два яйца. Если яйцо не сломается, у вас есть 34-этажная проблема с тремя яйцами с 7 каплями. Самое высокое, что вы можете решить с оставшимися 6 капельками, если яйцо разрывается, составляет 21 (6 * 7/2), поэтому вы можете выбрать пол 66 + 21 + 1 = 88. Если яйцо не сломается, у вас осталось 12 этажей с 6 каплями, что уже возможно только с двумя яйцами.

Систематически наибольшее количество этажей, которые вы, безусловно, можете решить с помощью d капель и e яиц,

          / 1, if d == 1
F(e,d) = |  d, if e == 1
          \ F(e-1,d-1) + 1 + F(e,d-1), if e > 1 and d > 1

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

Если у вас есть только одно яйцо, вам нужно проверять каждый этаж, пока яйцо не сломается или у вас не будет капель.

В противном случае, если первая капля с пола выше F(e-1,d-1) + 1, вы не сможете найти первый сломанный пол, если яйцо сломается. Если первая капля идет с нижнего этажа, вы не можете достичь столь же высокого уровня с помощью d-1 капель, если яйцо не сломается, поэтому первая капля должна быть от пола F(e-1,d-1) + 1, Если он сломается, вы можете решить с остальными яйцами e-1 и d-1 каплями по предположению. Если нет, вы можете решить для следующих этажей F(e,d-1) оставшиеся капли и яйца.

С другой стороны, чтобы найти, сколько капель вам может понадобиться для f полов с e яйцами, вы должны найти

D(e,f) = min { d | F(e,d) >= f }

Вы можете найти это, вычислив матрицу F(e,d), или вы можете использовать динамическое программирование:

Если вы выбираете пол s для первой капли, если яйцо ломается, вам нужно до D(e-1,s-1) капли, чтобы определить пол. Если яйцо не сломается, вам нужно до D(e,fs) капли, чтобы определить пол. Так что в худшем случае при выборе пола s для первой капли

WC(s,e,f) = 1 + max { D(e-1,s-1), D(e,f-s) }

и лучшим из худших случаев является

D(e,f) = minimum { WC(s,e,f) | 1 <= s <= f }

(где, конечно, D(e,0) = 0).

Ответ 2

Эта проблема может быть решена следующими тремя подходами (что я знаю):

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

Позвольте мне сначала определить некоторые символы следующим образом:

e = number of eggs
f = number of floors in building
n = number of egg drops 
Fmax(e, n) = maximum number of floors that can be tested with e eggs and n drops

Основа для подхода к динамическому программированию заключается в следующей рекурсивной формуле для Fmax:

Fmax(e, n) = 1 + Fmax(e-1, n-1) + fmax(e, n-1)

И суть для получения прямой математической формулы для Fmax заключается в следующей рекурсивной формуле для Fmax:

Fmax(e, n) = { ∑Fmax(e-1,i) for i = 1 to n } - Fmax(e-1, n) + n

Альтернативное решение, использующее двоичное дерево поиска (BST), также возможно для этой проблемы. Чтобы облегчить наш анализ, сделаем BST с небольшими изменениями следующим образом:

1.    If egg breaks then child node is drawn on left down side
2.    If egg does not break then child node is drawn straight down side

Если мы рисуем BST с таким видом представления, тогда ширина BST (т.е. количество вертикальных столбцов в BST) представляет количество яиц.

Любой BST с f числом узлов, нарисованный с помощью такого типа представления и подверженный ширине ограничения BST <= e (количество яиц), является решением, но это может быть не оптимальное решение.

Следовательно, получение оптимального решения эквивалентно получению расположения узлов в BST с минимальной высотой, подпадающей под ограничение: ширина BST <= e

Для получения более подробной информации обо всех вышеуказанных трех подходах, проверьте мой блог на: 3 подходах к решению проблемы генерализованного яйцеклада

Ответ 3

Вы можете использовать простое решение динамического программирования. n - количество этажей. k - количество яиц. D [n, k] = вы отвечаете (количество минимальных бросков). D [j, 1] = n-1 для каждого 1 <= j <= n.

Основная идея расчета D [n, k] при k> 1:

D [n, k] = максимум 1 <= j <= n-1 {максимум {D [j, k-1] +1, D [nj, k] +1}.