※ 引述《bleed1979 (十三)》之銘言：
: ※ [本文轉錄自 Soft_Job 看板 #1JI2zrVk ]
: 作者: bleed1979 (十三) 看板: Soft_Job
: 標題: [討論] Google面試問題
: 時間: Sat Apr 12 02:07:46 2014
: 問題：
: 假設你有兩顆蛋，然後有一棟100層樓高的大樓。
: 而蛋的特性有的可能很堅固，堅固到從一百層樓跌下都沒事，
: 有的可能很脆弱，一樓就可以摔破。
: 現在你只知道這這兩顆蛋是完全相同的，
: 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: 問題是：你要摔幾次才能計算出來？
: （如果你低於高度摔下蛋，蛋就沒事，如果高於那個樓層，蛋就完蛋）
: 在這過程你可以摔破蛋。
1)
先建立一個大家應該看得出來的前提
假設第一顆蛋摔破了，而且目前知道第L層不會破，第R層會破
那第二顆蛋就只能從L+1開始一直試到R-1，最壞情況要再試R-L-1次
2)
這題其實可以反過來想，假如你可以摔k次，可以判斷出幾層樓呢
以10次為例，假設最多只能摔10次
那我第一次不能在11樓以上摔，因為假設我在11樓摔破了
之後我就必須要從1試到10，最壞還要再試10次，加上第一次就超過10次
所以第一次最好是在10樓摔，假設摔破了再從1試到9最壞1+9=10次
而假設第一次沒破，那我下一次不能在20樓以上摔
因為如果破了，就必需從11試到19最壞共9次，加上前兩次又超過10次
所以第二次最好是在19樓摔，假設摔破了再從11試到18最壞共2+8=10次
依此類推，若沒破的話第三次可以在19+8=27樓摔，第四次在27+7=34樓摔
第10次就會在55樓摔。
假如到這都還沒破，樓高又超過55，就無法保證在10次內回答出來
因此我們可以歸納出，如果有k次可以用，樓高k(k+1)/2以內可以回答
對於100層樓，我們知道13次不夠用，因為13*14/2 < 100
而14*15/2 >= 100，所以最少的次數是14次
對於n層樓，最少次數就是 k(k-1)/2 < n <= k(k+1)/2 的整數解
要求出closed form的話，可以化成 4k^2-4k+1 < 8n+1 <= 4k^2+4k+1
所以 (2k-1)^2 < 8n+1 <= (2k+1)^2
2k-1 < sqrt(8n+1) <= 2k+1
k-1 < (sqrt(8n+1)-1)/2 <= k
故 k = ceiling((sqrt(8n+1)-1)/2)