時間 (2014-04-22 10:10:15)

推文5則 (4推 0噓 1→)
感謝大大分享...

本魯早上練習看看
http://codepad.org/9FhJe5Xp

最近要去面試缺作品集 T_T

※ 引述《bleed1979 (十三)》之銘言：
: 問題：
: 假設你有兩顆蛋，然後有一棟100層樓高的大樓。
: 而蛋的特性有的可能很堅固，堅固到從一百層樓跌下都沒事，
: 有的可能很脆弱，一樓就可以摔破。
: 現在你只知道這這兩顆蛋是完全相同的，
: 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: 問題是：你要摔幾次才能計算出來？
: （如果你低於高度摔下蛋，蛋就沒事，如果高於那個樓層，蛋就完蛋）
: 在這過程你可以摔破蛋。
: --- 以下是完全不經大腦思考的 rough 策略，有雷 ---
: http://ideone.com/B7E85H
: 策略是：
: 當我還有兩次機會時，我使用二分法。
: 當我只剩一次機會時，選擇已經安全的樓層 + 1。　
: 附上此策略的解答樓層 => 次數
: 1=>3
: 2=>4
: 3=>5
: 4=>6
: 5=>7
: 6=>8
: 7=>9
: 8=>10
: 9=>11
: 10=>12
: 11=>13
: 12=>14
: 13=>15
: 14=>16
: 15=>17
: 16=>18
: 17=>19
: 18=>20
: 19=>21
: 20=>22
: 21=>23
: 22=>24
: 23=>25
: 24=>26
: 25=>27
: 26=>28
: 27=>29
: 28=>30
: 29=>31
: 30=>32
: 31=>33
: 32=>34
: 33=>35
: 34=>36
: 35=>37
: 36=>38
: 37=>39
: 38=>40
: 39=>41
: 40=>42
: 41=>43
: 42=>44
: 43=>45
: 44=>46
: 45=>47
: 46=>48
: 47=>49
: 48=>50
: 49=>50
: 50=>3
: 51=>4
: 52=>5
: 53=>6
: 54=>7
: 55=>8
: 56=>9
: 57=>10
: 58=>11
: 59=>12
: 60=>13
: 61=>14
: 62=>15
: 63=>16
: 64=>17
: 65=>18
: 66=>19
: 67=>20
: 68=>21
: 69=>22
: 70=>23
: 71=>24
: 72=>25
: 73=>26
: 74=>26
: 75=>4
: 76=>5
: 77=>6
: 78=>7
: 79=>8
: 80=>9
: 81=>10
: 82=>11
: 83=>12
: 84=>13
: 85=>14
: 86=>15
: 87=>15
: 88=>5
: 89=>6
: 90=>7
: 91=>8
: 92=>9
: 93=>9
: 94=>6
: 95=>7
: 96=>7
: 97=>7
: 98=>7
: 99=>7
: 100=>7
--
※ 發信站: 批踢踢實業坊(pttweb.tw), 來自: 1.161.139.227
※ 文章網址: https://pttweb.tw/Soft_Job/M.1398132615.A.C86
※ 編輯: IhateOGC (1.161.139.227), 04/22/2014 10:15:44

#1推 :有沒有人能分享3顆蛋或n顆蛋的解法阿~04/22 16:16

#2 3顆蛋我自己算最多是要摔9次有無更快解法?04/22 16:20

#3推 :超過三顆蛋應該沒有數學上的close-form solution04/23 22:58

#4 程式角度的做法是用DP算固定蛋數與次數可丟幾層這樣04/23 22:59

#5 補遞回式:e=蛋,t=次數,f(e,t)=f(e-1,t-1)+f(e,t-1)+104/24 01:22