转自:
问题: 一种石头,在某一高度扔下就会碎,在这个高度以下不会碎,高度以上一定碎。现在有4个石头,1000层的楼房,需要测定这个石头破碎的高度。求最少多少次一定可以测出来。
分析: 这道题我们应反过来考虑,就是用a块石头扔b次至多一定可分辨层数X(a,b)。 先从最简装的一块石头考虑,很显然, X(1,1) = 1 X(1,2) = 2 X(1,3) = 3 . X(1,i) = i 再考虑二块石头,显而易见 X(2,1) = 1 对于X(2,2),我们可这样考虑,当我们扔第一次后,有两种可能:破和不破. 如果石头破了,则 1,我们还剩1块石头. 2,我们下一次只需检查下面的楼层. 3,我们还剩1次机会. 即我们还可分辨下面的 X(1,1) 层. 如果石头没破,则 1,我们还剩2块石头. 2,我们下一次只需检查上面的楼层. 3,我们还剩1次机会. 即我们还可分辨上面的 X(2,1) 层. 我们知道,X(1,1) = 1.所以我们第一次从第二层开始扔,如果石头破了,则再测试第一层.如果没破则再测试第三层. 所以用2块石头扔2次至多一定可分辨 1 + X(1,1) + X(2,1) = 1 + 1 + 1 = 3 层. 不失一般性,我们考虑 X(2,i) 对X(2,i),我们这样考虑,当我们扔第一次后,有两种可能:破和不破. 如果石头破了,则 1,我们还剩1块石头. 2,我们下一次只需检查下面的楼层. 3,我们还剩i-1次机会. 即我们还可分辨下面的 X(1,i-1) 层. 如果石头没破,则 1,我们还剩2块石头. 2,我们下一次只需检查上面的楼层. 3,我们还剩i-1次机会. 即我们还可分辨上面的 X(2,i-1) 层. 则 X(2,i) = 1 + X(1,i-1) + X(2,i-1) 接下来我们考虑 X(i1,i2) 同样,对 X(i1,i2),我们还是这样考虑,当我们扔第一次后,有两种可能:破和不破. 如果石头破了,则 1,我们还剩i1-1块石头. 2,我们下一次只需检查下面的楼层. 3,我们还剩i2-1次机会. 如果石头没破,则 1,我们还剩i1块石头. 2,我们下一次只需检查上面的楼层. 3,我们还剩i2-1次机会. 即 X(i1,i2) = 1 + X(i1-1,i2-1) + X(i1,i2-1) 很明显 无论你有几块石头,扔一次只能测试一层. 即 X(i,1) = 1. 这样,我们可制出如下表: 扔的次数: 1 2 3 04 05 06 007 008 009 010 011 012 013 分辨层数: 一块石头: 1 2 3 04 05 06 007 008 009 010 011 012 013 二块石头: 1 3 6 10 15 21 028 036 045 055 066 078 091 三块石头: 1 3 7 14 25 41 063 092 129 175 231 298 377 四块石头: 1 3 7 15 30 56 098 162 255 385 561 793 1092 五块石头: 1 3 7 15 31 62 119 218 381 637 1023 六块石头: 1 3 7 15 31 63 126 246 465 847 1485 也就是说用4块石头扔12次至多一定可分辨793层,扔13次至多一定可分辨1092层. 答案: 1000层的楼房, 用4块石头,扔13次一定可测试出来.
==================================================================