100楼层和两个玻璃球

﹏ヽ暗。殇╰゛Y 2022-08-08 00:53 125阅读 0赞

有一栋100层高的大楼，给你两个完全相同的玻璃球。假设从某一层开始，丢下玻璃球会摔碎。那么怎么利用手中的两个球，用什么最优策略知道这个临界的层是第几层？？？

2012年腾讯实习生笔试的时候，有一个智力题跟这个一样，只不过就是描述不一样而已。我记得大概是这样：1到100之间有一个数字，一个人猜，另外一个人给一些辅助信息，如果这个人猜的数比指定的数小，则会告诉他小了，如果比指定的数大了，则会告诉他比这个数大了，并且以后再猜的话，只会告诉对错，不告诉大了还是小了。

仔细想想，这两个题一样吧～～。下面我借助别人的分析我来仔细分析一下。

每次肯定是由低的楼层往高的楼层尝试，直到在楼层f(k)，第一个球已经碎掉了，记录上一个尝试的楼层为f(k-1),在此楼层，玻璃球不会碎，所以接下来要尝试 f(k-1)+1,f(k-1)+2,f(k-3)+3, ....,知道有一个楼层碎了，这个楼层就是解啦，最坏的是到达f(k)-1 层。

以下分析转自：[http://blog.csdn.net/xiaohai0504/article/details/6941467][http_blog.csdn.net_xiaohai0504_article_details_6941467]

接下来的解决方案就很容易想出了：既然第一步（确定临界段）的投掷数增加不可避免，我们就让第二步（确定临界层）的投掷数随着第一步的次数增加而减少。第一步的投掷数是一次一次增加的，那就让第二步的投掷数一次一次减少。假设第一次投掷的层数是f，转化成数学模型，f+(f-1)+...+2+1就表示从f开始猜，每次的增量都比前一次的曾量减1的情况下，最后猜的那个数（即 f+(f-1)+...+2+1 ），按照提议要求f+(f-1)+...+2+1>=99，即f(f+1)/2>=99(第一次测试点选择100层是无意义的，必然会碎，所以无任何测试价值，所以第一次测试点k是1-99中的一个数)，解出结果等于14。丢下第一颗鸡蛋的楼层就分别是 14 ， 27 ， 39 ， 50 ， 60 ， 69 ， 77 ，84 ， 90 ， 95 ， 99 。

有一栋100层高的大楼，给你两个完全相同的玻璃球。假设从某一层开始，丢下玻璃球会摔碎。那么怎么利用手中的两个球，用什么最优策略知道这个临界的层是第几层？？

解题思路：

假如只有一个球，那很显然，只有一个办法：从第一层开始投，如果没碎再试第二层、第三层.....

现在有两个球，我们应该利用第一个球缩小临界楼层所在的楼层范围，可能会想到第一个球先从50层开始投，如果碎了，再用最后一个球从第一层开始投，最多到49楼肯定可以找到临界楼层，如果没碎那就说明临界楼层在50-100中，此时继续尝试75楼....

可惜，上面的方法并非是最好的。因为最坏情况的投掷次数分布不均匀。比如，如果50楼碎了，此时最坏情况下需要尝试50次，如果50楼没碎，而75层不管是否碎了，最坏情况也只需要尝试25次，也就是说，50楼投掷结果不同，所需最坏情况下的次数也不同，这就是分布不均匀的意思，那是否有办法让其分布均匀，也就是说假如在f层投，不管碎还是不碎，继续时最坏情况所需次数也是一样的。这样才能使最坏情况下所需投掷次数达到最小。

假设一开始从第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次了。

金子分析：我来解释一个不等式右侧为什么是99呢，其实使用99还是100最后结果是一样的，只不过99说明理解的深刻，因为如果你都已经到了99层了，可以玻璃球还是没有碎，那么答案就肯定是100啦，所以100就不用猜了，如果面试的时候说一下这个99和100的关系，就说明你够聪明，至于到底用100还是99，看考官吧，不同的人理解不一样。

首次选择14，那么最高可以判断到呢，按照上面的递减数列，14 ， 27 ， 39 ， 50 ， 60 ， 69 ， 77 ，84 ， 90 ， 95 ， 99 ，102，104，105。一共是14次，最后是到105了，按照上面99和100的分析，虽然是14次猜，但是最后一个猜到了105，可知如果105还是不碎的话，那么肯定是106，106是铁定的了，不用猜了就知道，所以14次最大可以判断到106，这样15次的话就要从15开始猜，并且如果107层的话，那么需要15次。

比如到27层，玻璃碎了，则要从15开始一层一层的尝试，比如26是解的话，那么猜的序列就是 14，27，15，16，17，18，19，20，21，22，23，24，25，26，一共14次。

[http_blog.csdn.net_xiaohai0504_article_details_6941467]: http://blog.csdn.net/xiaohai0504/article/details/6941467