※ [本文轉錄自 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)的方法？