本文概述扔鸡蛋问题
以下是对这个著名难题的实例的描述, 该难题涉及n = 2个鸡蛋和k = 36层的建筑物。
假设我们希望知道36层建筑物中的哪个楼层可以安全地放下鸡蛋, 并且哪些会导致鸡蛋在着陆时破裂。我们做一些假设：
…..跌落下来的鸡蛋可以再次使用。
…..破蛋必须丢弃。
…..跌落对所有鸡蛋的影响都是相同的。
…..如果鸡蛋掉落时破裂, 那么如果从较高的地板掉落, 鸡蛋也会破裂。
…..如果鸡蛋在跌落中幸存下来, 那么它在较短的跌落中幸存下来。
…..不能排除一楼的窗户破鸡蛋, 也不可以排除第36层的窗户不会破鸡蛋。
如果只有一个鸡蛋可用, 并且我们希望确保获得正确的结果, 则只能以一种方式进行实验。从一楼的窗户放鸡蛋；如果它仍然存在, 请将其从第二层窗口中放下。继续向上直到破裂。在最坏的情况下, 此方法可能需要丢弃36次。假设有2个鸡蛋。保证在所有情况下都能正常工作的最少的排卵次数是多少？
问题实际上不是找到关键的最低限度, 而只是确定应该从中跌落鸡蛋的最低限度, 以使试验的总数最小化。
资源：动态编程维基
推荐：请在"实践首先, 在继续解决方案之前。
方法1:递归。
在这篇文章中, 我们将讨论解决" n"个鸡蛋和" k"个地板的一般问题的解决方案。解决方案是尝试从每个楼层(从1到k)投下一个鸡蛋, 并递归计算最坏情况下所需的最小投掷次数。在最坏的情况下提供最小值的最低要求将成为解决方案的一部分。
在以下解决方案中, 我们返回最坏情况下的最少试验次数；这些解决方案可以轻松修改, 以打印每个试验的楼层编号。
最坏情况的含义：最坏情况使用户有底限的保证。例如-如果我们有'1'鸡蛋和'k'地板, 我们将从一楼开始放鸡蛋, 直到假设鸡蛋在'kth'地板上破裂为止, 因此为我们提供保证的尝试次数为'k' 。
1)最佳子结构：
当我们从地板x上放一个鸡蛋时, 可能有两种情况(1)鸡蛋破裂(2)鸡蛋没有破裂。

1. 如果鸡蛋从'xth'地板掉落后破裂, 那么我们只需要检查剩余鸡蛋数量低于'x'的地板, 因为某些地板应该存在低于'x'且鸡蛋不会破裂的地板；因此问题减少到x-1层和n-1个鸡蛋。
2. 如果鸡蛋从'xth'地板掉下来后仍未破裂, 则我们只需要检查高于'x'的地板即可；因此问题减少到" k-x"层和n个鸡蛋。

由于我们需要尽量减少最坏的情况下, 我们最多只能考虑两种情况。我们考虑每个楼层的上述两种情况中的最大值, 并选择产生最少试验次数的楼层。

k ==> 楼层数n ==> 鸡蛋数eggDrop(n, k)==> 在最坏情况下找到关键楼层所需的最少试验次数。 eggDrop(n, k)= 1 + min {max(eggDrop(n – 1, x – 1), eggDrop(n, k – x))), 其中x在{1, 2, …, k}}中最坏的情况：例如：让" 2"个鸡蛋和" 2"个地板, 然后-：如果我们尝试从" 1st"地板扔球：最坏情况下的尝试次数= 1 + max(0, 1)0 => 如果鸡蛋从第一层破损, 然后是阈值层(最好的情况)。 1 => 如果鸡蛋没有从第一层破掉, 我们现在将有"?? 2"个鸡蛋和一层要测试的鸡蛋, 其答案将为" 1"。(最坏情况的可能性)我们考虑了最坏情况的可能性, 因此1 + max(0, 1)= 2如果我们尝试从'第二层'投掷：最坏情况下的尝试次数= 1 + max(1, 0)1 => 如果鸡蛋从第二层破损, 那么我们将有1个鸡蛋在1楼找到阈值地板。(最坏情况)0 => 如果鸡蛋没有从第二层摔破, 则为阈值地板。(最好的情况)我们考虑最坏情况的可能性, 因此1 + max(1, 0) = 2。最终答案是分钟(第1楼, 第2楼, 第3楼….., k楼), 所以这里的答案是" 2"。

下面是上述方法的实现：
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 pront 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 pront 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 kmin = 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 = resreturn 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.

输出如下：

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.

复杂度分析：

• 时间复杂度：由于存在子问题重叠的情况, 因此时间复杂度是指数级的。
• 辅助空间：O(1)。由于没有使用任何数据结构来存储值。

由于再次调用了相同的问题, 因此此问题具有"重叠子问题"属性。因此, Egg Dropping Puzzle具有两种属性(请参阅这个和这个)的动态编程问题。像其他典型的动态编程(DP)问题, 可以通过自下而上的方式构造一个临时数组eggFloor [] []来避免相同子问题的重新计算。
方法2:动态编程。
在这种方法中, 我们致力于上述相同的想法忽略了一次又一次地计算子问题答案的情况。。方法是制作一个表, 该表将存储子问题的结果, 以便解决子问题, 只需要从该表中查找即可恒定时间, 之前指数时间.
正式用于填充DP [i] [j]状态, 其中" i"是鸡蛋数, " j"是楼层数：
我们必须从" 1"到" j"遍历每个楼层" x", 并找出最小值：(1 + max(DP [i-1] [j-1], DP [i] [j-x]))。
该模拟将使事情变得清晰：

i => 鸡蛋数j => 楼层数查找最大数量让我们为以下情况填写表格：楼层='4'鸡蛋='2'1 2 3 4 1 2 3 4 => 1 1 2 2 3 => 2对于'egg-1', 每种情况都是基本情况, 因此尝试次数等于下限次数。对于" egg-2", 对于1楼(基本情况), 将尝试" 1"。对于2楼=> 进入1楼1 + max(0, DP [1] [1])进入2楼1 + max(DP [1] [1], 0)DP [2] [2] = min( 1 + max(0, DP [1] [1]), 1 + max(DP [1] [1], 0))对于floor-3 => 进入1楼1 + max(0, DP [2] [ 2])取2楼1 + max(DP [1] [1], DP [2] [1])取3楼1 + max(0, DP [2] [2])DP [2] [3] =最小值("所有三个楼层")= 2对于4楼=> 进入1楼1 + max(0, DP [2] [3])进入2楼1 + max(DP [1] [1], DP [2] [2])进入3楼1 + max(DP [1] [2], DP [2] [1])进入4楼1 + max(0, DP [2] [3])DP [2 ] [4] =分钟("所有四个楼层")= 3

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 entery 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 pront 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 entery 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 pront 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*/

python

# 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 entery 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 pront 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 entery 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 entery 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 ?>

输出：

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

复杂度分析：

• 时间复杂度：O(n * k ^ 2)。
  其中" n"是鸡蛋的数量, " k"是楼层的数量, 因为我们对每个鸡蛋使用嵌套的循环" k ^ 2"次
• 辅助空间：O(n * k)。
  由于大小为" n * k"的二维数组用于存储元素。

作为练习, 你可以尝试修改上述DP解决方案以打印所有中间楼层(用于最小试验解决方案的楼层)。
【算法设计（扔鸡蛋问题 – 动态规划）】更高效的解决方案:鸡蛋掉落之谜(二项式系数和二元搜索解决方案)
2个鸡蛋和K层鸡蛋丢拼图
2个鸡蛋和100个地板拼图
参考文献：
http://archive.ite.journal.informs.org/Vol4No1/Sniedovich/index.php
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  健康码申诉多久有结果
• 

  脑卒中|它比癌症死亡率还高，每21秒就有1人因它死去！预防方法却很简单
• 

  酸枣仁泡水喝正确方法和用量 酸枣仁泡水喝正确方法
• 

  爱普生nx410清零
• 

  2017-2018学年八年级英语教学工作总结
• 

  民国时期的军阀孙传芳是怎么死的
• 

  佳能痰盂镜头 尼康小痰盂镜头半幅
• 

  遇到松下三匹变频空调外机不转怎么办？3个处理方法帮助你
• 

  苹果id锁定是什么意思（苹果ld锁定的意思）
• 

  如何提高文笔和写作能力 怎么提高写作水平
• 

  烧开的艾叶水能连续泡几天吗
• 

  外出烧烤必备烧烤食材清单
• 

  魔域手游9月14日更新内容介绍 全新功能寄售行上线
• 

  舷组词 汉字舷组词
• 

  68531异常指标分析
• 

  这一世，只为你
• 

  梦见打牌赢钱是什么意思
• 

  什么是即席分析,smartview即席分析
• 

  水中毒是怎么引起的
• 

  逃离塔科夫霰弹枪技能效果介绍 霰弹枪技能特效是什么

• 算法设计（金矿问题解析和代码实现）
• Python MongoDB –查找数据用法介绍
• jQuery :最后一个子元素选择器用法介绍
• 人工智能|全连接层的算力计算方式
• 优先队列（priority queue）和堆（heap）详解（二叉堆、d-堆、左式堆、斜堆和二项堆）
• vue filters过滤器的理解和使用
• vue各种属性的意义详细分析
• 运行gulp错误gulp[22202]src node_contextify.cc 626 static void
• 移动端web app开发框架MUI的使用及注意事项