Re: [討論] Google面試問題

[bndan (seed)]

※ 引述《bleed1979 (十三)》之銘言：
: 問題：
: 假設你有兩顆蛋，然後有一棟100層樓高的大樓。
: 而蛋的特性有的可能很堅固，堅固到從一百層樓跌下都沒事，
: 有的可能很脆弱，一樓就可以摔破。
: 現在你只知道這這兩顆蛋是完全相同的，
: 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: 問題是：你要摔幾次才能計算出來？
: （如果你低於高度摔下蛋，蛋就沒事，如果高於那個樓層，蛋就完蛋）
: 在這過程你可以摔破蛋。

手癢回文,其他恕刪...

以下為凡人解(離題?)...XD

純暴力解 => 從1樓開始一路丟到100樓

最糟 => 100次
最佳 => 1次

"如果假設每層樓出現的機率一致."

那平均為 (1+2+3+4+....+100) / 100 => (101/2)次

這平均測試數字太大,所以來個分組優化...

分組優化最高可能 => N^(1/2) = 10

所以分10組 每組10個

分組後的測試方法很簡單...一樣是玩暴力解

從底慢慢往上..

但差別在於先丟 10,20,30,40,50,60,70,80,90,100樓

第一顆如果在10樓壞掉,就測1~9 (假設一樓也要丟吧 = =)

第一顆如果在20樓壞掉,就測11~19

以此類推~

所以各測試次數為 第一顆測試次數 + 第二測試次數

也就是如果是11樓破與不破的分界點

那需要測試 2 + 2 次
  (丟10,20樓) (丟11,12樓)

可推論=>

最糟=19次
最佳=2次

"同暴力解,假設每樓出現機率一致"

平均為:

R=第一顆丟的次數 (分別為 1~10)

(R+1)+(R+2)+(R+3)....+(R+9) 為各組總合測試次數

因此單組為 10R+(1+2+~~~~+9) = 10R + 45

總合(共10組) => (10+45) + (20+45) + .... + (100+45)

平均 => (550 + 450) /100 = 10次

所以以此解法 可以將暴力解的平均次數縮減到10次..

優化後比較:

最糟: 100=> 19 (O)
最佳: 1=> 2    (X)
平均: 55=> 10  (O)

所以優化成立 XD....

PS:

暴力解基本的骨質就不好,套上優化要再往上應該會有所困難 XD

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 211.75.130.241
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1397301641.A.7FD.html
※ 編輯: bndan (211.75.130.241), 04/12/2014 19:22:14
→ musie:我是考官會問為什麼不是20,40,60,80 為什麼不是33,66,99
→ musie:這段邏輯也要寫出來..
→ bndan:分兩層 所以開更號 三層就開三方 以此類推 不寫出來是因為這
→ bndan:是非常基礎的東西 @@
→ jengjye:假設每層出現的機率一致是假命題,分層也是
→ bndan:特別標記當然是"補足"命題...換言之 這也是叫凡人解原因 :)
→ bndan:另外分層的部份是依照 他給的條件下去算 這只是普通優化手續
→ bndan:補充:分兩層之意是只有兩顆蛋 換言之有三顆可以分三層 以此
→ bndan:推.當層數越多 最佳會越來越爛 最遭會越來越趨向平均 這是基
→ bndan:本演算法(大學部)的東西...這東西是假命題? 這應該是誤會喔
→ jengjye:不...恕在下直言你會這樣解代表你根本沒看清楚題目
→ jengjye:在下認為看清楚題目才是解決問題的第一要件