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

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

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

　　題目：

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

　　形形色色的解答：

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

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

　　解答1：得0分的答案

　　用二分法。

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

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

　　解答2：得5分的答案

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

　　據說，他這種思路的靈感來自于數學中的求極值問題。

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

　　解：設一個自然數為x另一個自然數為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]

　　所以可得：

　　當x取12.5時有最小值2×156.25=312.5（當x==y==12.5時取得極小值）

　　當x取25時有最大值2×（12.52+156.5）=625

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

　　那么我們的做法如下：

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

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

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

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

　　解答3：得10分的答案

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

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

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

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

　　3

　　得出答案是14。