一個雞蛋從第N層及以上的樓層落下來會摔破？

　　現(xiàn)在很多大型IT企業(yè)在面試時都喜歡問一些智力相關(guān)的題目，雖然智力面試題在面試筆試中占的比例不大，但很多時候，面試環(huán)節(jié)中智力題往往會成為我們拿offer的最大攔路虎。因為有些面試官認(rèn)為通過智力題可以考查你的思維能力、抽象問題的能力。

　　下面是一道很經(jīng)典的智力型面試題，是一位Java老師的朋友去BAT面試中親身見識過的一道題。各位來體驗一下，看看自己的大腦是不是好使。

　　題目：

　　有一棟樓共100層，一個雞蛋從第N層及以上的樓層落下來會摔破，在第N層以下的樓層落下不會摔破。給你2個雞蛋，設(shè)計方案找出N，并且保證在最壞情況下，最小化雞蛋下落的次數(shù)。(假設(shè)每次摔落時，如果沒有摔碎，則不會給雞蛋帶來損耗)

　　形形色色的解答：

　　在參考下面的解答之前，請你先仔細思考10分鐘?？茨憬o出的方案最小下落次數(shù)是多少。如果題目總分10分，看看自己能得幾分。

　　===========================答案分割線================================

　　解答1：得0分的答案

　　用二分法。

　　這基本可以說就是沒有通過大腦得出來的答案，而且還貌似很牛掰的樣子，并常常帶著一個lgn的復(fù)雜度。如果你接著問怎么個二分法，他就答不上來了。

　　這個答案不是我杜撰出來的，而是我拿這個題目問過身邊的一些人，其中有幾個人真的隨口就把二分法給說出來了。每當(dāng)我聽到二分法時，當(dāng)我沒問。

　　解答2：得5分的答案

　　如果我們動一下腦子仔細思考這個問題，我們會得到一個相對不錯的答案。參加BAT面試那位朋友就給出了下面的這種方案，并自認(rèn)為是一種很完美的答案。但面試官給出的回答是：我還是不滿意。

　　據(jù)說，他這種思路的靈感來自于數(shù)學(xué)中的求極值問題。

　　已知兩個自然數(shù)的和為25，求這兩個數(shù)的平方和的最大、最小值。

　　解：設(shè)一個自然數(shù)為x另一個自然數(shù)為25-x

　　x2+(25-x)2

　　=2x2-50x+625

　　=2(x2-25x+312.5)

　　=2[(x-12.5)2-156.25+312.5]

　　=2[（x-12.5）2+156.25]

　　所以可得：

　　當(dāng)x取12.5時有最小值2×156.25=312.5（當(dāng)x==y==12.5時取得極小值）

　　當(dāng)x取25時有最大值2×（12.52+156.5）=625

　　因此，很容易得到啟發(fā)(當(dāng)然，這只是一種直覺，并沒有什么理論依據(jù)。)。100層樓，平均分成10分，每份剛好10層。

　　那么我們的做法如下：

　　將100層樓分成10分，每一份就是10層樓。首先，將雞蛋從第10層樓開始扔。那么結(jié)果有兩種可能：

　　情況1：如果碎了，說明臨界樓層在1到10之間，但現(xiàn)在只剩下一個雞蛋了，只能從第一層一直到第10層。

　　情況2：如果沒有碎，接下來從第20層扔雞蛋。

　　該方法的思路是，用一個雞蛋來試探，找到臨界樓層的大致范圍[1~10]、[11-20]….[91-100]。然后用另一個雞蛋在大致范圍內(nèi)找出精確樓層。該方法的最壞次數(shù)是：18次。(自己去算，如果你算出來是17次，那就17次唄)

　　解答3：得10分的答案

　　這是真正有理有據(jù)的解答。具體如下所述：

　　我們先假設(shè)最壞情況下，雞蛋下落次數(shù)為x，即我們?yōu)榱苏页鯪，一共用雞蛋做了x次的實驗。那么，我們第一次應(yīng)該在哪層樓往下扔雞蛋呢？先讓我們假設(shè)第一次是在第y層樓扔的雞蛋，如果第一個雞蛋在第一次扔就碎了，我們就只剩下一個雞蛋，要用它準(zhǔn)確地找出N，只能從第一層向上，一層一層的往上測試，直到它摔壞為止，答案就出來了。由于第一個雞蛋在第y層就摔破了，所以最壞的情況是第二個雞蛋要把第1到第y-1層的樓都測試一遍，最后得出結(jié)果，噢，原來雞蛋在第y-1層才能摔破(或是在第y-1層仍沒摔破，答案就是第y層。)這樣一來測試次數(shù)是1+(y-1)=x，即第一次測試要在第x層。OK，那如果第一次測試雞蛋沒摔破呢，那N肯定要比x大，要繼續(xù)往上找，需要在哪一層扔呢？我們可以模仿前面的操作，如果第一個雞蛋在第二次測試中摔破了，那么第二個雞蛋的測試次數(shù)就只剩下x-2次了(第一個雞蛋已經(jīng)用了2次)。這樣一來，第二次扔雞蛋的樓層和第一次扔雞蛋的樓層之間就隔著x-2層。我們再回過頭來看一看，第一次扔雞蛋的樓層在第x層，第1層到第x層間共x層；第1次扔雞蛋的樓層到第2次扔雞蛋的樓層間共有x-1層(包含第2次扔雞蛋的那一層)，同理繼續(xù)往下，我們可以得出，第2次扔雞蛋的樓層到第3次扔雞蛋的樓層間共有x-2層，……最后把這些互不包含的區(qū)間數(shù)加起來，應(yīng)該大于等于總共的樓層數(shù)量100，即

　　1x+(x-1)+(x-2)+...+1>=100

　　2(x+1)*x/2 >= 100

　　3

　　得出答案是14。