Re: [討論] Google面試問題

作者: artingo (那就起而行吧)   2014-04-13 12:08:42
個人認為正解是「最多七次」
因為一次可以刪掉最多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層樓高的大樓。
: 而蛋的特性有的可能很堅固,堅固到從一百層樓跌下都沒事,
: 有的可能很脆弱,一樓就可以摔破。
: 現在你只知道這這兩顆蛋是完全相同的,
: 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: 問題是:你要摔幾次才能計算出來?
: (如果你低於高度摔下蛋,蛋就沒事,如果高於那個樓層,蛋就完蛋)
: 在這過程你可以摔破蛋。
:
作者: exxfyy901926 (exfy)   2014-04-13 12:10:00
只有兩顆蛋,50樓破25樓又破,就沒得測了
作者: hobart277   2014-04-13 12:16:00
大家都知道如果有無限顆蛋的話用binary search
作者: zilong308 (大師兄)   2014-04-13 12:19:00
有破就要從前一次沒破的樓層一層一層測,因為只剩一顆蛋
作者: zilong308 (大師兄)   2014-04-13 12:20:00
但一路沒破的狀況應該是七次無誤,但這樣另一顆蛋沒用到
作者: zilong308 (大師兄)   2014-04-13 12:22:00
這題目應該是問最少幾次吧 最多是50次
作者: msty (Ting)   2014-04-13 12:37:00
三層測一次, 破了就拿另一顆測下一層, 都破就是3n-2層。
作者: demonhell (I count to three...)   2014-04-13 12:54:00
你只有兩顆蛋 還二分法 題目不看清楚一下就被刷掉了
作者: msty (Ting)   2014-04-13 13:00:00
二分一定錯, 不過四層一組,應該才是最佳解。
作者: msty (Ting)   2014-04-13 13:02:00
這題應該是2(蛋的個數)狀態數去計算。
作者: apley (佛渡有緣人)   2014-04-13 14:30:00
你只有2個蛋, 連『前提』都不理的解法就是GG再聯絡
作者: apley (佛渡有緣人)   2014-04-13 14:31:00
如果寫程式可以無視硬體資源的前提, 那暴力解可多了....
作者: keieykdx (YOz桑)   2014-04-13 14:31:00
sorry 題目看不懂可以多看幾次
作者: artingo (那就起而行吧)   2014-04-13 14:56:00
題目已寫過程可以摔破蛋啊
作者: artingo (那就起而行吧)   2014-04-13 14:57:00
哪裡有寫蛋破就沒了?
作者: shoube (B仔)   2014-04-13 15:06:00
可以摔破蛋是指這種狀況在實驗過成中是合理的
作者: shoube (B仔)   2014-04-13 15:07:00
可是你只有兩次機會 這樣很難懂嗎==
作者: shoube (B仔)   2014-04-13 15:09:00
如過要用這種方法解提目怎麼會只給你兩顆蛋
作者: shoube (B仔)   2014-04-13 15:10:00
“蛋就完蛋”四個字沒看到…?
作者: shoube (B仔)   2014-04-13 15:14:00
如果題目給你7顆蛋用此法就最適合
作者: cha122977 (CHA)   2014-04-13 16:11:00
你只有兩顆蛋,蛋可以破,但顯然不會補啊…
作者: kurumi31034   2014-04-13 17:49:00
左邊的門自行出去謝謝
作者: chenlarry (小鬼)   2014-04-13 18:21:00
第一句話就已經說了只有兩顆蛋..
作者: debut (humming bird)   2014-04-13 22:06:00
如你所說,題目已寫過程可以摔破蛋,但有說蛋破了再補給你嗎?

Links booklink

Contact Us: admin [ a t ] ucptt.com