推 shock0223:有丟5/3次這種東西？？ 04/13 16:11
我是用機率的觀點去看，而非討論串的big-O
以2樓的情況來看，很簡單，先丟1樓再丟2樓
1樓就破了，你也不用丟2樓了
1樓沒破，你要丟2樓
可能破可能沒破
總共三種情況，分別丟1 2 2次
平均就是丟5/3次
※ 編輯: Domos (42.75.112.29), 04/14/2014 08:15:23
※ 引述《bleed1979 (十三)》之銘言：
: ※ [本文轉錄自 Soft_Job 看板 #1JI2zrVk ]
: 作者: bleed1979 (十三) 看板: Soft_Job
: 標題: [討論] Google面試問題
: 時間: Sat Apr 12 02:07:46 2014
: 問題：
: 假設你有兩顆蛋，然後有一棟100層樓高的大樓。
: 而蛋的特性有的可能很堅固，堅固到從一百層樓跌下都沒事，
: 有的可能很脆弱，一樓就可以摔破。
: 現在你只知道這這兩顆蛋是完全相同的，
: 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: 問題是：你要摔幾次才能計算出來？
: （如果你低於高度摔下蛋，蛋就沒事，如果高於那個樓層，蛋就完蛋）
: 在這過程你可以摔破蛋。
先假設蛋的硬度是uniform distribution
以100層來說，我們分成1~101級
1級表示1樓摔下來就破
100級表示100樓摔下來破
101級表示100樓摔下來也不破
所以我們有101個級距，uniform distributed
你可以挑戰這個假設，例如使用normal distribution
或是增加級數，例如200個級距，但101級後就只能確定屬於100層
但我們先討論最簡單的case
1. 在此假設下，我們從n樓丟下，蛋破的機率是 n/101
延伸此假設，在最高m樓的情況下，從n樓將蛋丟下
蛋破的機率是 n/(m+1)
2. 假設蛋在x樓破了，我們就被迫從1樓開始丟起
此時的期望值為 g(x) = (x*x + x - 2)/ 2x
我們先假設x是6 (從第6層丟下結果破了)
可能的情況有
1破 => 1次
2破 => 2次
3破 => 3次
4破 => 4次
5破 => 5次
5不破6破 => 5次
每種情況的機率是 1/6
(1+2+3+4+5+5)/6 = 20/6 = g(6)
3. 假設蛋在x樓丟下不破
等於是變成 x+1樓 ~ m樓的問題
問題可以轉化成 1樓 ~ m-x樓的問題
總共 m - x + 1 個級距 (包括m-x樓不破)
3. 綜合(1) (2) (3)
在最高m樓的情況下，將二顆蛋從n樓丟下次數的問題
可以看成是 蛋破的機率 * 一顆蛋在最高n樓丟下次數的問題
+ 蛋不破的機率 * 二顆蛋從n+1樓~m樓丟下次數的問題
f(n, m) = n/(m+1) * g(n) + (1-n/(m+1)) * f(m-n, k) + 1
(記得加一，已經丟一次了)
新變數k表示第二次從k樓丟下
f(n, 100) = n/(101) * g(n) + (1-n/101) * f(100-n, k) + 1
4. f'(m)表示f(n, m)值域的min (我們要求的)
f'(1) = 1
f'(2) = 5/3
照這樣一路求到f'(100)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.58.103.123
※ 文章網址: http://www.ptt.cc/bbs/Tech_Job/M.1397269215.A.729.html