问题:
一种石头,在某一高度扔下就会碎,在这个高度以下不会碎,高度以上一定碎。现在有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次一定可测试出来.
转载声明:本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/kittyjie/archive/2009/10/27/4732415.aspx
分享到:
相关推荐
比如100层楼2个鸡蛋输出结果14:表示2个鸡蛋测试100层楼以获得最高安全层的最小次数为14次,测试方法也有输出,即第一个鸡蛋每段测试层数分别为14,13,,,,1.第二个鸡蛋每隔一层测试一次。另外程序中带有证明过程...
楼里面有一部可以通达所有楼层的电梯,每上一层楼需要uu秒钟,下一层楼需要dd秒,每个楼层会停ss秒。目前电梯在第N(1 \le N \le 200)N(1≤N≤200)层的地面上。若某个楼层没有上下需求,则电梯运行中会跳过该楼层。...
有一栋楼共100层,一个鸡蛋从第N层及以上的楼层落下来会摔破, 在第N层以下的楼层落下不会摔破。给你2个鸡蛋,设计方案找出N,并且保证在最坏情况下, 最小化鸡蛋下落的次数。 求鸡蛋承受楼层高度,java版
模拟程序还包含一个调度器(Scheduler),它通过随机设置两个时间开始每一天:第一个时间是一个人首次走到1层,并按下楼层按钮召唤电梯时间,第二个时间是一个人首次走到2层,并按下按钮召唤电梯时间。每个时间都是...
设计一个5层电梯楼层显示器,按下1-5号按键可以分别实时显示电梯所在的楼层信息,并让电梯楼层数字向上或向下运行到所按下的楼层号。采用8*8点阵显示器、按键、驱动芯片74LS245实现。 楼层显示器:可以采用88点阵...
goole曾用来做面试题,国内一些大型互联网公司也用过,这个文档是原版论文 ...现在有座100层的建筑,要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。要求给出最坏情况下的最少测试次数。
现在是疫情期间,被动裁员,呆在宿舍没事儿做,在YouTube上看见了李永乐老师的一个双蛋问题的视频,就是众所周知的动态...设M(t,n)为在从t层楼,n个蛋的情况下需要抛投的最少次数,情况有多少种呢。当然是t种,从每一
电梯楼层显示电路.。。。。。。。。。。。。。。。。。
板的层数一般不会事先确定好,会由工程师综合板子情况给出规划,总层数由信号层数加上电源地的层数构成。 一、电源、地层数的规划 电源的层数主要由电源的种类数目、分布情况、载流能力、单板的性能指标以及单板的...
100_floors_详细图文攻略(81-100层+附加楼层1-5)
自动电梯控制器,电梯内有八个输入按钮响应用户的上下楼层请求,并有八段数码管显示电梯当前所在楼层位置
本实验使用板上的四个开关来模拟电梯的叫梯按键,其中每个按钮有两个状态0和1,4个组成了电梯的叫楼层,将这4位二进制数字看成8421BCD码,转换成十进制数字。对于电梯按键,当没用用户叫梯时,叫梯的数码管BIT5(G1...
一套20层楼综合布线图,各楼层的综合布线,DWG格式 一套20层楼综合布线图,各楼层的综合布线,DWG格式 一套20层楼综合布线图,各楼层的综合布线,DWG格式
于是某人想出了一个新的电梯调度算法:由于大楼楼层不高,因此每次电梯从一楼往上走时,只允许电梯停在某一层,然后其他人在从本层爬楼梯到达各自的目的地;在一楼的时候,每人选择自己的楼层,电梯应根据每楼层的...
有一座10层高的建筑物,搬运工小李需要搬运一些相同的包裹来往于各楼层之间。小李可以不搬运任何包裹而上楼下楼... 现在请你编写一个程序,求出小李完成工作所需的最少上楼层数m(下楼层数不计),并且输出其搬运路径。
硬件工程师教程,权威经典,详尽实用,内容面向基础,是电子专业不可缺少的教材。 想让你的硬件知识更加牢固吗,想让你的硬件技术更上一层楼吗?想就不要错过。
你可以选择空格键,这使得电梯运行到要求的下一层,当系统检测到这层楼有人要出去,或是要进来,那么电梯停止、开门,等候出去的人出完,进来的人进来(当然,这是不允许超载的)。你也可以选择H或是h来查看帮助菜单...
是男人就下100层C#编写11111111111
小游戏 下一百层楼 c# c/s模式 详细编写了下一百层得小游戏,游戏测试无问题,绘图
电梯控制30层楼3部电梯的算法当从电梯外按下按钮(pressButton 方法)时,执行以下算法: 请求最近的“途中”电梯。 这是最近的电梯,将通过请求的楼层如果没有“途中”电梯,请请求最近的“空闲”电梯。 这是最近的...