看板 Tech_Job 關於我們 聯絡資訊
個人認為正解是「最多七次」 因為一次可以刪掉最多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
apley:你只有2個蛋, 連『前提』都不理的解法就是GG再聯絡 04/13 14:30
apley:如果寫程式可以無視硬體資源的前提, 那暴力解可多了.... 04/13 14:31
keieykdx:sorry 題目看不懂可以多看幾次 04/13 14:31
artingo:題目已寫過程可以摔破蛋啊 04/13 14:56
artingo:哪裡有寫蛋破就沒了? 04/13 14:57
shoube: 可以摔破蛋是指這種狀況在實驗過成中是合理的 04/13 15:06
shoube:可是你只有兩次機會 這樣很難懂嗎== 04/13 15:07
shoube:如過要用這種方法解提目怎麼會只給你兩顆蛋 04/13 15:09
shoube:“蛋就完蛋”四個字沒看到…? 04/13 15:10
shoube:如果題目給你7顆蛋用此法就最適合 04/13 15:14
cha122977:你只有兩顆蛋,蛋可以破,但顯然不會補啊… 04/13 16:11
kurumi31034:左邊的門自行出去謝謝 04/13 17:49
chenlarry:第一句話就已經說了只有兩顆蛋.. 04/13 18:21
debut:如你所說,題目已寫過程可以摔破蛋,但有說蛋破了再補給你嗎? 04/13 22:06