1.有1栋100层高的楼和两颗玻璃球。在一定的高度摔下玻璃球将会摔碎。请给定一个方法来确定玻璃球摔碎的临界楼层。并说明该方法的最好情况，最差情况以及方法的复杂度（楼层为N层时）。
分析：由于只有两个球，那么二分法、三分法就不行了，比如在50层丢一个，被摔坏。然后在25层丢另外一个，同样被摔坏，此时根本无从找到问题答案。
其次想到的是分段，用第一个球寻找损坏区间，然后用第二球去遍历那个区间去寻找损坏层。
假定最优区间长度是x，则第一步最多要摔100/x次，第二步最多摔x-1次，问题转换为求100/x+(x-1)的最小值。
具体描述：以10层楼为一个区间，先摔第一个，以确定摔坏的区间，然后再用另一个在这个区间内从最低的楼层摔，从而找到所要求层数，这种方法最多要摔19次。
然而这种等长区间也是有问题，第一次我们需要判断的范围是100，然而摔下第一个球的时候，判断区间就改变了，如果碎了，那么就进入第二个步骤了。如果没有碎，那么需要判断的区间就变成了x+1到100。由于他的区间变小，应该可以有更优的选择，而不适宜沿用之前的定长区间。
假设最终需要测试的次数的为x，我们在x楼层摔下第一个玻璃球，球摔坏了，那么最多需要的楼层为1到x-1，即总测试次数为1+（x-1）=x
如果球未损坏，那么我们的测试范围变成了x+1层到100层，即测试范围减少了x层。
当我们再次摔下第一个球的时候，为了保证最终的测试次数为x，那么需要增长x-1,即为x+x-1层。
如果还没有摔坏，那么为了保证最终的结果仍为x，那么我们需要增长x-2，即为x+（x-1）+（x-2）层。
以此类推，直到增长区间为1时，由于我们设定这个x为最差情况，因此最终可搜索的楼层是可能超过100层的，即x+（x-1）+（x-2）+（x-3）....+1>=100。
到此我们终于明白了，这不是等差数列吗，等差数列公式是（首项＋末项）×项数÷2，那么可以得到
（x+1）*x/2 >=100，由此我们求的x最小值为14。
具体描述：
先从14层扔（碎了试1-13）
再从27层扔（碎了试15-26）
再从39层扔（碎了试28-38）
再从50层扔（碎了试40-49）
再从60层扔（碎了试51-59）
再从69层扔（碎了试61-68）
再从77层扔（碎了试70-76）
再从84层扔（碎了试78-83）
再从90层扔（碎了试85-89)
再从95层扔（碎了试91-94）
再从99层扔（碎了试96-98）
最后从100层扔
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
