Re: [討論] Google面試問題

[johnathan717 (好神公仔)]

※ 引述《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://www.ptt.cc/bbs/Prob_Solve/M.1398152375.A.C05.html
※ 編輯: johnathan717 (111.243.123.89), 04/22/2014 15:43:03
推 DJWS:謝謝!
推 EdisonX:抱歉，關於第一點借問一下，假設第 10 樓破了，接下來是
→ EdisonX:否試 2.4.6.8 樓即可？在6破就代表只到5.worst case 當然
→ EdisonX:還是一樣就是了..
→ johnathan717:在6破你就不知道5會不會破啊，那答案可能是4或5
推 EdisonX:疑！是我腦頓了！抱歉
推 mob5566:原來可以這樣想!!