Rompecabezas de caída de huevos | DP-11

La siguiente es una descripción de la instancia de este famoso rompecabezas que involucra n=2 huevos y un edificio con k=36 pisos.
Supongamos que deseamos saber en qué pisos de un edificio de 36 pisos es seguro dejar caer los huevos y cuáles harán que los huevos se rompan al aterrizar. Hacemos algunas suposiciones:
…..Un huevo que sobrevive a una caída se puede utilizar de nuevo. 
…..Un huevo roto debe ser desechado. 
…..El efecto de una caída es el mismo para todos los huevos. 
…..Si un huevo se rompe cuando se cae, se romperá si se cae desde un piso más alto. 
…..Si un huevo sobrevive a una caída, entonces sobrevivirá a una caída más corta. 
…..No se descarta que las ventanas del primer piso rompan huevos, ni se descarta que las del piso 36 no provoquen que se rompa un huevo.
Si solo se dispone de un huevo y deseamos estar seguros de obtener el resultado correcto, el experimento se puede realizar de una sola manera. Deja caer el huevo desde la ventana del primer piso; si sobrevive, tíralo desde la ventana del segundo piso. Continúe hacia arriba hasta que se rompa. En el peor de los casos, este método puede requerir 36 excrementos. Supongamos que hay 2 huevos disponibles. ¿Cuál es el menor número de excrementos de huevo que se garantiza que funcionará en todos los casos? 
El problema no es en realidad encontrar el piso crítico, sino simplemente decidir los pisos desde los cuales se deben dejar caer los huevos para minimizar el número total de ensayos.
Fuente: Wiki para programación dinámica
 

C++

#include <bits/stdc++.h>
using namespace std;
 
// A utility function to get
// maximum of two integers
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
// Function to get minimum
// number of trials needed in worst
// case with n eggs and k floors
int eggDrop(int n, int k)
{
    // If there are no floors,
    // then no trials needed.
    // OR if there is one floor,
    // one trial needed.
    if (k == 1 || k == 0)
        return k;
 
    // We need k trials for one
    // egg and k floors
    if (n == 1)
        return k;
 
    int min = INT_MAX, x, res;
 
    // Consider all droppings from
    // 1st floor to kth floor and
    // return the minimum of these
    // values plus 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;
}
 
// Driver program to test
// to  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;
}
 
// This code is contributed
// by Akanksha Rai

C

#include <limits.h>
#include <stdio.h>
 
// A utility function to get
// maximum of two integers
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
/* Function to get minimum number of
 trials needed in worst case with n eggs
 and k floors */
int eggDrop(int n, int k)
{
    // If there are no floors, then no
    // trials needed. OR if there is
    // one floor, one trial needed.
    if (k == 1 || k == 0)
        return k;
 
    // We need k trials for one egg and
    // k floors
    if (n == 1)
        return k;
 
    int min = INT_MAX, x, res;
 
    // Consider all droppings from 1st
    // floor to kth floor and
    // return the minimum of these values
    // plus 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;
}
 
/* Driver program to test to  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;
}

Java

public class GFG {
 
    /* Function to get minimum number of
    trials needed in worst case with n
    eggs and k floors */
    static int eggDrop(int n, int k)
    {
        // If there are no floors, then
        // no trials needed. OR if there
        // is one floor, one trial needed.
        if (k == 1 || k == 0)
            return k;
 
        // We need k trials for one egg
        // and k floors
        if (n == 1)
            return k;
 
        int min = Integer.MAX_VALUE;
        int x, res;
 
        // Consider all droppings from
        // 1st floor to kth floor and
        // return the minimum of these
        // values plus 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;
    }
 
    // Driver code
    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));
    }
    // This code is contributed by Ryuga.
}

Python 3

import sys
 
# Function to get minimum number of trials
# needed in worst case with n eggs and k floors
def eggDrop(n, k):
 
    # If there are no floors, then no trials
    # needed. OR if there is one floor, one
    # trial needed.
    if (k == 1 or k == 0):
        return k
 
    # We need k trials for one egg
    # and k floors
    if (n == 1):
        return k
 
    min = sys.maxsize
 
    # Consider all droppings from 1st
    # floor to kth floor and return
    # the minimum of these values plus 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
 
# Driver Code
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))
 
# This code is contributed by ita_c

C#

using System;
 
class GFG {
 
    /* Function to get minimum number of
    trials needed in worst case with n
    eggs and k floors */
    static int eggDrop(int n, int k)
    {
        // If there are no floors, then
        // no trials needed. OR if there
        // is one floor, one trial needed.
        if (k == 1 || k == 0)
            return k;
 
        // We need k trials for one egg
        // and k floors
        if (n == 1)
            return k;
 
        int min = int.MaxValue;
        int x, res;
 
        // Consider all droppings from
        // 1st floor to kth floor and
        // return the minimum of these
        // values plus 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;
    }
 
    // Driver code
    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));
    }
}
 
// This code is contributed by Sam007.

Javascript

<script>
     
    /* Function to get minimum number of 
    trials needed in worst case with n 
    eggs and k floors */
    function eggDrop(n,k)
    {
     
        // If there are no floors, then
        // no trials needed. OR if there
        // is one floor, one trial needed.
        if (k == 1 || k == 0)
            return k;
         
        // We need k trials for one egg
        // and k floors
        if (n == 1)
            return k;
         
        let min = Number.MAX_VALUE;
        let x, res;
         
        // Consider all droppings from
        // 1st floor to kth floor and
        // return the minimum of these
        // values plus 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;
    }
     
    // Driver code
    let n = 2, k = 10;
    document.write("Minimum number of "
                         + "trials in worst case with "
                         + n + " eggs and " + k
                         + " floors is " + eggDrop(n, k));
     
    // This code is contributed by avanitrachhadiya2155
</script>

C++

// A Dynamic Programming based for
// the Egg Dropping Puzzle
#include <bits/stdc++.h>
using namespace std;
 
// A utility function to get
// maximum of two integers
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
/* Function to get minimum
number of trials needed in worst
case with n eggs and k floors */
int eggDrop(int n, int k)
{
    /* A 2D table where entry
    eggFloor[i][j] will represent
    minimum number of trials needed for
    i eggs and j floors. */
    int eggFloor[n + 1][k + 1];
    int res;
    int i, j, x;
 
    // We need one trial for one floor and 0
    // trials for 0 floors
    for (i = 1; i <= n; i++) {
        eggFloor[i][1] = 1;
        eggFloor[i][0] = 0;
    }
 
    // We always need j trials for one egg
    // and j floors.
    for (j = 1; j <= k; j++)
        eggFloor[1][j] = j;
 
    // Fill rest of the entries in table using
    // optimal substructure property
    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] holds the result
    return eggFloor[n][k];
}
 
/* Driver program to test to printDups*/
int main()
{
    int n = 2, k = 36;
    cout << "\nMinimum number of trials "
        "in worst case with " << n<< " eggs and "<< k<<
        " floors is "<< eggDrop(n, k);
    return 0;
}
 
// this code is contributed by shivanisinghss2110

C

// A Dynamic Programming based for
// the Egg Dropping Puzzle
#include <limits.h>
#include <stdio.h>
 
// A utility function to get
// maximum of two integers
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
/* Function to get minimum
number of trials needed in worst
case with n eggs and k floors */
int eggDrop(int n, int k)
{
    /* A 2D table where entry
    eggFloor[i][j] will represent
    minimum number of trials needed for
    i eggs and j floors. */
    int eggFloor[n + 1][k + 1];
    int res;
    int i, j, x;
 
    // We need one trial for one floor and 0
    // trials for 0 floors
    for (i = 1; i <= n; i++) {
        eggFloor[i][1] = 1;
        eggFloor[i][0] = 0;
    }
 
    // We always need j trials for one egg
    // and j floors.
    for (j = 1; j <= k; j++)
        eggFloor[1][j] = j;
 
    // Fill rest of the entries in table using
    // optimal substructure property
    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] holds the result
    return eggFloor[n][k];
}
 
/* Driver program to test to 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

// A Dynamic Programming based Java
// Program for the Egg Dropping Puzzle
class EggDrop {
 
    // A utility function to get
    // maximum of two integers
    static int max(int a, int b)
    {
        return (a > b) ? a : b;
    }
 
    /* Function to get minimum number
 of trials needed in worst
    case with n eggs and k floors */
    static int eggDrop(int n, int k)
    {
        /* A 2D table where entry eggFloor[i][j]
 will represent minimum number of trials
needed for i eggs and j floors. */
        int eggFloor[][] = new int[n + 1][k + 1];
        int res;
        int i, j, x;
 
        // We need one trial for one floor and
        // 0 trials for 0 floors
        for (i = 1; i <= n; i++) {
            eggFloor[i][1] = 1;
            eggFloor[i][0] = 0;
        }
 
        // We always need j trials for one egg
        // and j floors.
        for (j = 1; j <= k; j++)
            eggFloor[1][j] = j;
 
        // Fill rest of the entries in table using
        // optimal substructure property
        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] holds the result
        return eggFloor[n][k];
    }
 
    /* Driver program to test to 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));
    }
}
/*This code is contributed by Rajat Mishra*/

Python3

# A Dynamic Programming based Python Program for the Egg Dropping Puzzle
INT_MAX = 32767
 
# Function to get minimum number of trials needed in worst
# case with n eggs and k floors
def eggDrop(n, k):
    # A 2D table where entry eggFloor[i][j] will represent minimum
    # number of trials needed for i eggs and j floors.
    eggFloor = [[0 for x in range(k + 1)] for x in range(n + 1)]
 
    # We need one trial for one floor and0 trials for 0 floors
    for i in range(1, n + 1):
        eggFloor[i][1] = 1
        eggFloor[i][0] = 0
 
    # We always need j trials for one egg and j floors.
    for j in range(1, k + 1):
        eggFloor[1][j] = j
 
    # Fill rest of the entries in table using optimal substructure
    # property
    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] holds the result
    return eggFloor[n][k]
 
# Driver program to test to print 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)))
 
# This code is contributed by Bhavya Jain

C#

// A Dynamic Programming based C# Program
// for the Egg Dropping Puzzle
using System;
 
class GFG {
 
    // A utility function to get maximum of
    // two integers
    static int max(int a, int b)
    {
        return (a > b) ? a : b;
    }
 
    /* Function to get minimum number of
    trials needed in worst case with n
    eggs and k floors */
    static int eggDrop(int n, int k)
    {
 
        /* A 2D table where entry eggFloor[i][j]
        will represent minimum number of trials
        needed for i eggs and j floors. */
        int[, ] eggFloor = new int[n + 1, k + 1];
        int res;
        int i, j, x;
 
        // We need one trial for one floor and0
        // trials for 0 floors
        for (i = 1; i <= n; i++) {
            eggFloor[i, 1] = 1;
            eggFloor[i, 0] = 0;
        }
 
        // We always need j trials for one egg
        // and j floors.
        for (j = 1; j <= k; j++)
            eggFloor[1, j] = j;
 
        // Fill rest of the entries in table
        // using optimal substructure property
        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] holds the result
        return eggFloor[n, k];
    }
 
    // Driver function
    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));
    }
}
 
// This code is contributed by Sam007.

PHP

<?php
// A Dynamic Programming based PHP
// Program for the Egg Dropping Puzzle
 
/* Function to get minimum number
   of trials needed in worst
   case with n eggs and k floors */
function eggDrop($n, $k)
{
     
    /* A 2D table where entry eggFloor[i][j]
       will represent minimum number of
       trials needed for i eggs and j floors. */
    $eggFloor = array(array());;
     
    // We need one trial for one
    // floor and0 trials for 0 floors
    for ($i = 1; $i <=$n;$i++)
    {
        $eggFloor[$i][1] = 1;
        $eggFloor[$i][0] = 0;
    }
 
    // We always need j trials
    // for one egg and j floors.
    for ($j = 1; $j <= $k; $j++)
        $eggFloor[1][$j] = $j;
 
    // Fill rest of the entries in
    // table using optimal substructure
    // property
    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] holds the result
    return $eggFloor[$n][$k];
}
 
    // Driver Code
    $n = 2;
    $k = 36;
    echo "Minimum number of trials in worst case with " .$n. " eggs and "
                                    .$k. " floors is " .eggDrop($n, $k) ;
                                     
// This code is contributed by Sam007
?>

Javascript

<script>
 
// A Dynamic Programming based Javascript
// Program for the Egg Dropping Puzzle
 
// A utility function to get
    // maximum of two integers
function max(a,b)
{
    return (a > b) ? a : b;
}
 
/* Function to get minimum number
 of trials needed in worst
    case with n eggs and k floors */
function eggDrop(n,k)
{
    /* A 2D table where entry eggFloor[i][j]
 will represent minimum number of trials
needed for i eggs and j floors. */
        let eggFloor = new Array(n + 1);
        for(let i=0;i<(n+1);i++)
        {
            eggFloor[i]=new Array(k+1);
        }
        let res;
        let i, j, x;
  
        // We need one trial for one floor and
        // 0 trials for 0 floors
        for (i = 1; i <= n; i++) {
            eggFloor[i][1] = 1;
            eggFloor[i][0] = 0;
        }
  
        // We always need j trials for one egg
        // and j floors.
        for (j = 1; j <= k; j++)
            eggFloor[1][j] = j;
  
        // Fill rest of the entries in table using
        // optimal substructure property
        for (i = 2; i <= n; i++) {
            for (j = 2; j <= k; j++) {
                eggFloor[i][j] = Number.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] holds the result
        return eggFloor[n][k];
}
 
/* Driver program to test to printDups*/
let n = 2, k = 36;
document.write("Minimum number of trials in worst"
                           + " case with "
                           + n + "  eggs and "
                           + k + " floors is " + eggDrop(n, k));
     
 
 
// This code is contributed by ab2127
 
</script>

C++

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
 
vector<vector<int>> memo(MAX, vector<int> (MAX, -1));
int solveEggDrop(int n, int k) {
  
    if(memo[n][k] != -1) { return memo[n][k];}
     
    if (k == 1 || k == 0)
      return k;
 
    if (n == 1)
      return k;
 
    int min = INT_MAX, x, res;
 
    for (x = 1; x <= k; x++) {
      res = max(
        solveEggDrop(n - 1, x - 1),
        solveEggDrop(n, k - x));
      if (res < min)
        min = res;
    }
     
    memo[n][k] = min+1;
    return min + 1;
  }
 
int main() {
 
    int n = 2, k = 36;
    cout<<solveEggDrop(n, k);
    return 0;
}
 
// contributed by Shivam Agrawal(shivamagrawal3)

C

#include <stdio.h>
#include<limits.h>
#include<string.h>
#define MAX 1000
 
int memo[MAX][MAX];
int solveEggDrop(int n, int k) {
  
    if(memo[n][k] != -1) { return memo[n][k];}
     
    if (k == 1 || k == 0)
      return k;
 
    if (n == 1)
      return k;
 
    int min = INT_MAX, x, res;
 
    for (x = 1; x <= k; x++) {
      int a = solveEggDrop(n - 1, x - 1);
      int b = solveEggDrop(n, k - x);
      res = a>b?a:b;
      if (res < min)
        min = res;
    }
     
    memo[n][k] = min+1;
    return min + 1;
  }
 
int main() {
    memset( memo, -1,MAX * MAX * sizeof( int ) );
    int n = 2, k = 36;
    printf("%d",solveEggDrop(n, k));
    return 0;
}
 
// This code is contributed by repakaeswaripriya.

Java

import java.util.Arrays;
 
class GFG {
    static final int MAX = 1000;
 
    static int[][] memo = new int[MAX][MAX];
 
    static int solveEggDrop(int n, int k)
    {
 
        if (memo[n][k] != -1) {
            return memo[n][k];
        }
 
        if (k == 1 || k == 0)
            return k;
 
        if (n == 1)
            return k;
 
        int min = Integer.MAX_VALUE, x, res;
 
        for (x = 1; x <= k; x++) {
            res = Math.max(solveEggDrop(n - 1, x - 1),
                           solveEggDrop(n, k - x));
            if (res < min)
                min = res;
        }
 
        memo[n][k] = min + 1;
        return min + 1;
    }
 
    public static void main(String[] args)
    {
        for (int i = 0; i < memo.length; i++)
            Arrays.fill(memo[i], -1);
        int n = 2, k = 36;
        System.out.print(solveEggDrop(n, k));
    }
}
 
// This code IS contributed by umadevi9616

Python3

import sys
 
MAX = 1000;
 
memo = [[-1 for i in range(MAX)] for j in range(MAX)] ;
 
def solveEggDrop(n, k):
 
    if (memo[n][k] != -1):
        return memo[n][k];
     
    if (k == 1 or k == 0):
        return k;
 
    if (n == 1):
        return k;
 
    min = sys.maxsize;
    res = 0;
 
    for x in range(1,k+1):
        res = max(solveEggDrop(n - 1, x - 1), solveEggDrop(n, k - x));
        if (res < min):
            min = res;
     
 
    memo[n][k] = min + 1;
    return min + 1;
 
# Driver code
if __name__ == '__main__':
    n = 2;
    k = 36;
    print(solveEggDrop(n, k));
     
# This code is contributed by gauravrajput1

C#

using System;
 
public class GFG {
    static readonly int MAX = 1000;
 
    static int[,] memo = new int[MAX,MAX];
 
    static int solveEggDrop(int n, int k)
    {
 
        if (memo[n,k] != -1) {
            return memo[n,k];
        }
 
        if (k == 1 || k == 0)
            return k;
 
        if (n == 1)
            return k;
 
        int min = int.MaxValue, x, res;
 
        for (x = 1; x <= k; x++) {
            res = Math.Max(solveEggDrop(n - 1, x - 1),
                           solveEggDrop(n, k - x));
            if (res < min)
                min = res;
        }
 
        memo[n,k] = min + 1;
        return min + 1;
    }
 
    public static void Main(String[] args)
    {
        for (int i = 0; i < memo.GetLength(0); i++)
            for(int j =0;j<memo.GetLength(1);j++)
                memo[i,j] = -1;
        int n = 2, k = 36;
        Console.Write(solveEggDrop(n, k));
    }
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
var MAX = 1000;
 
     var memo = Array(MAX).fill().map(()=>Array(MAX).fill(-1));
 
    function solveEggDrop(n , k)
    {
 
        if (memo[n][k] != -1) {
            return memo[n][k];
        }
 
        if (k == 1 || k == 0)
            return k;
 
        if (n == 1)
            return k;
 
        var min = Number.MAX_VALUE, x, res;
 
        for (x = 1; x <= k; x++) {
            res = Math.max(solveEggDrop(n - 1, x - 1),
                           solveEggDrop(n, k - x));
            if (res < min)
                min = res;
        }
 
        memo[n][k] = min + 1;
        return min + 1;
    }
 
        var n = 2, k = 36;
        document.write(solveEggDrop(n, k));
 
// This code is contributed by gauravrajput1
</script>

C++

// C++ program to find minimum number of trials in worst
// case.
#include <bits/stdc++.h>
using namespace std;
 
int minTrials(int n, int k)
{
   // Initialize 2D of size (k+1) * (n+1).
   vector<vector<int> > dp(k + 1, vector<int>(n + 1, 0));
   int m = 0; // Number of moves
   while (dp[m][n] < k) {
       m++;
       for (int x = 1; x <= n; x++) {
           dp[m][x] = 1 + dp[m - 1][x - 1] + dp[m - 1][x];
       }
   }
   return m;
}
 
/* Driver code*/
int main()
{
   cout << minTrials(2, 10);
   return 0;
}
 
// This code is contributed by Arihant Jain (arihantjain01)

C++

// C++ program to find minimum number of trials in worst
// case.
#include <bits/stdc++.h>
using namespace std;
 
int minTrials(int n, int k)
{
   // Initialize array of size (n+1) and m as moves.
   int dp[n + 1] = { 0 }, m;
   for (m = 0; dp[n] < k; m++) {
       for (int x = n; x > 0; x--) {
           dp[x] += 1 + dp[x - 1];
       }
   }
   return m;
}
 
/* Driver code*/
int main()
{
   cout << minTrials(2, 10);
   return 0;
}
 
// This code is contributed by Arihant Jain (arihantjain01)

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *