時間 (2014-04-12 19:20:39)

推文12則 (0推 0噓 12→)
※ 引述《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

--
※ 發信站: 批踢踢實業坊(pttweb.tw), 來自: 211.75.130.241
※ 文章網址: https://pttweb.tw/Soft_Job/M.1397301641.A.7FD
※ 編輯: bndan (211.75.130.241), 04/12/2014 19:22:14

#1→ :我是考官會問為什麼不是20,40,60,80 為什麼不是33,66,9904/12 19:32

#2 這段邏輯也要寫出來..04/12 19:32

#3→ :分兩層所以開更號三層就開三方以此類推不寫出來是因為這04/13 10:36

#4 是非常基礎的東西 @@04/13 10:36

#5→ :假設每層出現的機率一致是假命題,分層也是04/13 16:51

#6→ :特別標記當然是"補足"命題...換言之這也是叫凡人解原因 :)04/13 17:14

#7 另外分層的部份是依照他給的條件下去算這只是普通優化手續04/13 17:15

#8 補充:分兩層之意是只有兩顆蛋換言之有三顆可以分三層以此04/13 17:19

#9 推.當層數越多最佳會越來越爛最遭會越來越趨向平均這是基04/13 17:20

#10 本演算法(大學部)的東西...這東西是假命題? 這應該是誤會喔04/13 17:21

#11→ :不...恕在下直言你會這樣解代表你根本沒看清楚題目04/22 01:50

#12 在下認為看清楚題目才是解決問題的第一要件04/22 01:51

Re: [討論] Google面試問題

同標題文章