应该怎么回答啊?

来源:百度知道 编辑:UC知道 时间:2024/05/22 02:01:59
有一栋100层高的大楼,给你两个完全相同的玻璃围棋子。假设从某一层开始丢下玻璃棋子就会破碎;那么怎么利用手中的两颗棋子,用一种什么样的最优策略知道这个临界的层高呢?
麻烦大家帮忙想想哦
大家都好厉害哦
这个是GOOGLE招聘的笔试题目啊

从低往高,每隔一个固定的层数(m)丢一次,假如在某个m层上(xm层)跌碎了(x≤100/m)
就退回到(x-1)m的那层,往上一层一层地扔,直到在y层上扔碎(y≤m-1)
这样总的次数就是x+y
在最坏的情况下,x=100/m且y=m-1,即扔到第100层的时候才碎,回退至(x-1)m层往上一层一层扔的时候直到99层都不碎,
带入m值可得总次数n=100/m+m-1

可得当m=10时,可以使n取值最小,也就是每隔10层扔一次,碎了退到下一个10层再一层一层地扔,最多只要扔19次

从第一层开始丢
若第一层碎,则停止
否则+1层继续丢
直到到达某一层,破碎。

其实就是从第一层开始穷举
如果要效率高的算法,不确定算法不能准确得出结论
确定的算法没想到

华罗庚教授创造了0.618实验法.你用10X0.618约6层.在6层扔,碎了从一层开始层层扔第二个.不碎,再用20层计算0.618约12层.碎了从7层开始层层扔第二个.以此类推,可快速找到碎裂的楼层.

我想,隔几层仍一下,比如隔X层仍一下,如果在NX的时候碎了,在从(N-1)X+1层仍起,直到找到哪个临界点至于X是几啊,我想想就是100/X+X尽可能的小就好,这样的题目我已经不会算拉,当做X是10了,那就隔10层仍一下,呵呵

http://blog.sina.com.cn/u/4aed4e750100066x
我朋友的博客上写的,和这个问题类似,写的很详细但我看不动:)

用goole