Re: [討論] Google面試問題
最佳策略是先用一顆蛋用二分法
e.g., 50F 沒破 -> 可能區間(51 - 100) ; 破 -> 可能區間(1 - 49)
用同樣方法縮小可能區間直到第一顆蛋破掉
接下來第二顆蛋就只能從當時知道的可能區間最低樓層一樓一樓增加
才能確保當蛋破掉的時候可以確定答案
best case 可以在log2 100 次左右用一顆蛋就得到答案
worse case (50F 第一顆蛋就破掉) 就是1+49次
※ 引述《eetug (eetug)》之銘言：
: ※ 引述《bleed1979 (十三)》之銘言：
: : 作者: bleed1979 (十三) 看板: Soft_Job
: : 標題: [討論] Google面試問題
: : 時間: Sat Apr 12 02:07:46 2014
: : 問題：
: : 假設你有兩顆蛋，然後有一棟100層樓高的大樓。
: : 而蛋的特性有的可能很堅固，堅固到從一百層樓跌下都沒事，
: : 有的可能很脆弱，一樓就可以摔破。
: : 現在你只知道這這兩顆蛋是完全相同的，
: : 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: : 問題是：你要摔幾次才能計算出來？
: : （如果你低於高度摔下蛋，蛋就沒事，如果高於那個樓層，蛋就完蛋）
: : 在這過程你可以摔破蛋。
: : --- 以下是完全不經大腦思考的 rough 策略，有雷 ---
: : http://ideone.com/B7E85H
: : 策略是：
: : 當我還有兩次機會時，我使用二分法。
: : 當我只剩一次機會時，選擇已經安全的樓層 + 1。
: 我的策略
: 1.先以十樓為單位丟，
: 2.丟到會破的，再減9個樓層丟
: 最快時間
: 1樓破：2次，一次十樓，一次一樓
: 最慢時間
: 99樓
: 10次+9次=>19次
: 10次是10 20 30~100 。共 10 次才會破
: 9次是 91 92 到99樓 ，共 9次才會破
: 以上為面試 google的答案
: 如果是面試鴻海，我會叫供應商提測試報告
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.240.208.86
※ 文章網址: http://www.ptt.cc/bbs/Tech_Job/M.1397305461.A.B88.html
噓
04/12 20:24, , 1F
04/12 20:24, 1F
→
04/12 20:27, , 2F
04/12 20:27, 2F
噓
04/12 22:34, , 3F
04/12 22:34, 3F
→
04/13 01:10, , 4F
04/13 01:10, 4F
討論串 (同標題文章)