找出小球不会被摔碎的最高楼层
你拿着两个质量一样的小球站在在一栋100层的大楼前。这两个小球可能很结实，就算是从100层大楼的楼顶掉下也不会摔破，也可能很易碎，在第1层楼摔下就破碎。在两只小球都被打碎以前，你用什么方法可以找出小球不会被摔碎的最高楼层？
- 上一篇：N根面条两两打结成圈的数目 EMC笔试题目
- 下一篇：Conway的天使魔鬼问题
回复列表
先拿第一个小球从第2层楼摔下，
若第一个小球破碎，则拿第二个小球从第1层楼摔下，若第二个小球也破碎，则小球不会被摔碎的最高楼层是0层；若第二个小球未破碎，则小球不会被摔碎的最高楼层是1层。
若第一个小球未破碎，则捡起第一个小球，
然后从第4层楼摔下，
若第一个小球破碎，则拿第二个小球从第3层楼摔下，若第二个小球也破碎，则小球不会被摔碎的最高楼层是2层；若第二个小球未破碎，则小球不会被摔碎的最高楼层是3层。
若第一个小球未破碎，则捡起第一个小球，
然后从第6层楼摔下，
依次类推……
若第一个小球破碎，则拿第二个小球从第1层楼摔下，若第二个小球也破碎，则小球不会被摔碎的最高楼层是0层；若第二个小球未破碎，则小球不会被摔碎的最高楼层是1层。
若第一个小球未破碎，则捡起第一个小球，
然后从第4层楼摔下，
若第一个小球破碎，则拿第二个小球从第3层楼摔下，若第二个小球也破碎，则小球不会被摔碎的最高楼层是2层；若第二个小球未破碎，则小球不会被摔碎的最高楼层是3层。
若第一个小球未破碎，则捡起第一个小球，
然后从第6层楼摔下，
依次类推……
同意、、
要是这样可以的话，那一个球岂不是也可以？
从1楼一直往上，哪层摔坏了就是哪层了呗。
从1楼一直往上，哪层摔坏了就是哪层了呗。
1楼的方案的确可行，但是效率可能不够高。如果小球不会被摔碎的最高楼层是100层，那就要尝试100次。
有一个更高效一些的方法，可以保证对于一个 n 层的楼房而言，至多经过 2 * sqrt(n) - 1 次就能找到小球不会被摔碎的最高楼层。对于本题而言，即是最多19次尝试就可以找到。方法如下：
先去10楼，丢下一个小球；
如小球碎了，就从1楼开始，用第二个小球逐层尝试，看在哪一层摔碎；
如果小球没碎，就去20楼丢下一个小球；
如果小球碎了，就从11楼开始，用第二个小球逐层尝试，看在哪一层摔碎；
如果小球没碎，就去30楼丢下一个小球；
如果小球碎了，就从21楼开始，用第二个小球逐层尝试，看在哪一层摔碎；
如果小球没碎，就去40楼丢下一个小球；
......
这样，最坏的情况是小球不会被摔碎的最高楼层是99楼，在这样的情况下需要试19次。
有一个更高效一些的方法，可以保证对于一个 n 层的楼房而言，至多经过 2 * sqrt(n) - 1 次就能找到小球不会被摔碎的最高楼层。对于本题而言，即是最多19次尝试就可以找到。方法如下：
先去10楼，丢下一个小球；
如小球碎了，就从1楼开始，用第二个小球逐层尝试，看在哪一层摔碎；
如果小球没碎，就去20楼丢下一个小球；
如果小球碎了，就从11楼开始，用第二个小球逐层尝试，看在哪一层摔碎；
如果小球没碎，就去30楼丢下一个小球；
如果小球碎了，就从21楼开始，用第二个小球逐层尝试，看在哪一层摔碎；
如果小球没碎，就去40楼丢下一个小球；
......
这样，最坏的情况是小球不会被摔碎的最高楼层是99楼，在这样的情况下需要试19次。
