|
|
有限層數(shù)和蛋數(shù)，求即使最壞情況下需要的最少判斷次數(shù)兩個(gè)軟硬程度一樣但未知的雞蛋，它們有可能都在一樓就摔碎，也可能從一百層樓摔下來(lái)沒(méi)事。有座100層的建筑，要你用這兩個(gè)雞蛋確定哪一層是雞蛋可以安全落下的最高位置�？梢运に閮蓚�(gè)雞蛋。（參見(jiàn)兩個(gè)雞蛋--一道Google面試題）
這是典型的動(dòng)態(tài)規(guī)劃問(wèn)題。假設(shè)f[n]表示從n層樓找到摔雞蛋不碎安全位置的最少判斷次數(shù)。假設(shè)第一個(gè)雞蛋第一次從第i層扔下，如果碎了，就剩一個(gè)雞蛋，為確定下面樓層中的安全位置，必須從第一層挨著試，還需要i-1次；如果不碎的話，上面還有n-i層，剩下兩個(gè)雞蛋，還需要f[n-i]次（子問(wèn)題，實(shí)體n層樓的上n-i層需要的最少判斷次數(shù)和實(shí)體n-i層樓需要的最少判斷次數(shù)其實(shí)是一樣的）。因此，最壞情況下還需要判斷max(i-1,f[n-i])次。
狀態(tài)轉(zhuǎn)移方程：f[n] = min{ 1+max(i-1,f[n-i]) | i=1..n } 初始條件: f[0]=0（或f[1]=1）實(shí)際上，兩個(gè)雞蛋的情況用數(shù)學(xué)方程就可以解決，前提是你知道該怎么扔：
一種想法是第一個(gè)雞蛋折半搜索，如100層的樓，先從50層扔下去，如果碎了則第二個(gè)雞蛋在1~49層樓中自底向上線性搜索；如果沒(méi)碎則第一個(gè)雞蛋再?gòu)?5層扔。如果這次碎了則第二個(gè)雞蛋在51~74層樓中自底向上線性搜索；如果還沒(méi)碎則第一個(gè)雞蛋再?gòu)?8層扔，依此類推。這種方法不是最優(yōu)，因?yàn)樽顗那闆r下安全位置恰好是49層，需要嘗試50次。
正確的方法是先假設(shè)最少判斷次數(shù)為x，則第一個(gè)雞蛋第一次從第x層扔（不管碎沒(méi)碎，還有x-1次嘗試機(jī)會(huì)）。如果碎了，則第二個(gè)雞蛋在1～x-1層中線性搜索，最多x-1次；如果沒(méi)碎，則第一個(gè)雞蛋第二次從x+(x-1)層扔（現(xiàn)在還剩x-2次嘗試機(jī)會(huì)）。如果這次碎了，則第二個(gè)雞蛋在x+1～x+(x-1)-1層中線性搜索，最多x-2次；如果還沒(méi)碎第一個(gè)雞蛋再?gòu)膞+(x-1)+(x-2)層扔，依此類推。x次嘗試所能確定的最高樓層數(shù)為x+(x-1)+(x-2)+...+1=x(x+1)/2。
比如100層的樓，只要讓x(x+1)/2>=100，得x>=14，最少判斷14次。具體地說(shuō)，100層的樓，第一次從14層開(kāi)始扔。碎了好說(shuō)，從第1層開(kāi)始試。不碎的話還有13次機(jī)會(huì)，再?gòu)?4+13=27層開(kāi)始扔。依此類推，各次嘗試的樓層依次為
1427 = 14 + 1339 = 27 + 12...99 = 95 + 4100現(xiàn)在推廣成n層樓，m個(gè)雞蛋：
還是動(dòng)態(tài)規(guī)劃。假設(shè)f[n,m]表示n層樓、m個(gè)雞蛋時(shí)找到摔雞蛋不碎的最少判斷次數(shù)。則一個(gè)雞蛋從第i層扔下，如果碎了，還剩m-1個(gè)雞蛋，為確定下面樓層中的安全位置，還需要f[i-1,m-1]次（子問(wèn)題）；不碎的話，上面還有n-i層，還需要f[n-i,m]次（子問(wèn)題，實(shí)體n層樓的上n-i層需要的最少判斷次數(shù)和實(shí)體n-i層樓需要的最少判斷次數(shù)其實(shí)是一樣的）。
狀態(tài)轉(zhuǎn)移方程：f[n,m] = min{ 1+max(f[i-1,m-1], f[n-i,m]) | i＝1..n }初始條件：f[i,0]=0（或f[i,1]=i），對(duì)所有i
|
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
