王国维在《人间词话》中道出了三个境界：
一境：昨夜西风凋碧树。独上高楼，望尽天涯路。
二境：衣带渐宽终不悔，为伊消得人憔悴。
三境：众里寻他千百度。蓦然回首，那人却在灯火阑珊处。
唐诗宋词元曲清小说，余独爱宋词，因其不拘一格，随性洒脱是也。三句也毫不例外的属于宋词。分别是北宋晏殊《蝶恋花·槛菊愁烟兰泣露》、北宋柳永《蝶恋花·伫倚危楼风细细》、南宋辛弃疾《青玉案·元夕》。如果用三个字来总结三个境界的话，就是“立”， “守”， “得”。
立：当解为高处不胜寒，目标明确，无杂念；
守：应该是在追求真理的道路上寻寻觅觅，孜孜不倦；
得：就该是得道之后，黎明的曙光驱散黑暗，豁然开朗的那一瞬了吧。
回到扔鸡蛋的话题上来，这是程序员面试中的一道经典面试，先看一下问题的详细描述:
[一幢 100 层的大楼,给你两个鸡蛋. 假设在第 n 层扔下鸡蛋,鸡蛋不碎,那么从前 n-1 层扔鸡蛋都不碎.这两个鸡蛋一模一样,不碎的话能够扔无数次. 提出一个策略, 要保证能測出鸡蛋恰好不会碎的楼层, 并使此策略在最坏情况下所扔次数最少]
[鸡蛋做自由落体运动，脑补物理公式：h=1/2*g*t^2。v=g*t。吧啦吧啦，其实这些一点儿用也没有。并且，你如果想到这里，你就跑偏了，距离出局也就不远了。还有就是你如果觉得就凭一个鸡蛋，一米都会摔碎，一层楼至少三米高，而直接得出问题答案：问题不现实。那咱们别玩了，再见 !]。
回归正题，我们先来分析一下问题，有一些前提我们需要知道：
鸡蛋没有被摔碎，可以继续重复使用，如果摔碎了，则不能重复使用；
有可能在一层就摔碎，也有可能在100层都摔不碎；
可以摔碎两个鸡蛋，只要能确定最高不会被摔碎的楼层。
有了这些前提条件，我们就可以分析问题了。[当然，你可以先自己思考一下，再继续往下看... ... ]
其实接下来我想把这个问题给非计算机或者数学专业的人讲清楚，所以会从简至繁/循序渐进的思路对这个问题进行分析，当然，也是参考了网络上各位大神的分析，有了自己的理解。本人水平有限，难免有错，欢迎指正。
正文
从原始问题的需求来看，我们的目的就是为了得到一个鸡蛋不会被摔碎的最高层数（下文称为临界层）。至于要求的最少实验次数，这属于优化问题，可以暂且不管，先看原始问题如何解决，这样做的目的可以让我们一开始就能够专注于问题本身，不至于直接陷入最优解的困扰中而忘记了初衷。
于是，我们独上高楼，因为站在最高的地方，才能排除下面的乌烟瘴气的影响，才能看得清，看得远，看的到自己想要的东西。
昨夜西风凋碧树。独上高楼，望尽天涯路。
为了得到不摔碎的最高层数，最简单明了办法就是从第一层开始测试扔鸡蛋，逐级增加层数，直到摔碎的层数N，那么临界层就是N-1。
这样的话，只需要一颗鸡蛋就可以找到临界层。这种情况下，最差情况就是要测试100次才能得到正确结果（直到第100层才摔碎或着1-100层都没有摔碎）。
无论如何，最初级的解决方案已经有了：从第一层开始，逐级增加层数测试。那么接下来就是如何去根据现有条件继续优化我们的最差情况下需要的次数。
天涯路已望尽，那接下来就是如何最快的上路了。极目远眺后，发现可以抄个近路，因此，整理行装，收拾细软，拍马前行了。
衣带渐宽终不悔，为伊消得人憔悴。
既然给了两颗鸡蛋，那么就要充分利用两颗鸡蛋。在计算机系统中最常见的算法就是二分法，也是最容易理解的一种算法。下面就使用两颗鸡蛋和二分法来对以上结果进行一下优化。
二分法，顾名思义，就是将规模为n的问题通过O(1)操作变为规模为n/2的问题，时间复杂度是 O(logN)。在本问题中，就是将100的规模先经过一次操作将问题变为50的规模。
对于本问题，应用二分法，就可以直接从第50层开始扔鸡蛋。鸡蛋碎或者不碎都可以将问题规模缩小到0-50或者51-100。假如我们在第50层扔下了第一颗鸡蛋，只有两种情况：碎或不碎。如果蛋碎了，那么临界层应该在1-50之间，接下来用另一个蛋，从1到50逐级测试，直到第二颗蛋也碎掉或者到了第49层也没有碎，那49就是临界层；如果第50层没有碎，那么继续测试第75层，同理，继续。这样最坏情况就50层碎掉，49层是临界层的情况，需要测试50次。因为第一颗鸡蛋在第50层碎掉之后，第二颗鸡蛋只能从第一层开始逐级往上测试，最差情况就是测试到第49层也没有碎或者碎了，才能确定临界层，这样第一颗鸡蛋测试的1次加上第二颗鸡蛋测试的49次，就是50次。
此时，二分法的优化结果就是在最差情况下比第一种方法减少了一半，变成了50次。到这里，我们其实可以知道，可用的鸡蛋越多，效果会越好，推广开来也就是n分法了，原理相同。当然，二分法仍然达不到我们的要求，测量的粒度还是太大了，最后一个鸡蛋逐级测试大方法其实与原始方法并无太大差别。所以还是有可以优化的空间的。
其实到了二分法，距离真理更近了一些了。二分法在思路上给我们开拓了疆域。接下来就是将问题转化为另一种思想：动态规划。
众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
动态规划算法一般适用于最优子结构和重叠子问题性质的问题。这两个性质通俗一些讲就是整个问题需要解其不同部分（即子问题），再合并各个部分的解最终得到原问题的解。
对应到扔鸡蛋问题，我们可以这样考虑：假如我们从第n层扔下，鸡蛋没有碎，那么原始【1-100】的问题，就变成了【n-100】的问题了，因为小于n层鸡蛋肯定不会碎。这样【n-100】就是【1-100】的一个子问题，这个子问题的解再加上第一次尝试的一次，合并起来的答案就是整个问题的解。
我们用F(n)表示n层楼最差情况需要的测试次数，假设从第 i 层开始扔鸡蛋，那么我们有以下分析:
如果，第 i 层碎掉了，这是最糟糕的情况了，因为只能用剩下的另一颗鸡蛋从第一层到第 i-1 层去尝试，这时候的最差次数是 1 + (i-1) 。
如果，第i层没有碎掉，那么我们除了用掉一次测试次数外，一颗鸡蛋都没有碎，问题就变成了两颗鸡蛋测试第i+1到n层最差情况下的需要的测试次数了，也就是F(n-i)。所以，这种情况下的最差次数就是 1 + F(n-i)。
对于以上两种情况，我们取最大值，就是F(n)的临界值。即：F(n) = 1 + Max(i-1，F(n-i))。
于是，我们得到了当从第i层扔鸡蛋的时候的F(n)的取值，也就是最差情况下的次数。所以，我们尝试完所有的 i 值(1<= i <=100)的最差情况下的最大次数，然后取最小值对应的 i 值，就是原始问题的最优解了。
最后的公式就变成了：F(n) = Min(1 + Max(i - 1, F(n-i)))
对应于100层的高楼，扔鸡蛋问题的解就成了：
F(100) = Min(1 + Max(i - 1, F(100-i)))
最终结果是14层，也就是最坏情况的尝试次数是14次，可以找到临界层。
【验证】
当从14层开始测试的时候，最坏情况下当然就是14层碎掉了，然后从第一层开始尝试到13层，一共14次。
14层没有碎的情况比较多，只列举100层是临界层的情况，那么所尝试的楼层数列举出来就是：14,27, 39, 50,60,69,77, 84,90,95,99,100 。一共12次，小于14次。其他情况也是小于14次的，因此，14是最终结果啦！
最后附上暴力破解的代码[暂不考虑代码优化]
#include <stdio.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
int fun ( int layer )
{
if ( layer <= 0 )
{
return 0;
}
if ( layer == 1 )
{
return 1;
}
int min = layer;
int temp;
for ( int i = 1; i <= layer; i++ )
{
temp = 1 + MAX(i-1, fun( layer - i ) );
if( min > temp )
min = temp;
}
return min;
}
int main()
{
int layer = 100;
printf("%d",fun(layer));
return 0;
}
[友情提示：不要尝试用低配计算机跑这段程序，我相信计算机可能不会崩溃，但你一定会崩溃！]
更多有趣文章学习，可关注公众号【木石说：mushiwords】
拨云见日
文/yycaptain
网友评论