原题: 有一个100层高的大厦,你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎,用你手中的这两个玻璃围棋子,找出一个最优的策略,来得知那个临界

有一个100层高的大厦,你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎,用你手中的这两个玻璃围棋子,找出一个最优的策略,来得知那个临界层面。 

 

分析：

一共有一百层，实际的高度只有99层的高度，用x表示楼层高度，x的范围范围0-99，楼层用f loor表示， x和楼层的转换为 floor = x +1,将设我每次都以某个固定的值step(表示楼高),来步进测试楼层。

 

1.setp*K (k=1),如果第一个球破了，那么就要用第2个球从0-step来测试,而且肯定能测试到。

                    如果第一个球没有破，那么就测试 2.

2.setp*K+1 ,如果第一个球破了，那么就要用第2个球从step+1 - step*(k+1)来测试,而且肯定能测试到。

                   如果第一个小球没有破，那么就测试2.

 

k表示进行第几次步进测试.

 

 

还是没想清楚

写道

http://www.iteye.com/topic/249567

armorking 写道
chenpingtai2008 写道
1。现有一百层高楼和两个棋子，棋子从X层上掉落摔到地面刚好摔碎（即X层以下是摔不碎的）
请问至少需要多少次摔棋子试验就一定能够找到X层是第几层？（棋子摔碎了就不能再用了）


至少需要18次摔棋子试验就一定能够找到X层是第几层


这是个查找问题
当可以有无数个棋子的时候，可以用2分（3分...）查找获得O[XlogX]的性能
当棋子只有一个的情况下，只能从第2楼开始一层一层往上试进行线性查找
注意到棋子只有2个
所以，第一个棋子可以每隔n层试验一次，这个棋子第n*k层摔碎以后，
再从第n*(k-1)+1层开始试验第2个棋子，最多需要试验n-1次就可以得到X
所以需要的次数是(X/n)+n-1
而如果k达到(X/n)的最大值的时候第一个棋子仍然没有摔碎的话
剩下的楼层显然不足n-1层
所以，用(X/n)+n-1次试验一定能够知道X
于是，得到如下表达式
y = (X/n)+n-1
其中y就是一定能查找到X的次数

当n = X的平方根的时候，y取最小值
注意到n是整数
所以，当X是整数的平方的时候，min(y)=X的平方根*2-1
当X不是整数的平方的时候，min(y)=X的平方根*2

X在1-100的范围内min(y)的最大值为19

不过，在这里，题目有一点模糊的地方：
站在第100层的地板上扔棋子，实际的高度是第99层天花板的高度
而从1楼的地板上扔棋子是没有意义的
所以，实际上X的范围应当是1-99，
于是得出结果是18次

先从14层扔（碎了试1-13）
再从27层扔（碎了试15-26）
再从39层扔（碎了试28-38）
再从50层扔（碎了试40-49）
再从60层扔（碎了试51-59）
再从69层扔（碎了试61-68）
再从77层扔（碎了试70-76）
再从84层扔（碎了试78-83）
再从90层扔（碎了试85-89)
再从95层扔（碎了试91-94）
再从99层扔（碎了试96-98）
最后从100层扔（如果确认临界层肯定存在的话，这步都可以省了）。

 

 

 

 

评论

2 楼 sst330381 2011-11-18  

     

1 楼 sst330381 2011-11-18