Рубрики

Пазл с яйцом | DP-11

Ниже приведено описание случая этой знаменитой головоломки с n = 2 яйцами и зданием с k = 36 этажами.

Предположим, что мы хотим знать, из каких историй в 36-этажном здании безопасно бросать яйца, а какие разбивают яйца при приземлении. Мы делаем несколько предположений:

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

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

Источник: Wiki для динамического программирования

В этом посте мы обсудим решение общей проблемы с n яйцами и k этажами. Решение состоит в том, чтобы попытаться бросить яйцо со всех этажей (от 1 до k) и рекурсивно рассчитать минимальное количество помета, необходимое в худшем случае. Пол, который дает минимальное значение в худшем случае, будет частью решения.
В следующих решениях мы возвращаем минимальное количество испытаний в худшем случае; эти решения могут быть легко изменены, чтобы печатать номера этажей каждого испытания также.

1) Оптимальная подструктура:
Когда мы бросаем яйцо с пола х, может быть два случая: (1) разбивание яиц (2) яйцо не разбивается.

1) Если яйцо разбивается после падения с x-го этажа, то нам нужно только проверить наличие этажей ниже x с оставшимися яйцами; поэтому проблема сводится к х-1 этажам и п-1 яйцам
2) Если яйцо не разбилось после падения с x-го этажа, то нам нужно только проверить наличие этажей выше x; так что проблема сводится к kx этажей и n яиц.

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

  k ==> Number of floors
  n ==> Number of Eggs
  eggDrop(n, k) ==> Minimum number of trials needed to find the critical
                    floor in worst case.
  eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)): 
                 x in {1, 2, ..., k}}

2) Перекрывающиеся подзадачи
Ниже приводится рекурсивная реализация, которая просто следует рекурсивной структуре, упомянутой выше.

C ++

#include<bits/stdc++.h>

using namespace std;

  
// Вспомогательная функция для получения максимум двух целых

int max(int a, int b) { return (a > b)? a: b; }

  
/ * Функция для получения минимального количества испытаний, необходимых в худшем случае
ящик с n яйцами и k этажами * /

int eggDrop(int n, int k)

{

    // Если этажей нет, то испытания не нужны. ИЛИ если есть

    // один этаж, одно испытание

    if (k == 1 || k == 0)

        return k;

  

    // Нам нужно k испытаний для одного яйца и k этажей

    if (n == 1)

        return k;

  

    int min = INT_MAX, x, res;

  

    // Рассмотрим все помёт от 1-го этажа до k-го этажа и

    // вернуть минимум этих значений плюс 1.

    for (x = 1; x <= k; x++)

    {

        res = max(eggDrop(n-1, x-1), eggDrop(n, k-x));

        if (res < min)

            min = res;

    }

  

    return min + 1;

}

  
/ * Программа драйвера для проверки на печать printDups * /

int main()

{

    int n = 2, k = 10;

    cout << "Minimum number of trials in worst case with "

         << n << " eggs and " << k << " floors is " 

         << eggDrop(n, k) << endl;

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

# include <stdio.h>
# include <limits.h>

  
// Вспомогательная функция для получения максимум двух целых

int max(int a, int b) { return (a > b)? a: b; }

  
/ * Функция для получения минимального количества испытаний, необходимых в худшем случае

  ящик с n яйцами и k этажами * /

int eggDrop(int n, int k)

{

    // Если этажей нет, то испытания не нужны. ИЛИ если есть

    // один этаж, одно испытание

    if (k == 1 || k == 0)

        return k;

  

    // Нам нужно k испытаний для одного яйца и k этажей

    if (n == 1)

        return k;

  

    int min = INT_MAX, x, res;

  

    // Рассмотрим все помёт от 1-го этажа до k-го этажа и

    // вернуть минимум этих значений плюс 1.

    for (x = 1; x <= k; x++)

    {

        res = max(eggDrop(n-1, x-1), eggDrop(n, k-x));

        if (res < min)

            min = res;

    }

  

    return min + 1;

}

  
/ * Программа драйвера для проверки на печать printDups * /

int main()

{

    int n = 2, k = 10;

    printf ("nMinimum number of trials in worst case with %d eggs and "

             "%d floors is %d \n", n, k, eggDrop(n, k));

    return 0;

}

Джава

public class GFG { 

      

    / * Функция для получения минимального количества

    испытания нужны в худшем случае с п

    яйца и k этажей * /

    static int eggDrop(int n, int k) 

    

        // Если этажей нет, то

        // никаких испытаний не требуется. ИЛИ если есть

        // один этаж, нужно одно испытание

        if (k == 1 || k == 0

            return k; 

      

        // Нам нужно k испытаний для одного яйца

        // и k этажей

        if (n == 1

            return k; 

      

        int min = Integer.MAX_VALUE; 

        int x, res; 

      

        // Учитываем все пометы из

        // с 1 по 2 этаж и

        // вернуть минимум

        // значения плюс 1.

        for (x = 1; x <= k; x++) 

        

            res = Math.max(eggDrop(n-1, x-1), 

                        eggDrop(n, k-x)); 

            if (res < min) 

                min = res; 

        

      

        return min + 1

    

      

    // Код драйвера

    public static void main(String args[]) 

    

        int n = 2, k = 10

        System.out.print("Minimum number of "

            + "trials in worst case with "

                + n + " eggs and " + k 

        + " floors is " + eggDrop(n, k)); 

    

    // Этот код предоставлен Ryuga.

Python 3

import sys 

  
# Функция для получения минимального количества испытаний
# требуется в худшем случае с n яйцами и k этажами

def eggDrop(n, k):

  

    # Если нет этажей, то нет испытаний

    # нужно. ИЛИ если есть один этаж, один

    # пробная версия нужна.

    if (k == 1 or k == 0):

        return k

  

    # Нам нужно k испытаний для одного яйца

    # и k этажей

    if (n == 1):

        return k

  

    min = sys.maxsize

  

    # Рассмотрим все помет от 1-го

    # этаж на kth этаж и возвращение

    # минимум этих значений плюс 1.

    for x in range(1, k + 1):

  

        res = max(eggDrop(n - 1, x - 1), 

                  eggDrop(n, k - x))

        if (res < min):

            min = res

  

    return min + 1

  
Код водителя

if __name__ == "__main__":

  

    n = 2

    k = 10

    print("Minimum number of trials in worst case with",

           n, "eggs and", k, "floors is", eggDrop(n, k))

  
# Этот код предоставлен ita_c

C #

using System;

  

class GFG {

      

    / * Функция для получения минимального количества

    испытания нужны в худшем случае с п

    яйца и k этажей * /

    static int eggDrop(int n, int k)

    {

        // Если этажей нет, то

        // никаких испытаний не требуется. ИЛИ если есть

        // один этаж, нужно одно испытание

        if (k == 1 || k == 0)

            return k;

      

        // Нам нужно k испытаний для одного яйца

        // и k этажей

        if (n == 1)

            return k;

      

        int min = int.MaxValue;

        int x, res;

      

        // Учитываем все пометы из

        // с 1 по 2 этаж и

        // вернуть минимум

        // значения плюс 1.

        for (x = 1; x <= k; x++)

        {

            res = Math.Max(eggDrop(n-1, x-1), 

                           eggDrop(n, k-x));

            if (res < min)

                min = res;

        }

      

        return min + 1;

    }

      

    // Код драйвера

    static void Main()

    {

        int n = 2, k = 10;

        Console.Write("Minimum number of "

            + "trials in worst case with "

                   + n + " eggs and " + k

          + " floors is " + eggDrop(n, k));

    }

}

  
// Этот код предоставлен Sam007.


Выход:

Minimum number of trials in worst case with 2 eggs and 10 floors is 4

Следует отметить, что вышеуказанная функция снова и снова вычисляет одни и те же подзадачи. Смотрите следующее дерево частичной рекурсии, E (2, 2) оценивается дважды. Будет много повторяющихся подзадач, когда вы рисуете полное дерево рекурсии даже для небольших значений n и k.


                         E(2,4)
                           |                      
          ------------------------------------- 
          |             |           |         |   
          |             |           |         |       
      x=1/          x=2/      x=3/     x=4/ 
        /             /         ....      ....
       /             /    
 E(1,0)  E(2,3)     E(1,1)  E(2,2)
          /  /...         /  
      x=1/                 .....
        /    
     E(1,0)  E(2,2)
            /   
            ......

Partial recursion tree for 2 eggs and 4 floors.

Поскольку те же самые подзадачи вызываются снова, эта проблема имеет свойство Перекрывающиеся подзадачи. Таким образом, Egg Dropping Puzzle обладает обоими свойствами (см. Это и это ) задачи динамического программирования. Как и другие типичные проблемы динамического программирования (DP) , повторных вычислений с одинаковыми подзадачами можно избежать, построив временный массив eggFloor [] [] снизу вверх.

Решение для динамического программирования
Ниже приведены реализации для решения проблемы сброса яиц с использованием динамического программирования.

C ++

// Программа C ++ на основе динамического программирования для головоломки с яйцом
# include <stdio.h>
# include <limits.h>

  
// Вспомогательная функция для получения максимум двух целых

int max(int a, int b) { return (a > b)? a: b; }

  
/ * Функция для получения минимального количества испытаний, необходимых в худшем случае

  ящик с n яйцами и k этажами * /

int eggDrop(int n, int k)

{

    / * 2D-таблица, где entery eggFloor [i] [j] будет представлять минимум

       количество испытаний, необходимых для яиц и я этажей. * /

    int eggFloor[n+1][k+1];

    int res;

    int i, j, x;

  

    // Нам нужно одно испытание для одного этажа и 0 испытаний для 0 этажей

    for (i = 1; i <= n; i++)

    {

        eggFloor[i][1] = 1;

        eggFloor[i][0] = 0;

    }

  

    // Нам всегда нужны j испытаний для одного яйца и j этажей.

    for (j = 1; j <= k; j++)

        eggFloor[1][j] = j;

  

    // Заполняем остальные записи в таблице, используя оптимальную подструктуру

    // свойство

    for (i = 2; i <= n; i++)

    {

        for (j = 2; j <= k; j++)

        {

            eggFloor[i][j] = INT_MAX;

            for (x = 1; x <= j; x++)

            {

                res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);

                if (res < eggFloor[i][j])

                    eggFloor[i][j] = res;

            }

        }

    }

  

    // eggFloor [n] [k] содержит результат

    return eggFloor[n][k];

}

  
/ * Программа драйвера для проверки на печать printDups * /

int main()

{

    int n = 2, k = 36;

    printf ("nMinimum number of trials in worst case with %d eggs and "

             "%d floors is %d \n", n, k, eggDrop(n, k));

    return 0;

}

Джава

// Java-программа на основе динамического программирования для головоломки с яйцом

class EggDrop

{

    // Вспомогательная функция для получения максимум двух целых

    static int max(int a, int b) { return (a > b)? a: b; }

       

    / * Функция для получения минимального количества испытаний, необходимых в худшем случае

    ящик с n яйцами и k этажами * /

    static int eggDrop(int n, int k)

    {

       / * 2D-таблица, где entery eggFloor [i] [j] будет представлять минимум

       количество испытаний, необходимых для яиц и я этажей. * /

        int eggFloor[][] = new int[n+1][k+1];

        int res;

        int i, j, x;

           

        // Нам нужно одно испытание для одного этажа и 0 испытаний для 0 этажей

        for (i = 1; i <= n; i++)

        {

            eggFloor[i][1] = 1;

            eggFloor[i][0] = 0;

        }

           

       // Нам всегда нужны j испытаний для одного яйца и j этажей.

        for (j = 1; j <= k; j++)

            eggFloor[1][j] = j;

           

        // Заполняем остальные записи в таблице, используя оптимальную подструктуру

        // свойство

        for (i = 2; i <= n; i++)

        {

            for (j = 2; j <= k; j++)

            {

                eggFloor[i][j] = Integer.MAX_VALUE;

                for (x = 1; x <= j; x++)

                {

                     res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);

                     if (res < eggFloor[i][j])

                        eggFloor[i][j] = res;

                }

            }

        }

           

        // eggFloor [n] [k] содержит результат

        return eggFloor[n][k];

  

    }

           

    / * Программа драйвера для проверки на печать printDups * /

    public static void  main(String args[] )

    {

        int n = 2, k = 10;

        System.out.println("Minimum number of trials in worst case with "+n+"  eggs and "+k+

                 " floors is "+eggDrop(n, k));   

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Python-программа на основе динамического программирования для головоломки Egg Dropping

INT_MAX = 32767

  
# Функция для получения минимального количества испытаний, необходимых в худшем случае
# кейс с n яйцами и k этажами

def eggDrop(n, k):

    # 2D-таблица, где entery eggFloor [i] [j] будет представлять минимум

    # количество испытаний, необходимых для яиц и я этажей.

    eggFloor = [[0 for x in range(k+1)] for x in range(n+1)]

  

    # Нам нужно одно испытание для одного этажа и 0 испытаний для 0 этажей

    for i in range(1, n+1):

        eggFloor[i][1] = 1

        eggFloor[i][0] = 0

  

    # Нам всегда нужны j испытаний для одного яйца и j этажей.

    for j in range(1, k+1):

        eggFloor[1][j] = j

  

    # Заполните остальные записи в таблице, используя оптимальную подструктуру

    # свойство

    for i in range(2, n+1):

        for j in range(2, k+1):

            eggFloor[i][j] = INT_MAX

            for x in range(1, j+1):

                res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x])

                if res < eggFloor[i][j]:

                    eggFloor[i][j] = res

  

    # eggFloor [n] [k] содержит результат

    return eggFloor[n][k]

  
# Драйвер программы для проверки на печать printDups

n = 2

k = 36

print("Minimum number of trials in worst case with" + str(n) + "eggs and " 

       + str(k) + " floors is " + str(eggDrop(n, k)))

  
# Этот код предоставлен Bhavya Jain

C #

// Программа C # на основе динамического программирования
// для головоломки с яйцом

using System;

  

class GFG {

      

    // Функция полезности, чтобы получить максимум

    // два целых числа

    static int max(int a, int b) 

    {

        return (a > b) ? a: b;

    }

      

    / * Функция для получения минимального количества

    испытания нужны в худшем случае с п

    яйца и k этажей * /

    static int eggDrop(int n, int k)

    {

          

        / * 2D-таблица, где Entery eggFloor [i] [j]

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

        нужны для яиц и j этажей. * /

        int [,]eggFloor = new int[n+1,k+1];

        int res;

        int i, j, x;

          

        // нам нужно одно испытание на один этаж и0

        // испытания для 0 этажей

        for (i = 1; i <= n; i++)

        {

            eggFloor[i,1] = 1;

            eggFloor[i,0] = 0;

        }

          

        // нам всегда нужны j испытаний для одного яйца

        // и j этажи.

        for (j = 1; j <= k; j++)

            eggFloor[1,j] = j;

          

        // Заполняем остальные записи в таблице

        // используя оптимальное свойство подструктуры

        for (i = 2; i <= n; i++)

        {

            for (j = 2; j <= k; j++)

            {

                eggFloor[i,j] = int.MaxValue;

                for (x = 1; x <= j; x++)

                {

                    res = 1 + max(eggFloor[i-1,x-1],

                                  eggFloor[i,j-x]);

                    if (res < eggFloor[i,j])

                        eggFloor[i,j] = res;

                }

            }

        }

          

        // eggFloor [n] [k] содержит результат

        return eggFloor[n,k];

  

    }

  

    // Функция драйвера

    public static void Main()

    {

        int n = 2, k = 36;

        Console.WriteLine("Minimum number of trials "

           + "in worst case with " + n + " eggs and "

                 + k + "floors is " + eggDrop(n, k)); 

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// Динамическое программирование на основе PHP
// Программа для головоломки с яйцом

  
/ * Функция для получения минимального числа

   испытаний нужно в худшем

   ящик с n яйцами и k этажами * /

function eggDrop($n, $k)

{

      

    / * 2D-таблица, где Entery eggFloor [i] [j]

       будет представлять минимальное количество

       испытания, необходимые для яиц и я этажей. * /

    $eggFloor = array(array());;

      

    // Нам нужно одно испытание для одного

    // Этаж и 0 испытаний для 0 этажей

    for ($i = 1; $i <=$n;$i++)

    {

        $eggFloor[$i][1] = 1;

        $eggFloor[$i][0] = 0;

    }

  

    // нам всегда нужны j испытания

    // для одного яйца и j этажей.

    for ($j = 1; $j <= $k; $j++)

        $eggFloor[1][$j] = $j;

  

    // Заполняем остальные записи в

    // таблица с использованием оптимальной подструктуры

    // свойство

    for ($i = 2; $i <= $n; $i++)

    {

        for ($j = 2; $j <= $k; $j++)

        {

            $eggFloor[$i][$j] = 999999;

            for ($x = 1; $x <= $j; $x++)

            {

                $res = 1 + max($eggFloor[$i - 1][$x - 1], 

                                 $eggFloor[$i][$j - $x]);

                if ($res < $eggFloor[$i][$j])

                    $eggFloor[$i][$j] = $res;

            }

        }

    }

  

    // eggFloor [n] [k] содержит результат

    return $eggFloor[$n][$k];

}

  

    // Код драйвера

    $n = 2;

    $k = 36;

    echo "Minimum number of trials in worst case with " .$n. " eggs and "

                                    .$k. " floors is " .eggDrop($n, $k) ;

                                      
// Этот код предоставлен Sam007
?>


Выход :

Minimum number of trials in worst case with 2 eggs and 36 floors is 8

Сложность времени: O (nk ^ 2)
Вспомогательное пространство: O (nk)

В качестве упражнения вы можете попробовать модифицировать вышеуказанное решение DP, чтобы напечатать все промежуточные этажи (этажи используются для минимального пробного решения).

Более эффективное решение : головоломка сбрасывания яиц (биномиальный коэффициент и решение для бинарного поиска)

Пазл с яйцом и 2-мя яйцами
2 яйца и 100 этаж пазл

Ссылки:
http://archive.ite.journal.informs.org/Vol4No1/Sniedovich/index.php

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

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

Пазл с яйцом | DP-11

0.00 (0%) 0 votes