Re: [問題] 擲杯問題

看板Inference (推理遊戲)作者stimim (qqaa)時間15年前 (2009/06/16 19:34)推噓4(4推 0噓 3→)

留言7則, 5人參與討論串3/3 (看更多)

※ 引述《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)