Рубрики

Головоломка | Набор 35 (2 яйца и 100 этажей)

Ниже приводится описание случая этой знаменитой головоломки, включающей 2 яйца и здание с 100 этажами.

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

Мы можем сделать несколько предположений:

  • Яйцо, пережившее падение, можно использовать снова.
  • Разбитое яйцо нужно выбросить.
  • Эффект падения одинаков для всех яиц.
  • Если яйцо сломается при падении, оно сломается, если его упадет с верхнего этажа.
  • Если яйцо переживет падение, оно переживет более короткое падение.

Мы настоятельно рекомендуем вам свернуть браузер и сначала попробовать это самостоятельно.

Если доступно только одно яйцо, и мы хотим быть уверенными в получении правильного результата, эксперимент можно провести только одним способом. Бросьте яйцо из окна первого этажа; если он выживет, бросьте его из окна второго этажа. Продолжайте вверх, пока не сломается. В худшем случае этот метод может потребовать 100 помет.
Предположим, 2 яйца доступны. Какое наименьшее количество помета для яиц гарантированно работает во всех случаях?
Проблема на самом деле не в том, чтобы найти критический этаж, а просто в определении этажей, с которых следует сбрасывать яйца, чтобы минимизировать общее количество испытаний.

Если мы используем метод бинарного поиска, чтобы найти слово, и мы начинаем с 50-го этажа, то в худшем случае мы получим 50 сравнений. Наихудший случай случается, когда требуемый этаж занимает 49-й этаж.

Оптимизированный метод:
Идея состоит в том, чтобы оптимизировать решение, используя приведенное ниже уравнение:

Let us make our first attempt on x'th floor. 

If it breaks, we try remaining (x-1) floors one by one. 
So in worst case, we make x trials.

If it doesn’t break, we jump (x-1) floors (Because we have
already made one attempt and we don't want to go beyond 
x attempts.  Therefore (x-1) attempts are available),
    Next floor we try is floor x + (x-1)

Similarly, if this drop does not break, next need to jump 
up to floor x + (x-1) + (x-2), then x + (x-1) + (x-2) + (x-3)
and so on.

Since the last floor to be tried is 100'th floor, sum of
series should be 100 for optimal value of x.

 x + (x-1) + (x-2) + (x-3) + .... + 1  = 100

 x(x+1)/2  = 100
         x = 13.651

Therefore, we start trying from 14'th floor. If Egg breaks
we one by one try remaining 13 floors.  If egg doesn't break
we go to 27th floor.
If egg breaks on 27'th floor, we try floors form 15 to 26.
If egg doesn't break on 27'th floor, we go to 39'th floor.

An so on...

Оптимальное количество испытаний — 14 в худшем случае.

Ниже приведено программное решение для общих k яиц и n этажей.
http://espressocode.top/dynamic-programming-set-11-egg-dropping-puzzle/

Эта статья предоставлена Rachit . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Головоломка | Набор 35 (2 яйца и 100 этажей)

0.00 (0%) 0 votes