Re: [討論] Google面試問題
※ 引述《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
→
04/12 19:32, , 1F
04/12 19:32, 1F
→
04/12 19:32, , 2F
04/12 19:32, 2F
→
04/13 10:36, , 3F
04/13 10:36, 3F
→
04/13 10:36, , 4F
04/13 10:36, 4F
→
04/13 16:51, , 5F
04/13 16:51, 5F
→
04/13 17:14, , 6F
04/13 17:14, 6F
→
04/13 17:15, , 7F
04/13 17:15, 7F
→
04/13 17:19, , 8F
04/13 17:19, 8F
→
04/13 17:20, , 9F
04/13 17:20, 9F
→
04/13 17:21, , 10F
04/13 17:21, 10F
→
04/22 01:50, , 11F
04/22 01:50, 11F
→
04/22 01:51, , 12F
04/22 01:51, 12F
討論串 (同標題文章)