Re: [討論] Google面試問題
打在記事本後再貼上的，怕斷線
================================================
我解出來了，若有錯誤請多指教...
不過基本上我認為我得答案是對的 XD
首先，假設有一層樓，"最低的 worst case" 就是 1
若是有兩層樓，"最低的 worst case" 就是 2
我們定義一個 f(x) 代表從 x 層丟下去"最低的 worst case"
我們已知
f(1) = 1
f(2) = 2
而 f(3) 等於多少呢?
我們已知計算"最低的 worst case"的演算法絕對不可能從一層一層丟下去
否則 f(n) 就會是 n。
所以當從中間丟第一顆蛋下去，則接下來會被切成兩個情況
破掉 = > f(1)
沒破掉 => 1
所以 f(3) = min( f(1), 1 ) + 1 = 2
接下來計算 f(4)
若從中間丟下去，可以從第二層丟或是第三層丟，所以會被分成以下情況
若從第二層丟 =>
沒破 => f(2)
破 => 1
所以如果我們從第二層丟，所得到的"最低 worst case" = Max(f(2), 1) + 1 = 3
若從第三層丟 =>
沒破 => f(1)
破 => 2
所以"最低 worst case" = Max(f(1), 2) + 1 = 3
所以 f(4) = min( Max(1,f(2)), Max(f(1),2) ) + 1
= 2 + 1 = 3
根據以上情況可以看出幾個公式
1. f(n) >= f(n-1)
2. f(n) = min( x=1..(n-1) Max(f(x), (n-x-1)) ) + 1
3. f(n) <= n
用公式三可以判端出
Max( f(1), 2 ) = 2
Max( 1, f(2) ) = 不確定
所以 min( Max(1,f(2)), Max(f(1),2) ) = min( Max(1,f(2)), 2 )
我們已知 f(2) <= 2
所以 f(3) 可以簡化成 min(Max(1,f(2)))
另外可以對公式二進行簡化成公式四
4. f(n) = min( x=1..((n-1)/2) Max( x, f(n-x-1) ) ) + 1
帶入此公式可以算出 { 若 x = f(n-x-1) ，則定義 Max(x, f(n-x-1)) = x ||
f(n-x-1) }
f(3) = min(1) + 1 = 2
f(4) = min(f(2)) + 1 = 3
f(5) = min(f(3), 2) + 1 = 3
f(6) = min(f(4), f(3) || 2) + 1 = 3
f(7) = min(f(5), f(4), 3) + 1 = 4
f(8) = min(f(6), f(5), f(4) || 3) + 1 = 4
f(9) = min(f(7), f(6), f(5) || 3, 4) + 1 = 4
f(10) = min(f(8), f(7), f(6), 4) + 1 = 4
由以上可判斷出每一個 f(n) 有一個值 λ ，若 x < λ ，則 min(x, f(n-x-1)) =
f(n-x-1)
若 x >= λ，則min(x, f(n-x-1)) = x
所以可以推出公式五
5. f(n) = min( f(n-2), f(n-3), ... , f(n-λ), λ, (λ+1), (λ+2), ... ) + 1
由公式五可以看出來，min( f(n-2), f(n-3), ... , f(n-λ), λ, (λ+1), (λ+2),
... ) = min(λ, f(n-λ))
藉由之前λ定義可以看出
f(n-λ) > λ-1
因為f(n-λ)是正整數，所以可以推論出 f(n-λ) >= λ
所以 min( f(n-2), f(n-3), ... , f(n-λ), λ, (λ+1), (λ+2), ... ) = λ
因此推導出公式六
6. f(n) = λ+1
接下來，因為 f(n) = λ+1，所以 min(f(n), λ+1) = λ+1
有公式五跟公式六可以推導出公式七
7. f(n+f(n)) = f(n) + 1
所以可以推出
f(1+f(1)) = f(2) = f(1) + 1 = 2
f(2 +f(2)) = f(4) = f(2) + 1 = 3
f(4 +f(4)) = f(7) = f(4) + 1 = 4
f(7 +f(7)) = f(11) = f(7) + 1 = 5
f(11 +f(11)) = f(16) = f(11) + 1 = 6
可看出這是一個遞增公式
f(1) ~ f(20) 分別為
1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6
雖然知道這是怎麼出來的，但是我公式寫不出來，不知道要用啥符號 @@
所以可以導出， 若"worst case" 若為 t
則樓層最高為 (1+t)t/2 (梯形公式) ，最低為 t(t-1)/2 + 1
所以若100樓所能導出的 "最低 worst case" 為 14
因為 100 介於 91 ~ 105 之間
至於要怎麼丟，寫個 recusive 應該就能跑出來了
感覺繞了一大圈遠路才算出來 @@
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.218.64.133
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1397811257.A.34C.html
推
04/18 19:24, , 1F
04/18 19:24, 1F
→
04/18 19:25, , 2F
04/18 19:25, 2F
推
04/18 20:00, , 3F
04/18 20:00, 3F
推
04/18 20:04, , 4F
04/18 20:04, 4F
※ 編輯: cyclone350 (123.193.201.124), 04/18/2014 21:30:43
※ 編輯: cyclone350 (123.193.201.124), 04/18/2014 21:42:15
※ 編輯: cyclone350 (123.193.201.124), 04/18/2014 22:03:46
討論串 (同標題文章)
完整討論串 (本文為第 14 之 19 篇)：
討論
18
38