用2個玻璃球找到從一100層的大樓的某一層落下剛好會摔碎，如何制定最優策略？

01-11

有一棟100層高的大樓，給你兩個完全相同的玻璃球，假設從某一層開始丟下玻璃球會摔碎，怎麼利用手中的兩個玻璃球，用什麼最優策略（最少次數）知道這個臨界的層是第幾層

最近是不是到了面試季，看到好多經典面試題。

這個題目首先是關於「最優」的定義。

考慮best-worse case最壞情況下最優。也就是說假如你的演算法是從第一樓逐樓往上試，那麼相應最壞的情況是在100樓破，相應的是一百次。

這種情況下最優策略也就是匿名用戶提到的從14樓開始遞減間隔的辦法，worst case 需要14次。

解法：

記n層s球的問題為Q(n,s),對應的最壞情況最優解為ba(n,s);

一些簡單的結果：

(0) ba(m,2)&>=ba(n,2) 如果m&>n,trivial.

(1) ba(n,1)=n

當你只剩下一個球，為了能夠檢驗出臨界點，你只能逐層檢驗，最壞情況下所需的檢驗次數為n；

(2)ba(1,2)=1

(3)iterative: 假設你從k層扔球，有兩種情形：

球破。那麼臨界層必然在1層到k-1層之間，剩下一球，由(1)得出，最壞情況最優所需的步數為: 1 + ba(k-1,1)=k;
球不破。問題變成n-k層兩球的問題Q(n-k,2), 所以最壞情況最優所需步數是：1+ba(n-k,2);

綜合1，2，最壞情況所需步數： $ba(n,2)=max{k,1+ba(n-k,2)}$

當k=1+ba(n-k,2)的時候，

ba(n,2)=ba(n-k,2)+1

結合(2),(3),由(2)迭代得知:

當n = 1+2+3+...+k

ba(n,2)=k

當k=13時， n=91；

ba(100,2)=max(9,1+ba(91,2))=14

所以100層，最壞情況最優策略的步數是14.

我們首先需要一些假設：玻璃球一定在1－100層底某一層恰好碎掉，而且概率服從平均分布。

我們給出的最優是指期望值最小的做法。如果是希望在最少的步數內一定能確定出樓層的，請參考其他人的答案。

我們的策略是首先選定一些特定的樓層，在這些樓層自下往上試驗第一個玻璃球，直到破碎或者到達最後一個特定的樓層，然後我們可以得到一個區間，再在這個區間內從下往上試驗第二個玻璃球。

第一個球：

假設第一個球的試驗樓層為 $s_1,ldots,s_{k-1}$ 。令 $s_0=0,s_k=100$ ，那麼每次試驗落在 $s_{i-1}$ 到 $s_i$ 之間的概率為 $a_i/100$ ，其中 $a_i=s_i-s_{i-1}$ ，而我們得到這樣的區間的嘗試次數為 $i$ 。除非在樓層 $s_{k-1}$ 的時候都沒碎，此時我們可以確定恰好碎掉的樓層在 $s_{k-1}$ 到 $s_k$ 之間，次數為 $k-1$ 。

第二個球：

如果樓層落在 $s_{i-1}$ 到 $s_i$ 之間，恰好碎掉的樓層為 $s_{i-1}+1,ldots,s_i$ ，其中前 $a_i-1$ 個試驗次數分別為 $1,2,ldots,a_i-1$ ，而如果恰好碎掉的樓層為 $s_i$ 所需次數為 $a_i-1$ 次，無需再試驗 $s_i$ 層。因此這一步我們平均需要的次數為

$frac{1}{a_i}(1+cdots+(a_i-1)+a_i-1)=frac{a_i+1}{2}-frac{1}{a_i}$ 。

我們得到最後的步數的期望值為

$E=sum_{i=1}^{k-1} frac{a_i}{100}(i+frac{a_i+1}{2}-frac{1}{a_i})+frac{a_k}{100}(k-1+frac{a_k+1}{2}-frac{1}{a_k})$

$=0.005(sum_{i=1}^{k-1}((a_i+i+1/2)^2-(i+1/2)^2)+(a_k+k-1/2)^2-(k-1/2)^2-2k)$

記 $b_i=egin{cases}a_i+i+1/2,1le ile k-1\ a_k+k-1/2,i=k end{cases}$ ，則

$s=sum_{i=1}^k b_i=100+(k^2+2k-2)/2$ 。

$200E=sum_{i=1}^k b_i^2-k(4k^2+12k+11)/12$

(1) 如果允許 $b_i$ 取任意正實數，我們知道 $b_i$ 全部相等時達到極小。此時

$b_i=99/k+k/2+1,$

$200E=f(k)=k(99/k+k/2+1)^2-k(4k^2+12k+11)/12$

$=frac{99^2}{k}+198+99frac{1}{12}k-frac{k^3}{12}$ 。

(2) 但是實際上 $b_i$ 只能取半整數，容易驗證這些數至多相差1時達到極小值。令

$mu={99/k+k/2+3/2}$ 的小數部分，那麼 $b_i$ 有 $kmu$ 個 $s/k-mu+1$ 和 $k(1-mu)$ 個 $s/k-mu$ ，

$200E=g(k)=frac{99^2}{k}+198+99frac{1}{12}k-frac{k^3}{12}+kmu(1-mu)le f(k)+k/4$

(3) 此外，我們還要求 $b_ige i+1/2,b_kge k-1/2$ 。當 $k$ 很大的時候，如果 $b_i$ 取值相等，將會小於這個範圍。這樣我們就需要將下標較大的 $b_i$ 適當地提高以滿足實際情況。然而，我們知道如果將大於平均值的一個數調大，而相應地小於平均值的某個數調小時，總的平方和會增大。因此，為了平方和盡量小，我們希望 $b_i$ 取值盡量靠近，而這樣的結果就是 $b_k=k-1/2$ ，或者說 $a_k=0$ 。這種情形實際上可以退化成 $k-1$ 的情形，所以我們可以不妨假設 $s/k-mu+1ge k-1/2$ ， $sge k(k-1/2)$ ， $k(k-3)le 198,kle 15$ 。

(4) 我們計算

$f(k-1)-f(k)=frac{99^2}{k(k-1)}+frac{k(k-1)}{4}-99$

我們發現k&<13時，它大於 $k/4$ ，於是 $g(k-1)>g(k)$ ，所以 $g$ 在k-1不能達到極小。因此g的極小值出現在k&>=12。

k=12時，mu=9/12,g(k)=2062.

$k=13,mu=8/13,g(k)=2060$ ，此時 $a_1,ldots,a_{12}+11,a_{13}+11$ 有8個14和5個13。

$k=14,mu=8/14,g(k)=2060$ ，此時 $a_1,ldots,a_{13}+12,a_{14}+12$ 有8個14和6個13。

$k=15,mu=9/15,g(k)=2060$ ，此時 $a_1,ldots,a_{14}+13,a_{15}+13$ 有9個14和6個13（某些情形會退化）。

某些讀者可能會注意到一點，因為第一個球有可能在 $s_{k-1}$ 樓層不破碎，這時看上去我們應當將 $s_{k-1}$ 到 $s_k$ 樓層再進行一次細分，把這個不破碎的球再利用起來。然而實際上由於我們得到的已經是極小值了，因此這種情形不會影響我們的結論，而且我們得到 $a_k=1$ 或2或3，簡單計算可以發現再次細分不會影響次數的期望值，因此還是變成了我們得到的情形。

結論：當且僅當 $k=13,14,15$ 且 $a_i$ 滿足我們給定的情形時， $E=E_{min}=10.3$

這題看似直白，其實並不容易。這裡的不容易是兩個層面的，一是給出一種最優的策略，二是證明該策略是最優的，顯然第二層「不容易」要更不容易一些。

在正式回答這個問題之前，先對原題做一些補充說明：

暫時假設在每個樓層球破碎的概率是一致的。在沒有外加信息的情況下，假設均勻的概率分布是最合理的方式（熵最大原理），但這種假設並不能被看作是先驗的，我把這種假設稱作「均勻分布假設」。事實上，如果把這個題目看成物理問題，考慮球摔碎的力學過程的話，在每個樓層摔碎的概率就更沒有理由都相等。為了簡明起見，以及為了接下來突出核心問題，暫時認可「均勻分布假設」。
（如同題目中標註的，）最優指的是嘗試次數最少。如果把最優理解為其他含義，比如「跑上跑下的總樓層數最少」，那顯然會得到不同的結論。

最終得到的結果將依賴於破碎樓層的概率分布，以及對於「最優」的詮釋。

再詳細回答前，先給出一種（相對）最優的策略：

第一個球在沒扔碎前，按照如下樓層嘗試：13 25 36 47 56 65 72 79 85 90 94 97 98 99 100直到確定一個「不碎-碎」的樓層區間：比如在47層沒碎，在56層碎了。
第二個球在第一個球確定的「不碎-碎」區間中，逐層向上嘗試：比如球最終會在50層碎，那第一個球確定了（47，56]的區間，第二個球依次嘗試：48 49 50，將發現球在49層沒碎，在50層碎了，於是得到臨界層50。

圖1：不同臨界樓層時，該最優策略給出的嘗試次數

關於上述策略，有必要做幾點解釋：

該策略給出的平均嘗試次數為10.31次。（註：此處10.31為精確值；「平均」指的是對球在每一層砸碎的可能情況下的嘗試次數的平均值。）
該策略的大致思路是顯而易見的：通過第一個球確定區間，再通過第二個球逐層搜索。由於要求一定要找到臨界層，所以第二個球必須採用需要逐層往上的方式，以免漏過臨界層而把僅有的一個球摔碎；
所以，這個問題的關鍵在於找到第一個球嘗試的樓層序列，定義為F

現在正式解答問題：

如上所述，該問題可以粗略的簡化為尋找第一個球的嘗試序列，但顯然可能的序列的總數非常之多，它們構成了一個非常龐大的集合（或者空間），以至於幾乎很難處理。所以首先要找到處理這個問題的方法論：

@曾興旺給出了一個重要的思路，在幾乎是無數種可能的序列挑選出一組特殊的子集，然後用解析的方法求出最優化的解。該特殊的子集要求第一個球的嘗試層數是等間隔的：如10 20 30 40 ......，或者6 12 18 24......等。經過一系列的分析，@曾興旺給出了在這個子集中的最優解：

10 20 30 40 50 60 70 80 90 100

經過計算，該策略給出的平均嘗試次數為10.9，已經比較接近我在之前給出的結果了。我把這個方法稱為「等間隔模型」。

這種方法論最漂亮的地方在於從一個複雜而龐大的空間選取一個子空間，用類似泛函的方法求出子集中的極值，非常類似於量子力學中的變分法，給出的結果可以視作最優策略（即「基態」）的上界。

但這個方法也有明顯的問題，即選取的某個子空間很有可能不包括真正的最優解。換句話說，對等間隔模型而言，真正的最優解的序列是否是等間隔的，並不是一件顯然的事情，它很有可能（也的確）是錯的。

圖2：不同臨界樓層時，等間隔模型給出的嘗試次數2.

第二類方法是一種非常「不靠譜」的做法，就是「猜」。當然這裡的猜並不是胡猜，它依據一定的邏輯推理。

從分析上述「等間隔模型」的問題開始，將指引我們去「猜」出某種最優的解。對於等間隔模型給出的最優策略，如果真正的臨界樓層比較低的時候，這種策略的效率較高，比如：臨界樓層是5層，僅嘗試一次就可以將區間確定在9層之內；但當臨界樓層比較高的時候，比如95層，那麼按照該策略，需要從10 20 30開始一直嘗試到100層，（共10次），才能將區間確定在9層之內。換句話說，此時，多用了9次嘗試才得到了和低樓層時一樣的區間，這顯然是相對低效的。

通過如上分析，我們可以得知關於最優策略的一些信息：即序列F的間隔應該遞減。這樣對於較高的臨界樓層的情況，雖然第一個球嘗試的次數不可避免的會比較多，但已經將樓層限定在了一個比較小區間內，這樣將減少第二個球的嘗試次數。

可以隨手寫出一個符合這種條件的序列F，比如：

14 27 39 50 60 69 77 84 90 95 99 100

（除了最後一個間隔，）該序列的間隔依次比上一個間隔小1，第一個數取14（或者13），可以大致保證間隔依次減小到1時剛好到100。此時的平均嘗試次數為10.39。

再比如：

12 22 34 45 55 64 72 79 85 90 94 97 99 100

（除了第一個間隔，）該序列的間隔依次比上一個間隔小1，且剛好停在100。此時的平均嘗試次數為10.35。

可以看到這兩個序列都給出了比等間隔模型更好的結果，並且很接近我給出的最終結果，表明上述分析是相當合理的。

還可以有其他的方法，比如窮舉法，寫出所有100以內遞增的序列，但顯然實在太多了。

還有類似共軛梯度法等傳統的最優化方法，雖然可以寫出一個矢量（即序列F）

F(1) F(2) F(3) ......F(100)

該序列可以有重複的數，比如F(20)=F(21)=......=F(100)=100，同時要求單調遞增的約束條件。但即便如此，似乎也有一種無從下手的感覺。

這正是這個題目有意思的地方，因為很難找到一種特別合適的方法來處理它。

所以只能另闢蹊徑。需要找到一種方法，它應該要能自適應的依據優化的要求，在龐大的參數空間中逐漸搜索到最優解。最終我使用了遺傳演算法（的思路）

（註：本人非計算機專業出身，對於遺傳演算法更是知之甚少，只是在梅拉妮·米歇爾的《複雜》一書中看到了遺傳演算法，對其強大的功能以及別樣的思路印象很深。之前也沒有自己寫過相關的演算法，就這這個有意思的題目，按照遺傳演算法的思路，寫了一小段程序，勢必不入方家之眼，還希望得到專業人士的指點。）

非常簡單地重複一下我的演算法的思路：

生成一系列隨機的序列，這些序列都符合遞增到100的要求；

計算每個序列的平均嘗試次數，找到最好的兩個序列；

讓這兩個序列「雜交」生成子代，即子代序列中每一位數都有50%的幾率沿襲「父」或「母」序列中相應位數的數值；

子代序列中每一位數有30%的幾率發生變異，即數字增加或減少1；

對子序列重複步驟2；

直到最終收斂在一種（一組）最優的策略上。

遺傳演算法的結果是很不錯的，大約在幾百代就可以給出最優解，對應的平均嘗試次數是10.31次。由於遺傳的隨機性，每次給出的最優結果的策略都略有不同，比如：

13 25 36 46 56 64 72 79 85 90 94 96 98 99 100

或者

14 27 38 48 57 66 73 79 85 90 93 96 98 99 100

等序列能給出同樣的平均嘗試次數。

這一系列的最優策略的共同點就是是都有著遞減的間隔，以及初始的嘗試樓層都是13或者14，與前文的猜想給出的定性考慮一致。

補充兩點：

我將程序運了一晚上，遺傳了 $10^{5}$ 代，並沒有得到更好的結果；
另外，遺傳演算法不是證明，我們沒法通過遺傳演算法得知這究竟是不是最優的解。

我沒法保證我的演算法是最好的，甚至不能保證該演算法是正確的，這種演算法甚至有可能在原則上錯過真正最優的策略。又或者有某種非常直接的做法，可以給出最優的解；又或者有某種非常巧妙的做法，可以證明某個解是最優的；又或者還有著更好的答案——這些我都不知道。

附：matlab代碼

1. 根據序列F計算各臨界樓層的嘗試次數的程序：

function T=zhihu_floor_result(F,N) % return try time T for all possible crashing floor % F is sequence of testing floor number % N is total floor number F=[0 F]; T=zeros(1,N); for ii=1:N t1=find(F&

2.遺傳演算法：
未免有誤，貽笑大方，暫時不貼出來。

/*

 *

 * m個球，n層樓，最少幾次（假設為最壞情況下的最少次數，不是平均次數）

 * 能判斷從哪層樓開始扔球會壞掉，假設球摔壞的概率與樓層高度無關且每層相等,

 * 並且不一定肯定有一層能摔壞

 * 遞推公式：

 * b(m,n) = min{ max{ b(m-1,k-1)+1, b(m,n-k)+1 } }

 *

 *

 */

#include &

int max(const int a, const int b){

    return a&>b ? a : b;

}

int min(const int a, const int b){

    return a&>b ? b : a;

}

void mball_nfloor(int m, int m);

int main(int argc, char **argv){

    fprintf(stdout, "

**********************mball_nfloor(4, 100)************************

");

    mball_nfloor(4, 100);

    fprintf(stdout,

"

******************************************************************

");

    fprintf(stdout, "

**********************mball_nfloor(1, 100)************************

");

    mball_nfloor(1, 200);

    fprintf(stdout,

"

******************************************************************

");

fprintf(stdout, "

**********************mball_nfloor(4, 1)**************************

");

    mball_nfloor(4, 1);

    fprintf(stdout, "

******************************************************************

");    return 0;

}

//b(m,n) = min{ max{ b(m-1,k-1)+1, b(m,n-k)+1 } }

//n&>=1,m&>=2,1&<=k&<=n
//For convenience, we handle m=1, n=0 separately
void mball_nfloor(int m, int n){
    if(m&<=0 || n&<=0)
        return;
    int result[m+1][n+1];
    int temp_min = n+1;
    int temp_max = 0;
    //for n==0 and n==1
    for(int i=0;i&<=m;i++){
        result[i][0] = 0;
        result[i][1] = 1;
    }
    //for m==0 and m==1
    for(int i=0;i&<=n;i++){
        result[1][i] = i;
        result[0][i] = 0;
    }
    if(m&>1  n&>1){

        //start from 2 balls

        for(int a=2;a&<=m;a++){
            //start from 1 floors
            for(int i=1;i&<=n;i++){
                for(int k=1;k&<=i;k++){
                     temp_max = max(result[a-1][k-1]+1, result[a][i-k]+1);
                    temp_min = min(temp_min, temp_max);
                }
                result[a][i] = temp_min;
                temp_min = n+1;
            }
        }
    }
    for(int i=1;i&<=m;i++){
        fprintf(stdout, "
======%d個球，%d層，每種樓層各種丟球方法中最壞情況下的最少丟球次數======
", i, n);
        for(int j=1;j&<=n;j++){
            fprintf(stdout, "%d	", result[i][j]);
        }
        fprintf(stdout, "
");
    }
}


因為只有兩個球，所以要保證有解的情況下，策略是，利用第一個球，用盡量少的次數找到一個（不碎－碎）區間，利用第二個球，找出臨界值。所以重點在於如何利用第一個球找出最小空間，如在50層試一次，如果50層球碎了，那麼第二個球就必須從第一層開始一層一層遞進，才能找到臨界層，否則如第一層未碎，直接第三層嘗試，第三層碎了，則無法得知臨界值是2還是3.
    此時，此題變為，在如題所述的條件下，把（0－100）分割成a個100/a個連續數字的區間，總次數為（a＋100/a）次（100/a，為總10個集合需搜索次數的平均值），當a＝10時，該值最小，值為20，即第一個球10層10層地遞增時，最多19次（9個截點即可將分出10個線段），即可找到臨界值。
    即第一個球從10層開始，如果10層碎了，則第二個球從第一層開始逐層往上找到臨界值。如果10層沒碎，則第一個球在第20層開始嘗試，依次遞歸到90層。
ps-------------------------------------------------------------------------
感謝後來的同志指出問題，因為有初值的存在（就是落在不同區間內段內的破碎層，在劃分區段時有實際已經使用的初始值不同情況出現），所以到了切割10段後，本題就由演算法題變為了概率題，，可以縮小落在高低區間之間的次數差距（平均法是各個區間從低到高依次遞增），來達到優化期望值，最理想的方案，應該是10個區間，每個區間內的期望次數也是相等，相當於方差為0時，效果最優（大學時期沒好好學概率論，哈哈）。我在估算不會超過11時，就忽略了初值與期望優化，實際上。當此時N足夠大時，理論期望可接近N的平方根，最優方法的期望次數能做到比平均法少最多到1次（概率方面的知識儲備流失嚴重，沒法做嚴謹的公式論證，希望有更嚴謹的論證）

三個假設：
由於是100層的大樓，所以假設地基是水泥地等堅硬是合理的；
由於題目沒有給出特別說明，所以假設玻璃球是普通玻璃球是合理的；
假設玻璃球自由下落，沒有初速度；
三個先驗結論：
基於上述三個假設，認為在五樓及以上玻璃球一定碎裂(小時候玩彈珠遊戲，力氣大的時候能一下把彈珠撞爛碎裂，若彈珠自由往前滾動，能有十幾米，滾動摩擦係數小於一，所以才有這個先驗條件)；在一樓高度太低(人身高)一定不會碎裂(力氣小打彈珠不會裂)；由於玻璃珠的滾動，在樓上扔下玻璃珠若沒碎裂就滾彈到遠處再也找不到，無法用第二次，若碎裂則能找到，從而判斷是否碎裂；
那麼只剩下二三四樓，第一次選擇3樓：
1～若第三層不碎裂，則用第二個玻璃球檢驗第四層；若第四層不碎裂，說明臨界樓層是五層；若第四層碎裂，說明臨界樓層是四樓；
2～若第三層碎裂則檢驗二樓是否碎裂，若不碎裂說明臨界樓層是三層；若碎裂說明臨界樓層是二層；
於是整個方法用到的玻璃球的期望是兩個，剛好用完所給條件完美解決問題。至於一百層，呵呵，被繞進去的孩子不少。
轉載請註明出處！

樓上很多想法，可能很正確。我思考了很久覺得答案應該為5次操作吧，不知道和 @bh lin的意思是否相同。
這個問題假設大概上面都已經說了，還要補充一個，100中玻璃球必碎。最優策略的理解為【通過最少次操作必然可以遍歷在所有情況下解決問題】。
這個問題先變形一下，樓層數為N,問題變化為每層樓對應信號一個信號（相同結果信號相同），那麼問題變成求信號突變發生在那一層樓。之後每次操作用1個探針探測得到一個信號，最壞的情況應該是2**n&>=N，n為探測到突變值。
現在情況變為你有兩個探針，那麼應該情況是3**n&>=N，n為探測到突變值。
3**5=243，3**4=81，雖然這個情況下和上面問題不同，有可能有一個探測器會消失，問題由兩個探測器變為1個探測器的情況，但是我想可能依然是可以實現最優策略的，雖然我現在還沒有想明白。

經典面試題動規啊。

早年的信息學國家集訓隊論文《鷹蛋》就是這道題目的最優解
動態規劃

動態規劃 = =

只有兩個玻璃球的話，我大概能給你一個區間。
第一個玻璃球從50層下落（樓下的注意腦袋，拉起警戒線）。
如果沒有碎，則，
第二個球從75層下落，
第二個也沒有碎，
則，第一個從88層下落。
第一個還沒有碎。
則第二個從96層下落。

  推薦閱讀：


※產品經理該不該畫原型？原型設計上誰負責？
※非線性優化中的KKT條件該如何理解？
※編譯器優化過程具體是做了些什麼,優化後的程序速度能提高多少百分比?
TAG:數學 | 優化 | 概率論 | 概率論與數理統計 | 物理思考 |