Re: [討論] Google面試問題

[evanslee (321)]

可以參考看看

假設 我們有N次機會來判定 是否會破

我們可以從第N樓開始丟, 可分情況兩種

1) 從第N樓丟破=>還有另一蛋但可以從1丟到 N-1樓 檢驗
   所以情況(1)最多N次

2) 從第N樓丟沒破，我們剩下N-1次可以測驗
   所以 可以往上至N+(N-1)樓丟擲 (丟了之後還剩下N-2次可以試驗)

由 (1),(2) 邏輯推斷
最多我們需要幾次 N+(N-1)+(N-2)+...+1 > 100樓
得到 N=14

※ 引述《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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.192.2.235
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1397272044.A.B03.html
推 aresa:為什麼沒人推你
推 e0204558:無法反駁啊
推 bndan:明明第二~第三篇解法一樣 為何都到樓下去了呢..推先行者
推 carlcarl:為啥知道往上加也是用N-1??
推 apley:因為你己經丟了第一次了, 不管怎樣都是N-1
推 prpure:為什麼N次機會要從N樓開始丟?
推 pcyu16:這篇是正解