N個雞蛋從M樓層摔(2個雞蛋從100層摔)

NO IMAGE

一、題目:
  有一棟樓共100層,一個雞蛋從第N層及以上的樓層落下來會摔破, 在第N層以下的樓層落下不會摔破。給你2個雞蛋,設計方案找出N,並且保證在最壞情況下, 最小化雞蛋下落的次數。

二、思路:
  先假設,最小的次數為x次。
  首先在x層摔,那麼會出現兩個結果:
  1、碎了,為了找出那一層碎了,第二個雞蛋必須從1~x-1進行遍歷的摔
  2、沒碎,那麼第二次就在x (x-1)樓層摔。

為什麼是x x-1樓層呢?
首先我們已經假設了通過x步我們就能得到答案,現在我們在x層已經用了一次了,那麼就只剩下x-1步了。所以我們選擇x (x-1)層,如果碎了,我們就能通過x-2步,遍歷x 1~x (x-1)-1的所有樓層。

  3、如果在x (x-1)樓碎了,那麼同1,遍歷x 1~x (x-1)-1
  4、沒碎,那麼同2,就在x (x-1) (x-2)層摔
  …
  最後我們將會得出這樣一個樓層公式x (x-1) (x-2) … 1 = x(x 1)/2。
  這個公式有什麼意義呢?
  有, x(x 1)/2 >= 100,這樣才能順利的解除x。
  有人說,x(x 1)/2 = 99就可以,如果雞蛋在99層都沒碎,那麼必定是100層。 我想說誰告訴你記得一定會碎!
  那麼我們就順利的解除 x=14。

三、擴充套件
  此題還有一個擴充套件,就是為N個雞蛋從M層摔找出最小值。
  那就不是很好手解了,所以寫了程式碼,使用動態規劃原理。動態規劃式子如下:

f[n][m] = 1 max(f[n-1][k-1],f[n][m-k]) k屬於[1,m-1]
解釋下原理:
1、當手裡有n個的時候,雞蛋從k層往下摔,如果破了,那麼手裡只有n-1雞蛋了,那麼就需要測試f[n-1][k-1]樓層。或者更通俗好理解點的,我們運用2個雞蛋100樓層的題目舉例子。以上式子變為:f[2][m] = 1 max(f[1][k-1],f[2][m-k])
  那麼當手裡有2個雞蛋的時候,在k層摔,碎了。那麼現在手裡也就只有一個雞蛋了,此時我們必須遍歷1~k-1找出第一次碎的樓層。所以為1 f[1][m-k],前面的1代表在k層的操作。
2、沒破,那麼手裡還有n個雞蛋,那麼需要測試k 1~m這些樓層。

此時我想問下,當手裡有2個雞蛋測試1~m-k層和手裡有2個雞蛋測試k 1~m有什麼區別?
有人說有,因為樓層越高越容易碎,那其實是你個人的想法罷了。其實並沒有區別,所以第一個公式可以寫為f[n][m-k]。

最後附上程式碼,為了理解方便,而不必從陣列從0開始而困擾,這裡就空間多開了點,所以如果拿去用的話,可以優化下:

public class Eggs{
public int countMinSetp(int egg,int num){
if(egg < 1 || num < 1) return 0;
int[][] f = new int[egg 1][num 1];//代表egg個雞蛋,從num樓層冷下來所需的最小的次數
for(int i=1;i<=egg; i  ){
for(int j=1; j<=num; j  )
f[i][j] = j;//初始化,最壞的步數
}
for(int n=2; n<=egg; n  ){
for(int m=1; m<=num; m  ){
for(int k=1; k<m; k  ){
//這裡的DP的遞推公式為f[n][m] = 1 max(f[n-1][k-1],f[n][m-k]) k屬於[1,m-1]
//從1-m層中隨機抽出來一層k
//如果第一個雞蛋在k層碎了,那麼我們將測試1~k-1層,就可以找出來,也即1 f[1][k-1]
//如果第一個雞蛋在k層沒有碎,那麼我們將測試k 1~m也即m-k層,
//      這裡也是重點!!!! 
//      現在我們手裡有2個雞蛋,要測試m-k層,那麼我想問,此時和你手裡有2個雞蛋要測試1~m-k層有什麼區別?
//      沒有區別!是的在已知k層不碎的情況下,測試k 1~m層的方法和測試1~m-k沒區別,所以可以寫成 1 f[n][m-k] 其中1表示為 在k層的那一次測試
f[n][m] = Math.min(f[n][m],1 Math.max(f[n-1][k-1],f[n][m-k]));
}
}
}
return f[egg][num];
}
public static void main(String[] args) {
Eggs e = new Eggs();
System.out.println(e.countMinSetp(2,100));
}
}

參考文章:
100層樓2個雞蛋,如何得知雞蛋能承受幾層的撞擊
兩個雞蛋100層樓(DP)