推 zased:感謝資訊 04/14 14:16
推 h520:#typo: storey 04/23 02:26
※ 引述《bleed1979 (十三)》之銘言：
: 問題：
: 假設你有兩顆蛋，然後有一棟100層樓高的大樓。
: 而蛋的特性有的可能很堅固，堅固到從一百層樓跌下都沒事，
: 有的可能很脆弱，一樓就可以摔破。
: 現在你只知道這這兩顆蛋是完全相同的，
: 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: 問題是：你要摔幾次才能計算出來？
: （如果你低於高度摔下蛋，蛋就沒事，如果高於那個樓層，蛋就完蛋）
: 在這過程你可以摔破蛋。
答案前面都有了
這邊補充一下, 這題有很多變形, 主要解題技巧是 load balance
想辦法減輕 worst case 工作量, 將它攤到其他地方
變形有
Ref: https://class.coursera.org/algs4partI-004/
by Robert Sedgewick
Interview Questions: Analysis of Algorithms
Egg drop. Suppose that you have an N-story building and plenty of eggs. An
egg breaks if it is dropped from floor T or higher and does not break
otherwise. Your goal is to devise a strategy to determine the value of T
given the following limitations on the number of eggs and tosses:
Version 0: 1 egg, <= T tosses. (<= 是小於等於)
Version 1: ~1 lg N eggs and ~ 1 lg N tosses
Version 2: ~lg T eggs and ~ 2 lg T tosses
Version 3: 2 eggs and ~ 2 sqrt(N) tosses <= 原 po 的題目落在這
Version 4: 2 eggs and <= c sqrt(T) tosses for some fixed constant c
有些題目可以做到更好
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.171.48.246
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1397327883.A.6EA.html