12.3日谷歌面試題詳解

　　題目：你拿著兩個(gè)雞蛋站在100層的大樓上。雞蛋或許結(jié)實(shí)到從樓頂?shù)粝乱膊粫?huì)摔破，或許很易碎，在一樓摔下就破碎。最少試驗(yàn)多少次可以找出雞蛋不會(huì)被摔碎的最高樓層?

　　解答： 在只有一個(gè)雞蛋時(shí)，保險(xiǎn)起見，我們只能從一樓開始，一層一層地試驗(yàn)，看看雞蛋有沒有被摔爛。這樣最精確，但是消耗的時(shí)間也最久。如果我們事先就知道這個(gè)雞蛋不被摔碎的最高落下點(diǎn)在30層到75層之間，我們最多也只要嘗試45次就能知道結(jié)果�，F(xiàn)在我們手上有兩個(gè)雞蛋，根據(jù)上面的分析，一個(gè)合理的策略就是用第一個(gè)雞蛋確定出一個(gè)較小的樓層范圍，然后在這個(gè)范圍里用第二個(gè)雞蛋從下往上逐層嘗試。

　　比如說讓第一個(gè)雞蛋每隔5層試驗(yàn)一次。當(dāng)它在某一層被摔爛時(shí)，也就意味著確定了一個(gè)4層的待測(cè)試寬度(為什么是4層呢?假如雞蛋在5樓的時(shí)候沒破，10樓的時(shí)候破了，那么我們就只需要知道雞蛋在 6 , 7 , 8 , 9 層的結(jié)果)。這時(shí)候，用第二顆雞蛋一層一層地嘗試，就能用較少的次數(shù)找出雞蛋剛好摔不爛的高度。

　　需要注意的是，如果想留給第二顆雞蛋較小的測(cè)試寬度，就要縮短第一個(gè)雞蛋的測(cè)試跨度。相應(yīng)的，也就增加了嘗試次數(shù)。為了確定合適的跨度，使得總試驗(yàn)次數(shù)之和盡可能小，我們可以采取如下的.辦法。

　　設(shè)跨度是L，第一顆雞蛋的嘗試次數(shù)就是[ 100/L ]，第二顆雞蛋的嘗試次數(shù)就是 L - 1，因此嘗試次數(shù)總和就是 [ 100/L ] + L - 1 。根據(jù)這個(gè)公式，我們可以列出下面這個(gè)表格：

　　可以看出，我們只需要選 8 - 13 之間的一個(gè)寬度，都能使得總嘗試次數(shù)是19次。

　　但問題是，這已經(jīng)是最優(yōu)策略了嗎，有沒有更好的方法呢?

　　有的。上面的方法固定了第一顆雞蛋的測(cè)試跨度，如果我們靈活變動(dòng)，就能使得總嘗試次數(shù)變得更少。首先，我們選擇從14樓丟下第一顆雞蛋。如果它破碎了，我們就從1樓開始，逐層丟第二顆雞蛋，最多試14次便能得到答案。如果它沒有破碎，那我們往上走 13 層，在 27 樓第二次丟下第一顆雞蛋。此時(shí)如果雞蛋碎了，那我們只需要在 15 層到 26 層之間用第二顆雞蛋進(jìn)行最多12次試驗(yàn)即可，加上第一顆雞蛋的兩次嘗試，仍然是14次。類似的，依次減小測(cè)試跨度，如果雞蛋足夠頑強(qiáng)，那我們丟下第一顆雞蛋的樓層就分別是 14 ， 27 ， 39 ， 50 ， 60 ， 69 ， 77 ，84 ， 90 ， 95 ， 99 以及最后的100層。因?yàn)榈谝活w雞蛋每多嘗試一次，第二顆雞蛋需要嘗試的最大次數(shù)就減少一次，因此，總嘗試次數(shù)的最大可能值一直是不變的，保持在14次。用這種方法，我們只需要不超過14次的嘗試就能夠找出答案。有沒有更優(yōu)的策略了?感興趣的讀者可以自行思考。

http://m.ardmore-hotel.com/

【12.3日谷歌面試題詳解】相關(guān)文章：

谷歌的面試題目04-11

谷歌工程師的面試題04-11

谷歌薪酬最高十職位10-28

德爾福面試題01-11

移動(dòng)面試題04-01

英文面試題08-06

mybatis面試題05-09

谷歌創(chuàng)始人送給大學(xué)生的畢業(yè)留言07-30

華為公司面試題04-29

英語(yǔ)面試題目03-30