首页 > 试题广场 > 给你两个球,100层楼,每个球在一定高度扔下去会碎,怎么用最
[问答题]

给你两个球,100层楼,每个球在一定高度扔下去会碎,怎么用最少的次数给判断是几层楼能把求摔碎?

 (答案转自网络)假设一开始从第k层投,如果坏了,那么第二个球可以在剩下的k-1层一定能用k-1次确定哪层坏,再加上第k层的那次,所以总共k次。如果第k层没有坏,那么第一个球在第k层的基础上再加k-1层(注意不是k层,原因见后面),所以第二次从2k-1层投下,在k,k+1,k+2,……,2k-2,2k-1中则有k-2层,所以用k-2次才能找出,再加上原来的那两次,还是共用了k次(为了保持总共还是k次,所以上面只能加k-1层)
依次类推.....
在第2k-1层基础上再加k-2层,在第3k-3层基础上再加k-3层,……,依次类推,一定能加到在第某层的基础上再加2层,最后再原来的基础上面还能再加1层,到目前为止,设为第n-1层,如果第n-1层坏了,那么就是第n-1层,如果没有坏,根据已知题说某一层能摔碎球,那么在第n-1层上面有且仅还有一层就是刚摔坏的层(此时不需要实际投,而是直接推理得出),这时用的次数还是k次(最不理想的结果),所以k次能测最多n层,由上面的解说,可知n-1=k+(k-1)+(k-2)+(k-3)+……+2+1=k(k+1)/2,得n=k(k+1)/2+1,由上面可知n=100(层),k次最多能推测k(k+1)/2+1(层),所以k(k+1)/2+1≥100,得k(k+1)≥198,且k的最小整数为14,所以最多14次就能找出题目中的那层。
补充:由上得知,第一次在14层投,第二次在第27层投,则依次为14 27 39 50 60 69 77 84 90 95 99。还能得出14次最多能测得到106楼,只不过题目中给了100楼,如果是107楼,那么就需要15次了。
编辑于 2019-04-22 15:33:20 回复(2)
首先:对半,第一次球碎了,那就需要50次才能知道最坏情况。
怎样在最坏的情况下最小?
设需要X次那么 第一次在X层,因为X碎了则0~X最坏有X-1次。
那么下一次就是X+(X-1)处,因为这里碎了,最坏也是X次。    
同理....有(X+1)*(X)/2  等差数列求和  结果是14 向上取正
发表于 2019-11-23 21:24:28 回复(0)
对半摔

发表于 2019-08-17 10:59:57 回复(1)
<p>二分查找法</p>
发表于 2020-05-18 23:18:23 回复(0)
动态规划是不也可以来一下子?
发表于 2019-10-24 09:03:47 回复(0)