1樓：陶鵬祥
intball
(intn)
}ball[i
]=min;
}return
ball[n
];}主要是根據公式 ball(n, 2) = Min }，而 k 的值可以為 [1, n]。
其中初始值 ball(0, 2) = 0，ball(1, 2) = 1 。
2樓：劉志彬
很多答主給出了14次的答案，我嘗試寫個簡單的版本。
不管是扔雞蛋還是玻璃球，要麼碎要麼不碎，所以本質上最少次數=最開始扔的樓層。舉個例子，如果最少次數為6次，那麼你就得從6樓開始，扔碎了，那樓層就鎖定在1-5樓，為了保險，只能從最低樓層慢慢往上才能鎖定樓層。最倒霉的情況就是在5樓，總共嘗試了6次。
首先假定最少x次可以找出，那在這x次裡面，我們需要能遍歷完這100層樓。
假設第一次沒碎，那你就用掉了一次機會了，剩下的就只有x-1次。
以此類推，第二次沒碎，那就只剩下x-2次了，第三次沒碎，就剩x-3次。
把總共x次能嘗試的樓層累加起來，就是乙個等差數列：
x + (x - 1) + (x - 2) + … + 1 = x(x+1) / 2
這時再把題目中的100樓帶入進去，也就是累加的值要》=100:
x(x+1) / 2 >= 100
解出方程:
x>=14
所以最壞情況下的最少次數為14次。
最優策略就是從14樓開始扔，然後27，39，50...
3樓：小小球球
def ball(n):
dp = [n] * n
dp[0] = 1
for i in range(1, nfor j in range(1, i + 1dp[i] = min(max(j, dp[i - j] + 1), dp[i])
print dp
return dp[n - 1]
print ball(100)
[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14]
動態規劃可得最優策略為14次。。
4樓：wudidididi
Binary serach 了解一下。 Worst case, 第一層就碎了， 100 -> 50 -> 25 -> 12 -> 6 -> 3 - > 1.
5樓：
在看到此問題下所有答案之前，我之想出了先從50層扔乙個球的方案。
如果第乙個球50層碎了，說明在1-49之間，第二個球再去從1層2層3層開始嘗試；如果50層沒碎，說明在51-100之間，從51開始往上嘗試。這樣最差情況下要試50次左右。
看了其他人的答案，感覺我這種方案是步長為50的方案……如果調整步長為10，那麼最差情況下是試10次找出碎的樓層，再在10層的區間找，是20次……
如果調整步長為20，最差是5+20=25次設步長為x，則最差次數=100/x + x，這個函式在第一象限的最低點貌似就是個10……
所以我覺得步長10的時候最優
6樓：徐風來
我草草的考慮了下：設以k層為最小單位來檢測。
如果考慮最壞情況，就大概是在最後乙個層級得出答案，就是100/k次（假設這裡是可以整除的，草草計算下），最壞的值就是100/k+k，得出是10左右
這題顯然不是考慮最壞情況，考慮乙個概率性即可。先考慮第乙個區間，如果是第一層掛掉，那麼就是k次可以得出，。。。如果k層掛掉那麼就是2次得出，求和。
如果在k-2k區間得出，所有的值都要加上1，一共大概有100/k個區間，最後把所有的可能都除以100，就是平均的概率，算出來發現還是k=10最優，這我就有點摸不到頭腦了，可能還得再細化的算一下。
7樓：mills
好像前面的答主回答的有點複雜，我來個通俗易懂的吧。考慮好以下兩點就比較容易了:
A:這個形象一點就像顯微鏡的兩個調焦螺旋，乙個粗調確定大範圍，乙個微調確定具體樓層。
B：不管什麼情況，最終粗調微調的次數總和不變。
我們用①號球確定範圍，②號球確定樓層。
(一)假設第一次範圍為k層且①號碎了，那麼①號球1次，②號球k-1次，合計1+k-1=k次。
(二)假設①號球第二次才碎，那麼①號球2次，為保證總次數不變②號球要丟k-2次，相當於這個範圍有k-1層，情況以此類推。
最糟糕情況就是要把100層都覆蓋，那麼所有次的範圍之和加上最後的微調次數要≥98(第一層沒高度，無意義，第100層也不用丟，所以是100-2)
k+(k-1)+(k-2)+(k-3)+……+3+2+1≥98
等差數列求和得
k*(k+1)/2≥98，解得k=14，也就是最多14次，也就是第乙個範圍內有14層。
注意:k在這裡即是總次數，也是第一次的層數。
①號球具體丟的層數就是15層，28層，40層……
8樓：
樓上很多想法，可能很正確。我思考了很久覺得答案應該為5次操作吧，不知道和 @bh lin的意思是否相同。
這個問題假設大概上面都已經說了，還要補充乙個，100中玻璃球必碎。最優策略的理解為【通過最少次操作必然可以遍歷在所有情況下解決問題】。
這個問題先變形一下，樓層數為N,問題變化為每層樓對應訊號乙個訊號（相同結果訊號相同），那麼問題變成求訊號突變發生在那一層樓。之後每次操作用1個探針探測得到乙個訊號，最壞的情況應該是2**n>=N，n為探測到突變值。
現在情況變為你有兩個探針，那麼應該情況是3**n>=N，n為探測到突變值。
3**5=243，3**4=81，雖然這個情況下和上面問題不同，有可能有乙個探測器會消失，問題由兩個探測器變為1個探測器的情況，但是我想可能依然是可以實現最優策略的，雖然我現在還沒有想明白。
9樓：bh lin
最近是不是到了面試季，看到好多經典面試題。
這個題目首先是關於「最優」的定義。
考慮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，最壞情況所需步數：
當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.
10樓：如花似玉
我們首先需要一些假設：玻璃球一定在1－100層底某一層恰好碎掉，而且概率服從平均分布。
我們給出的最優是指期望值最小的做法。如果是希望在最少的步數內一定能確定出樓層的，請參考其他人的答案。
我們的策略是首先選定一些特定的樓層，在這些樓層自下往上試驗第乙個玻璃球，直到破碎或者到達最後乙個特定的樓層，然後我們可以得到乙個區間，再在這個區間內從下往上試驗第二個玻璃球。
第乙個球：
假設第乙個球的試驗樓層為。令，那麼每次試驗落在到之間的概率為，其中，而我們得到這樣的區間的嘗試次數為。除非在樓層的時候都沒碎，此時我們可以確定恰好碎掉的樓層在到之間，次數為。
第二個球：
如果樓層落在到之間，恰好碎掉的樓層為，其中前個試驗次數分別為，而如果恰好碎掉的樓層為所需次數為次，無需再試驗層。因此這一步我們平均需要的次數為
。我們得到最後的步數的期望值為
記，則。
(1) 如果允許取任意正實數，我們知道全部相等時達到極小。此時
。(2) 但是實際上只能取半整數，容易驗證這些數至多相差1時達到極小值。令
的小數部分，那麼有個和個，
(3) 此外，我們還要求。當很大的時候，如果取值相等，將會小於這個範圍。這樣我們就需要將下標較大的適當地提高以滿足實際情況。
然而，我們知道如果將大於平均值的乙個數調大，而相應地小於平均值的某個數調小時，總的平方和會增大。因此，為了平方和盡量小，我們希望取值盡量靠近，而這樣的結果就是，或者說。這種情形實際上可以退化成的情形，所以我們可以不妨假設，，。
(4) 我們計算
我們發現k<13時，它大於，於是g(k)" eeimg="1"/>，所以在k-1不能達到極小。因此g的極小值出現在k>=12。
k=12時，mu=9/12,g(k)=2062.
，此時有8個14和5個13。
，此時有8個14和6個13。
，此時有9個14和6個13（某些情形會退化）。
某些讀者可能會注意到一點，因為第乙個球有可能在樓層不破碎，這時看上去我們應當將到樓層再進行一次細分，把這個不破碎的球再利用起來。然而實際上由於我們得到的已經是極小值了，因此這種情形不會影響我們的結論，而且我們得到或2或3，簡單計算可以發現再次細分不會影響次數的期望值，因此還是變成了我們得到的情形。
結論：當且僅當且滿足我們給定的情形時，
《玻璃球遊戲》中烏托邦似的學院在那個世界中有何存在的意義？
尤其是必須學會放棄前輩一代代學者們認為值得為之奮鬥的一切利益 輕而易舉地迅速獲得金錢 榮譽 公眾的尊敬，受到報刊的讚美，與銀行家和工業家的女兒聯姻，過豪華奢侈的生活。作家們想的是著作暢銷，得諾貝爾獎和美麗的鄉村別墅名醫學家想要佩戴勳章和擁有穿號衣的僕人 教授們則想有出自豪門的太太和富麗堂皇的客廳 化...
用鏡子做乙個球內部景象會是怎樣？
西內 這是我在這顆鏡子球裡的第一天，頭很痛，只記得自己剛吃完六塊的聖代就暈過去了，醒來就到了這。一 我能看到的地方都是光亮，且還有自己奇奇怪怪的映像。這裡面不熱，倒也不涼，在這裡白天黑夜全憑臆想。難道我要在這孤獨終老？24小時全看著白色的亮光。二 漸漸的我適應了這裡的景象，呲牙咧嘴的樂趣已經消亡。包...
打羽毛球有個用球拍把地上的球撈起來的動作是怎麼練出來的？
我原本也不會，但2個月沒打球了，這週三去打。輪不到我打的時候試了一下，發現還能夠已經有點感覺了，可以勾起來一些。其實用的力非常輕微，基本上不用力就可以勾起來了。關鍵是要找感覺，找技巧。 chou墨飛沫 哈哈，我能說我花了2 4天時間才練OK嗎，平均每次就練個半個小時左右，每天練個3 4次。沒什麼要點...