100层楼，扔两个鸡蛋，寻找使鸡蛋摔碎的楼层最快要扔多少次？

解释：两个鸡蛋一样，只有在达到某个楼层高度时，才会摔碎。可以假设这个摔碎临界楼层是N。

• 最笨的方法:只用一个鸡蛋遍历——N次尝试
  • 一个鸡蛋遍历那就是从一楼顶开始，逐层尝试，如果摔不碎那就继续往上层尝试，直到N层摔碎了。这样就尝试了N次，而且浪费了一个鸡蛋的使用。
• 二分查找——两个鸡蛋，鸡蛋A用来二分尝试，鸡蛋B用来在A摔碎后做局部遍历尝试
  • 鸡蛋A用来做二分尝试，即第一次从50层扔下。
  • 最悲观情况，直接摔碎，说明N在1-50之间，那么鸡蛋B也只能从1开始遍历，回到了第一种情况（最多尝试次数也是N）。
  • 乐观情况，鸡蛋A没摔碎，接下来就可以尝试从75层扔下，碎了那就是N在51-74之间了。尝试次数为1+1+（74-51）=25次。
  • 更乐观情况，鸡蛋A在75层也没碎，接下来可以在87层扔下；A碎了则N在76-86之间，故是需要1+1+1+（86-76）=13次。
  • A没碎，接下来在93层扔下；A碎了则N在88-92之间，故需要扔1+1+1+1+（92-88）=8次。
  • A没碎，接下来在96层扔下；A碎了则N在94-95之间，故需要扔1+1+1+1+1+（95-94）=6次。
  • A没碎，接下来在98层扔下；A碎了则N在97-98，故需要扔1+1+1+1+1+1=6次。
  • A没碎，则A在99-100之间，如需要扔6+1=7次。
• 可见，用二分法结果很不稳定，特别是N小于50时最糟糕（甚至会比第一种直接遍历的还要多一次）。N越大越好找，需要尝试的次数越少。
  如果这个题目换成鸡蛋个数不限制，那就是用二分法最快了。
• 平均分割楼层法——假设总共扔X次，其中鸡蛋A扔了X1次，鸡蛋B扔了X2次
  • X=X1+X2
  • 鸡蛋A用来做楼层平均分割，大步尝试；鸡蛋B作为每一小部分的遍历小步尝试。
  • 假设将100层平均分为10部分，即鸡蛋A分别在第10、20、30、40、50、60、70、80、90、100层扔；则鸡蛋B在A摔碎后在细分的那个楼层小步遍历寻找即可。如此的平均尝试次数又要比二分查找更好。
  • 但问题是如何找到最优的平均分割n段，X1=n，X2=100/n。X=n+100/n，可见n平方=100即n等于10时，X=20。
  • 若能在后面每一段更准确地分析出应该分的楼层数（如图2），而不是平均10层一段（如图1），会有更优的效果。下一个方法就是这样。
• 假设法——假设最多允许尝试X次，问能尝试到的最高的楼层。
  • 第1次从X楼扔下来。因为即使摔坏了，也可以用另一个鸡蛋遍历X-1次找到该楼层。
  • 第2次（还剩X-1次尝试次数）可以从X+(X-1)层扔下来。因为即使摔碎了，也可以用另一个鸡蛋遍历X-1-1次找到该楼层。
  • 同理，第3次，可以从X+(X-1)+(X-2)层扔下来。
  • 第X次。可以从第X+(X-1)+(X-2)+...+(X-(X-2))+1层扔下来，这就是最高可能尝试到的楼层X*(X+1)/2，下面所有的楼层都可以在X次尝试中到达。
  • 当最高楼层为100时，可列出不等式：最高可能尝试到的楼层X(X+1)/2 > 100，解出X=14次。这就是最稳定的最快寻找到该楼层的扔鸡蛋次数。也就是说第一次扔鸡蛋要从14楼开始扔。14+13+12+11+...+2+1 = 105层，也就是14次尝试一定可以在1-105层中找到那个第N层。推出了公式X(X+1)/2后，要想编程求任意总楼层条件下，就都很方便了。

100层楼，K次机会.jpg

• 动态规划法——找最优解常用方法

在我们编程解决问题的过程中，如果遇到最优问题的时候，往往可以先尝试一下动态规划的方法。而动态规划的方法，首要的我们要找到构成这个最优问题的最优子问题。所以，下面的分析，我们首先尝试动态规划的方法，如何解决这个问题，这也是典型的程序员的思路；其次，在众多的问题当中，有不少可以直接归结为数学方程式，如果我们能够写出数学方程式，那么，答案将是更加的简洁、美妙（比如上一种方法推导出来的公式）。

• 基于动态规划的方法

  • 前面提到，若要采用动态规划的方法，最重要的是要找到子问题。做如下面的分析，假设F{n}表示从第n层楼扔下鸡蛋，找到不摔碎鸡蛋楼层的最少尝试次数。第一个鸡蛋可能从第i层扔下，有两个情况：
  • 碎了，第二个鸡蛋，需要从第一层开始试验，最多要尝试i-1次。
  • 没碎，两个鸡蛋，还有n-i层。这个就是子问题了f[n-i] 。

• 所以，当第一个鸡蛋，由第i个位置落下的时候，要尝试的次数为f[i]= 1 + max(i - 1, f[n-i])用max是确保一定可以在这么多次内找到。那么对于每一个i对f(i)进行比较，非最小的f(i)，就是F{n}的值。状态转移方程如下： F{n} = min f[i] = min(1 + max(i - 1, f[n-i]) ) 其中: i的范围为(1, n), f[1] = 1 完毕。

• 推广动态规划的方法，可以推广为n层楼，m个鸡蛋。如下分析： 假设f{n,m}表示n层楼、m个鸡蛋时找到最高楼层的最少尝试次数。当第一个鸡蛋从第i层扔下，如果碎了，还剩m-1个鸡蛋，为确定下面楼层中的安全楼层，还需要f{i-1,m-1}次，找到子问题；不碎的话，上面还有n-i层，还需要f[n-i,m]次，又一个子问题。 状态转移方程如下： f{n, m} = min(1 + max(f{i - 1, m - 1}, f{n - i, m}) ) 其中： i为(1, n), f{i, 1} = 1

• 拓展一下，如果不是100楼层，是N楼层，曾怎么计算呢？

  
  N层楼K次机会.png

• 再次拓展，如果我们有三个鸡蛋，有k次机会，我们最大可以测试多少层楼？

  
  三个鸡蛋.jpg

• 如果我们有M个鸡蛋，有k次机会，我们最大可以测试多少层楼？