Re: [討論] Google面試問題
假設f(x)是有x層樓時最糟情況最少需要丟的次數。
x
f(x) = min{max{1 + j - 1, 1 + f(x-j)}}
j=1
f(0) = 0
f(1) = 1
f(2) = 2
f(3) = 2
f(4) = 3
f(5) = 3
f(6) = 3
f(7) = 4
f(8) = 4
....
f(x) = k, where (k-1)k/2 < x <= k(k+1)/2
f(100) = 14
不確定f(x)對不對，k的部份可以用數學歸納法證明。
※ 引述《bleed1979 (十三)》之銘言：
: 問題：
: 假設你有兩顆蛋，然後有一棟100層樓高的大樓。
: 而蛋的特性有的可能很堅固，堅固到從一百層樓跌下都沒事，
: 有的可能很脆弱，一樓就可以摔破。
: 現在你只知道這這兩顆蛋是完全相同的，
: 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: 問題是：你要摔幾次才能計算出來？
: （如果你低於高度摔下蛋，蛋就沒事，如果高於那個樓層，蛋就完蛋）
: 在這過程你可以摔破蛋。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 72.229.214.138
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1397272575.A.198.html
※ 編輯: hweric (72.229.214.138), 04/12/2014 11:17:43
※ 編輯: hweric (72.229.214.138), 04/12/2014 11:18:50
※ 編輯: hweric (72.229.214.138), 04/12/2014 11:19:37
※ 編輯: hweric (72.229.214.138), 04/12/2014 11:22:42
推
04/12 11:28, , 1F
04/12 11:28, 1F
※ 編輯: hweric (72.229.214.138), 04/12/2014 11:33:42
推
04/12 12:09, , 2F
04/12 12:09, 2F
→
04/12 12:20, , 3F
04/12 12:20, 3F
→
04/12 12:20, , 4F
04/12 12:20, 4F
推
04/12 14:45, , 5F
04/12 14:45, 5F
推
04/12 15:28, , 6F
04/12 15:28, 6F
推
04/12 15:30, , 7F
04/12 15:30, 7F
→
04/12 15:57, , 8F
04/12 15:57, 8F
推
04/12 16:29, , 9F
04/12 16:29, 9F
→
04/13 00:47, , 10F
04/13 00:47, 10F
→
04/13 00:48, , 11F
04/13 00:48, 11F
→
04/13 00:48, , 12F
04/13 00:48, 12F
→
04/13 02:47, , 13F
04/13 02:47, 13F
→
04/13 02:48, , 14F
04/13 02:48, 14F
→
04/13 12:54, , 15F
04/13 12:54, 15F
→
04/13 15:32, , 16F
04/13 15:32, 16F
推
04/15 16:26, , 17F
04/15 16:26, 17F
→
04/15 16:29, , 18F
04/15 16:29, 18F
推
04/17 00:26, , 19F
04/17 00:26, 19F
→
04/18 01:01, , 20F
04/18 01:01, 20F
→
04/18 01:02, , 21F
04/18 01:02, 21F
討論串 (同標題文章)
Soft_Job 近期熱門文章
PTT職涯區 即時熱門文章