有道经典的算法题,两个一模一样的鸡蛋,某层之上扔鸡蛋就会碎。假如运气最差的话,问要测试多少次才能找出这层楼来。
如果只有一个鸡蛋,我就只能一层一层试验。两个的话关键就是找着第一个鸡蛋试验的位置,第二个鸡蛋还是只能一层一层试验。
这道问题其实可以扩展到任意个鸡蛋,但现在还是只看 2 个鸡蛋的情况。
2 个鸡蛋只有 n 层的最优解求出来假使为 k,那么,n+1 层的时候,把第一个鸡蛋在第 k 层释放,只有两种情况(n+1 只是分解成两个<=n 的子问题,这两个都是已经有解了的):
(1)破碎,于是只有之后就只能遍历从地面到第 k-1 层,一层层遍历,不能偷懒,最坏的情况在此要尝试 k 次;
(2)没碎,那问题
[……]阅读全文