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