時間 (2014-04-13 02:37:56)

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

有些題目可以做到更好--
※ 發信站: 批踢踢實業坊(pttweb.tw), 來自: 1.171.48.246
※ 文章網址: https://pttweb.tw/Soft_Job/M.1397327883.A.6EA

#1推 :感謝資訊04/14 14:16

#2推 :#typo: storey04/23 02:26