第二天
題目：扔雞蛋問題
有2個雞蛋，從100層樓上往下扔，以此來測試雞蛋的硬度。比如雞蛋在第9層沒有摔碎，在第10層摔碎了，那么雞蛋不會摔碎的臨界點就是9層。
問：如何用少的嘗試次數(shù)，測試出雞蛋不會摔碎的臨界點？
舉個栗子，笨的測試方法，是什么樣的呢？把其中一個雞蛋，從第1層開始往下扔。如果在第1層沒碎，換到第2層扔；如果在第2層沒碎，換到第3層扔…….如果第59層沒碎，換到第60層扔；如果第60層碎了，說明不會摔碎的臨界點是第59層。
在壞情況下，這個方法需要扔100次。
方法一：二分法
采用類似于二分查找的方法，把雞蛋從一半樓層（50層）往下扔。
如果枚雞蛋，在50層碎了，第二枚雞蛋，就從第1層開始扔，一層一層增長，一直扔到第49層。
如果枚雞蛋在50層沒碎了，則繼續(xù)使用二分法，在剩余樓層的一半（75層）往下扔……
這個方法在壞情況下，需要嘗試50次。
方法二：平方根法
如何讓枚雞蛋和第二枚雞蛋的嘗試次數(shù)，盡可能均衡呢？
很簡單，做一個平方根運算，100的平方根是10。
因此，我們嘗試每10層扔一次，次從10層扔，第二次從20層扔，第三次從30層……一直扔到100層。
這樣的好情況是在第10層碎掉，嘗試次數(shù)為 1 + 9 = 10次。
壞的情況是在第100層碎掉，嘗試次數(shù)為 10 + 9 = 19次。
不過，這里有一個小小的優(yōu)化點，我們可以從15層開始扔，接下來從25層、35層扔……一直到95層。
這樣壞情況是在第95層碎掉，嘗試次數(shù)為 9 + 9 = 18次。
假設優(yōu)的嘗試次數(shù)的x次，為什么次扔就要選擇第x層呢？
這里的解釋會有些燒腦，請小伙伴們坐穩(wěn)扶好：
假設次扔在第x+1層：
如果個雞蛋碎了，那么第二個雞蛋只能從第1層開始一層一層扔，一直扔到第x層。
這樣一來，我們總共嘗試了x+1次，和假設嘗試x次相悖。由此可見，次扔的樓層必須小于x+1層。
假設次扔在第x-1層：
如果個雞蛋碎了，那么第二個雞蛋只能從第1層開始一層一層扔，一直扔到第x-2層。
這樣一來，我們總共嘗試了x-2+1 = x-1次，雖然沒有超出假設次數(shù)，但似乎有些過于保守。
假設次扔在第x層：
如果個雞蛋碎了，那么第二個雞蛋只能從第1層開始一層一層扔，一直扔到第x-1層。
這樣一來，我們總共嘗試了x-1+1 = x次，剛剛好沒有超出假設次數(shù)。
因此，要想盡量樓層跨度大一些，又要保證不超過假設的嘗試次數(shù)x，那么次扔雞蛋的優(yōu)選擇就是第x層。
方法三：解方程法
x + (x-1) + (x-2) + … + 1 = 100
這個方程式不難理解：
左邊的多項式是各次扔雞蛋的樓層跨度之和。由于假設嘗試x次，所以這個多項式共有x項。
右邊是總的樓層數(shù)100。
下面我們來解這個方程：
x + (x-1) + (x-2) + … + 1 = 100 轉化為
(x+1)*x/2 = 100
終x向上取整，得到 x = 14
因此，優(yōu)解在壞情況的嘗試次數(shù)是14次，次扔雞蛋的樓層也是14層。
后，讓我們把個雞蛋沒碎的情況下，所嘗試的樓層數(shù)完整列舉出來：
14，27， 39， 50， 60， 69， 77， 84， 90， 95， 99， 100
舉個栗子驗證下：
假如雞蛋不會碎的臨界點是65層，那么個雞蛋扔出的樓層是14，27，50，60，69。這時候啪的一聲碎了。
第二個雞蛋繼續(xù)，從61層開始，61，62，63，64，65，66，啪的一聲碎了。
因此得到不會碎的臨界點65層，總嘗試次數(shù)是 6 + 6 = 12 < 14 。
本站文章版權歸原作者及原出處所有 。內容為作者個人觀點， 并不代表本站贊同其觀點和對其真實性負責，本站只提供參考并不構成任何投資及應用建議。本站是一個個人學習交流的平臺，網站上部分文章為轉載，并不用于任何商業(yè)目的，我們已經盡可能的對作者和來源進行了通告，但是能力有限或疏忽，造成漏登，請及時聯(lián)系我們，我們將根據(jù)著作權人的要求，立即更正或者刪除有關內容。本站擁有對此聲明的最終解釋權。
