王國維在《人間詞話》中道出了三個境界：
一境：昨夜西風凋碧樹。獨上高樓，望盡天涯路。
二境：衣帶漸寬終不悔，為伊消得人憔悴。
三境：眾里尋他千百度。驀然回首，那人卻在燈火闌珊處。
? ? 唐詩宋詞元曲清小說，余獨愛宋詞，因其不拘一格，隨性灑脫是也。三句也毫不例外的屬于宋詞。分別是北宋晏殊《蝶戀花·檻菊愁煙蘭泣露》、北宋柳永《蝶戀花·佇倚危樓風細細》、南宋辛棄疾《青玉案·元夕》。如果用三個字來總結三個境界的話，就是“立”， “守”， “得”。
? ? 立：當解為高處不勝寒，目標明確，無雜念；
? ? 守：應該是在追求真理的道路上尋尋覓覓，孜孜不倦；
? ? 得：就該是得道之后，黎明的曙光驅散黑暗，豁然開朗的那一瞬了吧。
? ? 回到扔雞蛋的話題上來，這是程序員面試中的一道經典面試，先看一下問題的詳細描述:
[一幢 100 層的大樓,給你兩個雞蛋. 假設在第 n 層扔下雞蛋,雞蛋不碎,那么從前 n-1 層扔雞蛋都不碎.這兩個雞蛋一模一樣,不碎的話能夠扔無數次. 提出一個策略, 要保證能測出雞蛋恰好不會碎的樓層, 并使此策略在最壞情況下所扔次數最少]
? ? [雞蛋做自由落體運動，腦補物理公式：h=1/2*g*t^2。v=g*t。吧啦吧啦，其實這些一點兒用也沒有。并且，你如果想到這里，你就跑偏了，距離出局也就不遠了。還有就是你如果覺得就憑一個雞蛋，一米都會摔碎，一層樓至少三米高，而直接得出問題答案：問題不現實。那咱們別玩了，再見 !]。
? ? 回歸正題，我們先來分析一下問題，有一些前提我們需要知道：
雞蛋沒有被摔碎，可以繼續(xù)重復使用，如果摔碎了，則不能重復使用；
有可能在一層就摔碎，也有可能在100層都摔不碎；
可以摔碎兩個雞蛋，只要能確定最高不會被摔碎的樓層。
? ? 有了這些前提條件，我們就可以分析問題了。[當然，你可以先自己思考一下，再繼續(xù)往下看... ... ]
? ? 其實接下來我想把這個問題給非計算機或者數學專業(yè)的人講清楚，所以會從簡至繁/循序漸進的思路對這個問題進行分析，當然，也是參考了網絡上各位大神的分析，有了自己的理解。本人水平有限，難免有錯，歡迎指正。
正文
從原始問題的需求來看，我們的目的就是為了得到一個雞蛋不會被摔碎的最高層數（下文稱為臨界層）。至于要求的最少實驗次數，這屬于優(yōu)化問題，可以暫且不管，先看原始問題如何解決，這樣做的目的可以讓我們一開始就能夠專注于問題本身，不至于直接陷入最優(yōu)解的困擾中而忘記了初衷。
? ? 于是，我們獨上高樓，因為站在最高的地方，才能排除下面的烏煙瘴氣的影響，才能看得清，看得遠，看的到自己想要的東西。
? ? 為了得到不摔碎的最高層數，最簡單明了辦法就是從第一層開始測試扔雞蛋，逐級增加層數，直到摔碎的層數N，那么臨界層就是N-1。
? ? 這樣的話，只需要一顆雞蛋就可以找到臨界層。這種情況下，最差情況就是要測試100次才能得到正確結果（直到第100層才摔碎或著1-100層都沒有摔碎）。
無論如何，最初級的解決方案已經有了：從第一層開始，逐級增加層數測試。那么接下來就是如何去根據現有條件繼續(xù)優(yōu)化我們的最差情況下需要的次數。
? ? 天涯路已望盡，那接下來就是如何最快的上路了。極目遠眺后，發(fā)現可以抄個近路，因此，整理行裝，收拾細軟，拍馬前行了。
既然給了兩顆雞蛋，那么就要充分利用兩顆雞蛋。在計算機系統(tǒng)中最常見的算法就是二分法，也是最容易理解的一種算法。下面就使用兩顆雞蛋和二分法來對以上結果進行一下優(yōu)化。
二分法，顧名思義，就是將規(guī)模為n的問題通過O(1)操作變?yōu)橐?guī)模為n/2的問題，時間復雜度是 O(logN)。在本問題中，就是將100的規(guī)模先經過一次操作將問題變?yōu)?0的規(guī)模。
? ? 對于本問題，應用二分法，就可以直接從第50層開始扔雞蛋。雞蛋碎或者不碎都可以將問題規(guī)?？s小到0-50或者51-100。假如我們在第50層扔下了第一顆雞蛋，只有兩種情況：碎或不碎。如果蛋碎了，那么臨界層應該在1-50之間，接下來用另一個蛋，從1到50逐級測試，直到第二顆蛋也碎掉或者到了第49層也沒有碎，那49就是臨界層；如果第50層沒有碎，那么繼續(xù)測試第75層，同理，繼續(xù)。這樣最壞情況就50層碎掉，49層是臨界層的情況，需要測試50次。因為第一顆雞蛋在第50層碎掉之后，第二顆雞蛋只能從第一層開始逐級往上測試，最差情況就是測試到第49層也沒有碎或者碎了，才能確定臨界層，這樣第一顆雞蛋測試的1次加上第二顆雞蛋測試的49次，就是50次。
? ? 此時，二分法的優(yōu)化結果就是在最差情況下比第一種方法減少了一半，變成了50次。到這里，我們其實可以知道，可用的雞蛋越多，效果會越好，推廣開來也就是n分法了，原理相同。當然，二分法仍然達不到我們的要求，測量的粒度還是太大了，最后一個雞蛋逐級測試大方法其實與原始方法并無太大差別。所以還是有可以優(yōu)化的空間的。
? ? 其實到了二分法，距離真理更近了一些了。二分法在思路上給我們開拓了疆域。接下來就是將問題轉化為另一種思想：動態(tài)規(guī)劃。
? ? 動態(tài)規(guī)劃算法一般適用于最優(yōu)子結構和重疊子問題性質的問題。這兩個性質通俗一些講就是整個問題需要解其不同部分（即子問題），再合并各個部分的解最終得到原問題的解。
? ? 對應到扔雞蛋問題，我們可以這樣考慮：假如我們從第n層扔下，雞蛋沒有碎，那么原始【1-100】的問題，就變成了【n-100】的問題了，因為小于n層雞蛋肯定不會碎。這樣【n-100】就是【1-100】的一個子問題，這個子問題的解再加上第一次嘗試的一次，合并起來的答案就是整個問題的解。
我們用F(n)表示n層樓最差情況需要的測試次數，假設從第 i 層開始扔雞蛋，那么我們有以下分析:
?如果，第 i 層碎掉了，這是最糟糕的情況了，因為只能用剩下的另一顆雞蛋從第一層到第 i-1 層去嘗試，這時候的最差次數是 1 + (i-1) 。
如果，第i層沒有碎掉，那么我們除了用掉一次測試次數外，一顆雞蛋都沒有碎，問題就變成了兩顆雞蛋測試第i+1到n層最差情況下的需要的測試次數了，也就是F(n-i)。所以，這種情況下的最差次數就是 1 + F(n-i)。
對于以上兩種情況，我們取最大值，就是F(n)的臨界值。即：F(n) = 1 + Max(i-1，F(n-i))。
? ? 于是，我們得到了當從第i層扔雞蛋的時候的F(n)的取值，也就是最差情況下的次數。所以，我們嘗試完所有的 i 值(1<= i <=100)的最差情況下的最大次數，然后取最小值對應的 i 值，就是原始問題的最優(yōu)解了。
最后的公式就變成了：F(n) = Min(1?+ Max(i?-?1, F(n-i)))
? ? 對應于100層的高樓，扔雞蛋問題的解就成了：
? ? F(100) = Min(1?+ Max(i?-?1, F(100-i)))
? ??最終結果是14層，也就是最壞情況的嘗試次數是14次，可以找到臨界層。
【驗證】
? ? 當從14層開始測試的時候，最壞情況下當然就是14層碎掉了，然后從第一層開始嘗試到13層，一共14次。
? ? 14層沒有碎的情況比較多，只列舉100層是臨界層的情況，那么所嘗試的樓層數列舉出來就是：14,27, 39, 50,60,69,77, 84,90,95,99,100 。一共12次，小于14次。其他情況也是小于14次的，因此，14是最終結果啦！
最后附上暴力破解的代碼[暫不考慮代碼優(yōu)化]
#include <stdio.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
int fun ( int layer )
{
if ( layer <= 0 )
{
return 0;
}
if ( layer == 1 )
{
return 1;
}
int min = layer;
int temp;
for ( int i = 1; i <= layer; i++ )
{
temp = 1 + MAX(i-1, fun( layer - i ) );
if( min > temp )
min = temp;
}
return min;
}
int main()
{
int layer = 100;
printf("%d",fun(layer));
return 0;
}
[友情提示：不要嘗試用低配計算機跑這段程序，我相信計算機可能不會崩潰，但你一定會崩潰！]
更多有趣文章學習，可關注公眾號【木石說：mushiwords】
文/yycaptain
