作者artingo (那就起而行吧)
看板Tech_Job
標題Re: [討論] Google面試問題
時間Sun Apr 13 12:08:42 2014
個人認為正解是「最多七次」 因為一次可以刪掉最多50%的二分法，最多到第七次就能測出了 大家可以畫二分法的樹狀圖，第七層就答案出來了 第一次：丟50樓 第二次：有破丟25樓，沒破去75樓丟 依此類推..... (接下來bbs我不會畫樹狀圖，所以只列出每次都破的情況) 第三次：有破丟13樓 第四次：有破丟7樓 第五次：有破丟4樓 第六次：有破丟2樓 第七次：視上面結果，再去1或3樓丟，答案出來！ 以上面結果為例，可能的歷史進程就是 progress(50,25,13,7,4,2,1)=>得證1樓就會破 progress(50,25,13,7,4,2,3)=>得證到3樓才會破，2樓safe 還有另外62種可能的結果 因樹狀圖共有七階，有2的(7-1)次方,總共64種可能的歷史進程，但最多只要測7次 另顆蛋是完全相同的，所以沒必要再測一次，只是益智題的障眼法。
※ 引述《bleed1979 (十三)》之銘言： : ※ [本文轉錄自 Soft_Job 看板 #1JI2zrVk ] : 作者: bleed1979 (十三) 看板: Soft_Job : 標題: [討論] Google面試問題 : 時間: Sat Apr 12 02:07:46 2014 : 問題： : 假設你有兩顆蛋，然後有一棟100層樓高的大樓。 : 而蛋的特性有的可能很堅固，堅固到從一百層樓跌下都沒事， : 有的可能很脆弱，一樓就可以摔破。 : 現在你只知道這這兩顆蛋是完全相同的， : 你想要知道蛋最高從哪一層樓摔下來不會摔破。 : 問題是：你要摔幾次才能計算出來？ : （如果你低於高度摔下蛋，蛋就沒事，如果高於那個樓層，蛋就完蛋） : 在這過程你可以摔破蛋。 : --- 以下是完全不經大腦思考的 rough 策略，有雷 --- : http://ideone.com/B7E85H --
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.34.206.49 ※ 文章網址: http://www.ptt.cc/bbs/Tech_Job/M.1397362124.A.686.html
→ exxfyy901926:只有兩顆蛋,50樓破25樓又破,就沒得測了 04/13 12:10
→ hobart277:大家都知道如果有無限顆蛋的話用binary search 04/13 12:16
推 zilong308:有破就要從前一次沒破的樓層一層一層測，因為只剩一顆蛋 04/13 12:19
→ zilong308:但一路沒破的狀況應該是七次無誤，但這樣另一顆蛋沒用 04/13 12:20
→ zilong308:到 04/13 12:20
推 zilong308:這題目應該是問最少幾次吧 最多是50次 04/13 12:22
→ msty:三層測一次, 破了就拿另一顆測下一層, 都破就是3n-2層。 04/13 12:37
噓 demonhell:你只有兩顆蛋 還二分法 題目不看清楚一下就被刷掉了 04/13 12:54
→ msty:二分一定錯, 不過四層一組,應該才是最佳解。 04/13 13:00
→ msty:這題應該是2(蛋的個數)狀態數去計算。 04/13 13:02
This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers.
留言列表
留言列表
