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.
Suponga 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 volver a utilizar.
…..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
Solución de programación dinámica
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.
Minimum number of trials in worst case with 2 eggs and 36floors is 8
Consulte el artículo completo sobre Rompecabezas para dejar caer huevos | DP-11 para más detalles!
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