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