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