※ 引述《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) --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.123.89 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1398152375.A.C05.html ※ 編輯: johnathan717 (111.243.123.89), 04/22/2014 15:43:03