100層樓扔2個雞蛋、3個雞蛋……

NO IMAGE

原題目

    現有2個雞蛋,樓高100層,假設從n層樓及以上扔下會摔碎,n層以下不會,那麼怎樣扔能以最小的次數得到n?

分析

    最先想起來的是二分法的題目:100層最少需要扔多少次雞蛋才能求得n?答案是ceil(log2(100))=7 。不過現在只有兩個雞蛋,這種方法就不行了。採用二分法的話,如果1號蛋在50層碎了,那剩下一個雞蛋只能從1層開始慢慢扔了,需要扔1 49 = 50次。

    另外一種容易想起來的就是,1號蛋每兩層扔一次,1、3、5、7……假設7層碎了,那2號蛋在6層再扔一次即可確定n。需要n/2 2次,最多需要扔51次。進而,如果1號蛋每m層扔一次,同樣的策略最多需要扔100/m m-1次。m取10,最壞情況下次數最小,為19次。

聰明的方法

    一種方法是限定扔的次數,看在最壞的情況下最多能在樓高多少層的情況下找出n。

    例如,限定最多扔15次,那麼第一次在15層扔。碎的情況下可以使用2號蛋最多14次確定n,如果沒有碎,則還剩下最多14次機會。這一次再隔14層(即15

14層)扔,同樣的,如果碎掉,可以使用2號蛋最多13次確定n,如果沒有碎,還剩下最多13次機會。那麼繼續,可以再隔13層扔……最後如果只剩一次,機會,則正好可以再確定一層樓。即總共可以確定 15 14 13 …… 1 = 120層樓。

    可以歸納出,限定最多扔e次,則最多可以處理的樓層數為:n (n-1) (n-2) …… 1 = n*(n 1)/2。令可處理的樓層數大於100,得到n = 14。

動態規劃解法及原題擴充套件

    從上面這種方法看到,採取隔m層扔的方法,最優的m值是隨總的樓層數變化的,每一步間隔層數應該是變化的。如果用cnt[p][2]表示樓共有p層,2個雞蛋情況下需要扔的次數,第一次從k層扔下,如果蛋碎了,總次數為cnt[k-1][1] 1,如果沒有碎,總次數為cnt[p-k][2] 1,綜合考慮這兩種情況下的結果,需要取這兩個值中的最大值。

    即有:cnt[p][2] = min{ max ( cnt[p-k][1] 1, cnt[p-k][2] 1) ,for k = 1,2,……p}

    其中,1個雞蛋情況下p層樓需要扔的次數為p。

    這種動態規劃的方法可以很輕易的擴充套件到多個雞蛋,比如已知p層樓2個雞蛋的答案,3個雞蛋的答案由下式就可以得到:

    cnt[p][3] = min{ max ( cnt[p-k][2] 1, cnt[p-k][3] 1) ,for k = 1,2,……p}

    假設e個雞蛋,p層樓,那麼建一個p*e的陣列,從第一列開始填就行了,複雜度為O(p^2 * e)。