神马文学网一个经典算数题(转)我是看不懂不过觉得有意思- 逝去的荣光 - 新浪BLOG
来源：百度文库 编辑：神马文学网 时间：2024/04/28 15:25:21
问题:
一种石头，在某一高度扔下就会碎，在这个高度以下不会碎，高度以上一定碎。现在有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次一定可测试出来.
一种石头，在某一高度扔下就会碎，在这个高度以下不会碎，高度以上一定碎。现在有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次一定可测试出来.
一个经典算数题(转)我是看不懂不过觉得有意思- 逝去的荣光 - 新浪BLOG
转一个超经典的！！ - 做最好的自己 - 新浪BLOG
一个感人的故事-龙龙 - 新浪BLOG
RE:西方大学的校训,您觉得怎么样? - 人间秋雨 - 新浪BLOG
一个希望小学的逝去
一个老股民的炒股经历- 兰心蕙质妹妹 - 新浪BLOG
一个大专生的心理独白- 蚊子 - 新浪BLOG
日语就是汉语的一个“方言” - 翟华 - 新浪BLOG
一个女人超级完美的一生 - 柯云路 - 新浪BLOG
告诉你另外一个真实的中国 ( 1) - 新浪BLOG
一个女人超级完美的一生 - 柯云路 - 新浪BLOG,
三顾茅庐---耍大牌的经典 - 加农张大爷 - 新浪BLOG
06年最经典的只言片语! - 王宝军 - 新浪BLOG
毛泽东最经典的词句 【图文】- 谦受益 - 新浪BLOG
管理学上的十条经典法则-云中舞 - 新浪BLOG
毛泽东最经典的词句 【图文】- 谦受益 - 新浪BLOG
经典个性的玩具收藏 - JackPOON_阿邦 - 新浪BLOG
管理学上的十条经典法则-云中舞 - 新浪BLOG
管理学上的十条经典法则-云中舞 - 新浪BLOG
谁的红色，何来经典？- 张鸣 - 新浪BLOG
最新男女朋友的经典称呼 - 营养师飞翔︾ - 新浪BLOG
06年最经典的只言片语! - 王宝军 - 新浪BLOG
经典女人的十大气质 - 宇灏 - 新浪BLOG
谁的红色，何来经典？- 张鸣 - 新浪BLOG