给你两个球，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次了。
依次类推.....
在第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
回复(5)
我觉得用二进制思维解就可以了，第一次测试64层，往最大测试次数那一端思考（如果层数在64-100之间测试次数会更小），第二次测试32层，第三次测试16层，第四次测试第8层，第五次测试第4层，第6次测试第2层，第七次测试第1或3层，最多七次。
发表于 2020-08-14 22:21:39
回复(2)
编辑于 2020-07-07 11:47:32
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
