※ 引述《teves (teves)》之銘言： : ※ 引述《brains (不認識)》之銘言： : : 一種杯子, : : 若在第 N 層被摔破, 則在任何比 N 高的樓層均會破; : : 若在第 M 層不破, 則在任何比 M 低的樓層均不破. : : 現在給你兩個這種杯子, 讓你在100層樓高的建築作測試, 要求用最少的測試次數找出 : : 恰巧會使杯子摔破的樓層. : : --------------------------- : : 這問題若po過我會自D : 以最大試驗次數最小來看 : 我認為是先丟 : 14,27,39,50,60,69,77,84,90,95,99這幾層直到破 : 另一個杯子依序試中間的區段 : 最多14次 這題可以換一種想法， 如果你有 k 個杯子，而且你可以做 t 次實驗， ( k,t>=1 ) (也就是你最多可以讓杯子破 k 次，你最多可以丟 t 次杯子) 定義一個 function f(k,t) 代表此狀態下最多可以確定多少層樓 Ex f(1,t) 時，因為我們只有一個杯子， 破了就沒了，所以只能從 1F , 2F 慢慢往上試， 直到破了或是 t 次機會都用掉為止 因此最多可以確定 t 層樓 => ｆ（１,ｔ）＝１ 另外，t=1的時候，因為只能丟一次，所以只能確定一層樓 ｆ（ｋ,１）＝１ 這樣的話，當我們有 k 個杯子 可以做 t 次實驗時 應該要從幾樓丟下去呢？ 若 f(k-1,t-1) = a , f(k,t-1) = b 我們把杯子從a+1樓丟下去，如果破了的話，不用擔心 因為我們可以肯定要找的樓層會落在 1~a 之間， 而且我們知道用 k-1 個杯子，做 t-1 次實驗可以找到 1~a 之間的某一樓 如果沒破，那代表我們要找的樓層比 a+1 還要來的高 另外，我們用 k 個杯子，做 t-1 次實驗，可以找到 1~b 之間的某一樓 但是現在的起點由 a+1 開始算，因此可以確定 (a+2)~(b+a+1) 之間的某一樓 所以我們知道 f(k,t) = f(k-1,t-1) + f(k,t-1) + 1 再來就是把表格寫出來囉： k=1 k=2 ---------------------------------- t = 1 1 1 2 2 3 3 3 6 4 4 10 5 5 15 6 6 21 7 7 28 8 8 36 9 9 45 10 10 55 11 11 66 12 12 78 13 13 91 14 14 105 <= 超過 100 了，因此最少做 14 次實驗 用這種方法只有有心，多少個杯子多少層樓都可以算出來～ 如果可以解 f(k,t) = f(k-1,t-1) + f(k,t-1) + 1 的遞回式的話， 當然可以算得更快～ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.157.150 ※ 編輯: stimim 來自: 61.228.159.214 (06/17 21:04)