※ [本文转录自 Soft_Job 看板 #1JI2zrVk ]
作者: bleed1979 (十三) 看板: Soft_Job
标题: [讨论] Google面试问题
时间: Sat Apr 12 02:07:46 2014
问题：
假设你有两颗蛋，然后有一栋100层楼高的大楼。
而蛋的特性有的可能很坚固，坚固到从一百层楼跌下都没事，
有的可能很脆弱，一楼就可以摔破。
现在你只知道这这两颗蛋是完全相同的，
你想要知道蛋最高从哪一层楼摔下来不会摔破。
问题是：你要摔几次才能计算出来？
（如果你低于高度摔下蛋，蛋就没事，如果高于那个楼层，蛋就完蛋）
在这过程你可以摔破蛋。

其实有比二分法更好的答案...提示: 那个 50 其实很容易变小沿着这个变小的思路就会得到最佳解了

期望值应该都是51次想想开方根好像比较正确:19次

我的策略跟楼上一样@@ 但是听说有更小的@_@

14次 f(0)=0 f(n)=max(j-1,f(i-j))+1, 1<=j<=nf(n)=min(max(j-1,f(i-j))+1), 1<=j<=n 这样才对QQn 一直打错

10次破1颗后step可以是2不对 我错了= =

看wikipedia的dynamic programming里面就有解答了..

想请教有没有O(n)的方法，甚至是低于O(n)的方法？