標題

Re: [討論] Google面試問題

(31/31篇)看板Prob_Solve板作者johnathan717 (好神公仔)推文7則 (4推 0噓 3→)
※ 引述《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)--
※ 發信站: 批踢踢實業坊(pttweb.tw), 來自: 111.243.123.89
※ 文章網址: https://pttweb.tw/Prob_Solve/M.1398152375.A.C05
※ 編輯: johnathan717 (111.243.123.89), 04/22/2014 15:43:03