原题如下
一幢 100 层的大楼，给你两个鸡蛋，如果在第 n 层扔下鸡蛋，鸡蛋不碎，那么从第 n-1 层扔鸡蛋，都不碎。这两只鸡蛋一模一样，不碎的话可以扔无数次，且鸡蛋在0层不会碎。设计一种策略能保证可以测出鸡蛋恰好会碎的楼层，且如果该策略是最坏的情况所扔次数最少。
因为我们这样的普通人很少能够像这篇文章（https://www.jianshu.com/p/896cfbca0d3e?utm_campaign=haruki&utm_content=note&utm_medium=reader_share&utm_source=weixin_timeline&from=timeline）里的作者一样，马上反应过来n-1的思路。所以就另外写了一个自己是如何一步步考虑这个问题的过程来帮助理解。
第一步
因为有两个鸡蛋，首先会反应过来的方法是二分法。即从第50层扔下第一个鸡蛋，排除一半的选项。如果碎了就从第1层开始遍历到49层，反之则从51层开始遍历到100层。这种情况下最差是破碎层在第49层或者100，加上扔第一个鸡蛋的那次一共扔了50次（注：第二个鸡蛋扔的实际次数是区间大小-1）。
第二步
观察第一步的思路，发觉二分法虽然可以快速排除一半楼层，但是50这个区间范围仍然过大，造成我们扔第二个鸡蛋的时候最差需要遍历49次。
有没有可能通过第一个鸡蛋多扔几次来缩小检测的范围，这样就降低了第二个鸡蛋需要遍历的楼层数？
受这个问题启发想到了平均分区。设X层为一个区间，则1-100总共包含的区间个数是100/X。假设我们从X层扔第一个鸡蛋，如果不碎就从2X再扔一次，直到在NX层碎了，我们就开始从（N-1）X+1开始遍历到NX，最差需要扔的次数是N（第一个鸡蛋已经扔的次数）+X-1次（破碎楼层就在NX层）。由于N的最大值为100/X，所以平均分区最糟糕的情况是破碎楼层就在100层，问题变成了求X等于多少时100/X+X-1最小。
很容易看出100/X+X-1这个图形在X为正时是一个近似U型的曲线，存在一个极小值。偷懒的算法是目测下是10，然后检验带入9和11，发觉算式结果都比10大，所以10就是最低点。推广到一般情况，正规算法是对100/X+X-1求导然后算-100/X平方+1=0这个算式的解。（导数表示切线斜率，最低点斜率为0），求出X=10
所以我们得到了一个最差19次的解。好像还不错，好过第一步的50了。到此为止所有的解题思路都是正向的。
第三步
最优解牛逼闪闪的动态规划是一种逆向思路，这里用自己的语言解释一遍。
首先，假设存在一个最小的Y，需要控制不管怎么扔总次数必须小于等于Y次。根据第二步我们知道Y由两部分组成：第一个鸡蛋已经扔的次数N和第二个鸡蛋需要遍历的区间-1。为了保证总次数不大于Y次，需要遍历区间大小始终等于Y-N+1（第二个鸡蛋扔Y-N次）。由于N最小取1，最大取Y，所以区间动态变化的范围就为1~Y，总共Y个。
现在这Y个区间加起来需要覆盖到100层，就得出公式1+2+3+....(Y-1)+Y=Y(Y+1)/2=100，最后求出Y=13.90....，向上取14。
验证下小于第二步得出的19，解题完毕。
——————————————————————
最后说句题外话，刘未鹏的《暗时间》是一本非常好的讲认知和学习方法的书，里面关于好题目的定义是“以考察思维方式为目的，并不需要利用到未知的知识”。鸡蛋问题所用的数学知识都是高中的，而大学高数连挂两次的我在工作这么多年后才发觉数学原来是有趣又有用的，认识的大学数学系的同学最后也没有从事数学相关的工作，这不知道是应试教育的失败还是我们自己的遗憾。
网友评论