擲杯問題 - 推理遊戲

※ 引述《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 的遞回式的話，

當然可以算得更快～


--