100楼层2个手机有关问题及其推广(百度面试题目)
一个楼层有100层,已知手机在其中的某一层摔下就会坏,现在有两个一样的手机,请问,最少能摔几次保证一定找出那个极限的楼层值.(从101层掉下必坏).
我们把有n个手机的问题用Q(n)表示,下面将分别考虑问题.
问题:
所谓的最少次数是什么意思
分析:
所谓的最少次数是指要给出一个算法,按照这个算法,无论如何都能保证在给定的步数内找出来(不论这个手机的极限层楼是几楼).有些同学可能说最少是1次,因为比如我第一次从1楼把手机向下丢下去,并且手机坏了,则说明只需要最少一次.其实,这并不是题目所说的最少的意思.如果第一次从1楼丢下去,并且手机不坏呢?这样还是一次么?所以说,最少一次是根本不成立的.要明白最少次数的意思,并不是说在某一次特例中成立的最少次数(一定是1),而是说,要保证在那个求出的最少次数之内一定能找出那个极限的楼层值(而不论它是多少).
题目隐含的信息:
题目中其实隐含着一个重大的信息,就是如果手机没有坏的话,就能再用它来摔第二次,如果坏了就不能用了.因为无法通过摔一个坏手机判断当前摔下的楼层是否超过最大的那个极限值.
Q(1) 分析:
当只有一个手机的时候,我们显然只能从1楼开始一层一层地试,在最差的情况下一直要到100层,也就是说,我们的Q(1)=100.为什么呢,显然,如果我们在某一次从 x楼丢下手机,并且手机没坏,则下一次的时候我们丢的楼层肯定要大于x(否则没有意义的,因为在 x楼都没有坏,则小于x楼也不会坏的).并且,肯定不会大于 x+1,否则设下一次丢的楼层是 y(y>x+1),如果下一次在y层丢下的时候手机坏了,此时我们无法判断是x+1,x+2......y-1 这y-x-1( 大于1)个楼层中的哪一个楼层是手机的极限值,因为我们已经没有手机了.
所以,如果只有一个手机的时候,我们只能依次从1到100一次一次地丢.换句话说,如果我们知道手机在x和y层中的某一层丢下会坏,则我们只有从 x到y一个一个地试,也就是说,要测试y-x+1次.我们设有k个手机,且允许么t次可以确定的手机的极限楼层的范围是F(k,t),则知F(1,t)=t.(由上的讨论可知).
Q(2)分析:
我们不妨设最丢n次就可以.并且设第一 个手机的序列是(这里假设的是如果第一个手机一直没有坏,如果它在Xk那里坏了,则不再使用第一个,此时已经知道了手机在X(k-1)和X(k)层之间坏掉的.
显然,一定要X(k)-X(k-1)+k<=n,因为,如果第一个手机在丢X(k)层是坏掉了,则知道手机是在[X(k-1)+1, X(k)]之间的的某一个楼层坏掉了或者都没有坏掉,即我们遍历一下即可,此时因为此剩下一个手机,所以一定要丢X(k)-X(k-1)次,另外由于从X1一直丢到X(k),第一个手机已经丢了k次,所以总共丢了X(k)-X(k-1)+k次,因为已经假设了最少n次可以搞定,所以有X(k)-X(k-1)+k<=n.于是知道X(k)<=n+(n-1)+(n-2)+...+(n-k+1)显然X序列一定要不小于100,也就是说n+(n-1)+(n-2) +...+1>=100,即最小的n要满足n>=14, 得到了第一个手机丢的序列是14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100,这样,可以知道手机如果第一次就坏了,则用第二个手机在[1,13]之间丢13次再加上第一个手机1次,共14次.在27时坏一样的有12+2.....
根据以上分析,有F(2,t)=t*(t+1)/2;即2个手机丢t次可以确定的范围是t*(t+1)/2,所以最少的次数要满足t*(t+1)/2>=100.
Q(3)分析
一样地,设第一个手机的序列是同样地设n次是最少的,则由于F(2,t)=t*(t+1)/2,则有X(k)-X(k-1)<=F(2,
n-k+1),即知F(3,t)=F(2,t)+F(2,t-1)+F(2,t-2) +.....F(2,1),最后得到的最少的满足
F(3,t)>=100 的t即是所求的.
..............
Q(m)分析
一样地,有F(m,t)=F(m-1,t)+F(m-1, t-1)+ F(m-1, t-2)+...+F(m-1,1),并且,最少的次数也是最少的满足F(m,t)>=100的t.(这其实是一个递归的过程)
说明:
转载请标明出处,这是作者自己研究出的结果,不是转自其它地方的哦.
如果有问题可以提问.
- 1楼ppppppppp20093天前 18:23
- 为什么不是折半呢
- Re: wind_2008_06_293天前 20:44
- 回复ppppppppp2009n你第一次丢50,如果手机坏了呢?那就不能再用了,明白了不?