最近，看了一道看似簡(jiǎn)單的問(wèn)題，拋瓶子。題目的描述是這樣的：
一棟樓高為100層，有兩個(gè)瓶子，如何用最少的實(shí)驗(yàn)次數(shù)(從某層樓拋下一個(gè)瓶子，看會(huì)不會(huì)碎，記為一次實(shí)驗(yàn)。)確保測(cè)出瓶子從哪一層（最小層數(shù)）摔下來(lái)會(huì)碎？
這個(gè)問(wèn)題，看似簡(jiǎn)單，其實(shí)并不是，下面簡(jiǎn)單的說(shuō)下幾種思路。
二分搜索
這道題，我的第一反應(yīng)是二分搜索。
首先用第一個(gè)瓶子，在第50層樓實(shí)驗(yàn)，如果瓶子碎了，證明瓶子在1-49層范圍內(nèi)就有可能碎。接下來(lái)，就可以用第二個(gè)瓶子，從第一層開(kāi)始，逐層向上試驗(yàn)，直到瓶子破碎，就找到了摔碎瓶子的最小層數(shù)。如果實(shí)驗(yàn)到底49層，瓶子還沒(méi)碎，就說(shuō)明摔碎第一個(gè)瓶子的第50層是瓶子摔碎的最小層數(shù)。這種情況下，最壞共需要實(shí)驗(yàn)50次才能得到答案。
如果第一個(gè)瓶子在第50層沒(méi)有摔碎，那么就繼續(xù)在第75層實(shí)驗(yàn)。如果碎了，就接著用第二個(gè)瓶子檢查第51到第74層，和前面一種情況中，用第二個(gè)瓶子檢查第1到49層類似。這種情況下，最壞共需要24+1+1次，也就是26次才能得到答案。
如果在第75層實(shí)驗(yàn)，第一個(gè)瓶子還沒(méi)有碎，那么就應(yīng)該繼續(xù)在75+(100-75)/2=87層實(shí)驗(yàn)。。。
后面的情況和前面的大致類似。這種思路下，最多的實(shí)驗(yàn)次數(shù)，就出現(xiàn)在剛開(kāi)始在第50層實(shí)驗(yàn)時(shí)第一個(gè)瓶子破碎的情況，總共需要50次實(shí)驗(yàn)才能夠得出答案。顯然，這個(gè)答案不是那么讓人滿意。
簡(jiǎn)單的思路
另外，有一種，更為簡(jiǎn)單的思路，從第2層開(kāi)始，每?jī)蓪佑玫谝粋€(gè)瓶子做一次實(shí)驗(yàn)，如果碎了，用第二個(gè)瓶子在相鄰?fù)碌囊粚幼鰧?shí)驗(yàn)即可得出結(jié)論。如果沒(méi)碎，繼續(xù)往上兩層，用第一個(gè)瓶子做實(shí)驗(yàn)，直到頂樓或者瓶子破碎。這樣，也能夠得出結(jié)果。最壞的情況下，第一個(gè)瓶子在第100層摔碎，第二個(gè)瓶子要在第100層相鄰?fù)碌囊粚?，也就?9層，做實(shí)驗(yàn)，如果碎了答案就是99，如果沒(méi)碎，答案就是100。這樣，最壞的情況下，我們需要實(shí)驗(yàn)的次數(shù)是50+1=51次。
從這個(gè)方案來(lái)看，實(shí)際上，第一個(gè)瓶子主要是用來(lái)確定范圍，第二個(gè)瓶子用來(lái)精準(zhǔn)定位，這樣，如果稍微調(diào)整下第一個(gè)瓶子實(shí)驗(yàn)的跨度，就能對(duì)這個(gè)方案的開(kāi)銷進(jìn)行優(yōu)化。比如，每?jī)蓪佑玫谝粋€(gè)瓶子做一次實(shí)驗(yàn)，改成每3層做一次實(shí)驗(yàn)。這樣的話，最壞情況下所需要的實(shí)驗(yàn)次數(shù)就是100/3+2=35次。
可以發(fā)現(xiàn)，這里調(diào)整第一個(gè)瓶子實(shí)驗(yàn)的跨度，可以優(yōu)化實(shí)驗(yàn)的效率。如果我們假設(shè)第一個(gè)瓶子實(shí)驗(yàn)的跨度為每x層實(shí)驗(yàn)一次，最終的實(shí)驗(yàn)次數(shù)為y，那么就會(huì)有：
這個(gè)函數(shù)的圖像如下：
不難發(fā)現(xiàn)，這種方案下最小的實(shí)驗(yàn)次數(shù)出現(xiàn)在x為10的時(shí)候，這時(shí)候的試驗(yàn)次數(shù)為19。
到這里，得到的結(jié)果已經(jīng)比前面二分的思路，優(yōu)化了好多，然而，這里并不是最優(yōu)的結(jié)論，因?yàn)檫@里做了一個(gè)限制，就是說(shuō)，第一個(gè)瓶子在各次實(shí)驗(yàn)中的跨度是一樣的。如果去掉這個(gè)限制，說(shuō)不定會(huì)有更好的解決思路。
