据说是google校园招聘的题目

cugb_cat

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

偶用二分法只能得出个范围，哪位高手能得出具体是哪一层啊～～～

isjfk

他没说你不能到楼底下把棋子拣上来再扔...

ssffzz1

这样吗，先从第一层扔，扔到那层碎，那层就是了。

invalid

看看这位的分析：
http://blog.csdn.net/jiaomeng/archive/2006/12/08/1435226.aspx

cugb_cat

原帖由 ssffzz1 于 2006-12-11 13:59 发表
这样吗，先从第一层扔，扔到那层碎，那层就是了。

呵呵，或许可以这样钻空子。。。。

koolcoy

要看到底什么为优了：时间最少？用玻璃球最少？

cugb_cat

原帖由 invalid 于 2006-12-11 14:12 发表
看看这位的分析：
http://blog.csdn.net/jiaomeng/archive/2006/12/08/1435226.aspx

这个最强～～～

softsongs

感觉确实有一个最优解，
1。首先如果只有一个玻璃球的情况，最多需要50次，
     一个球的情况，可以两层两层试，如果2层不碎，就试第4层，第4层不碎就是第6层，依此类推。如果到第n层碎了，那么临界层就是n-1层，因为n-2层的结果必定是不碎。

2。考虑有两个球的情况，其实只要看成我们有两次机会就可以了，相当于做两遍相同的题目。
     这次我们挑选的楼层就不是每隔两层了，而是每隔4层，
    依次为，4，8，12，16 .... 4n, (n>=1)
    公式为 a(1) = 4, a(2) = 8 ... a(n) = 4n;
    如果在第i层碎了，那么说明到a(i－1) 都不会碎，显然，我们只要考虑a(i-1) 到a(i)之间的楼层就可以了。
又，a(i) - a(i-1) = 4, 由递归公式得。
    因此，第二个球应该在楼层a(i-1) + 2 处扔下，如果碎了，说明临界层为a(i-1) + 1, 否则临界层为a(i) -1;

证明完毕；

cugb_cat

原帖由 softsongs 于 2006-12-11 15:47 发表
1。首先如果只有一个玻璃球的情况，最多需要50次，
     一个球的情况，可以两层两层试，如果2层不碎，就试第4层，第4层不碎就是第6层，依此类推。如果到第n层碎了，那么临界层就是n-1层，因为n-2层的结果必定是不碎。

这一条我感觉怎么不太对啊～～～
如果是在第4层碎了的话，那你能确定是第3层为临界面还是第4层为临界面吗？

ArXoR

题目的意思应该是
找出一个固定的方案A, 使得对于目标t为任意[1,100]里的数的时候, 找出t要扔的最多的次数 最小
因为t不同的时候, 方案A要扔的次数不一定一样, 我们就是要使得这个最多的次数最小
动态规划就好了

1. 
   
2. F(l,r,k)为 确定目标t是否在[l,r]中且手上有k个棋子的最少扔子次数, 有状态转移方程:
   
3.              /      (r-l+1)             (k = 1)
   
4. F(l,r,k) =   |      1                   (l = r)
   
5.              |      0                   (l > r)
   
6.              \      1+min{max{F(l,mid-1,k-1),F(mid+1,r,k)}}    (l<=mid<=r)
   

复制代码

所求就是F(1,100,2).

Please correct me if I'm wrong.