『悠然见南山』

    有一个100层高的大厦，你手中有两枚相同的玻璃棋子。从这个大厦的某一层扔下围棋子就会碎。用你手中的这两枚围棋子，找出一个最优的策略，来得知那个“临界”层面——
    第一次应该从哪层开始扔？
    以你的方案，最坏的情况多少次可以测出临界层？
    这是一道Google的面试试题，具体来源不得而知，网上有无数解法，讽刺的是，Google自己搜到的大部分解法都是错的。3月份的《程序员》杂志刊登了这到题目，但我分析了一下，对杂志上给出的答案（起始测试层）也有疑问。这并不是什么了不得的难题吧（////），网上的答案集中在19次，18次，16次和15次，我现在找到的策略是14次。我敢说超过15次的策略一定不是最优的，那么14一 是不是最优的呢？呵呵，我们来分析一下。
    假设你从50层开始扔第一枚棋子。如果第一枚棋子碎了，你就要从第1层开始逐层试探，最坏的情况是临界层在第49层，这样你总共测试了49+1=50次；如果第一枚棋子没碎，你可以把它拿到——比如说——75层，再试，如果这次碎了，另一枚棋子就要从51层试验到74层，这样总共试验了2+（74-51+1）=26次……以此类推，总之，最坏的情况，你要试验50次。
    现在假设你从10层开始扔第一枚棋子，假如第一枚棋子没有碎，则之后每10层扔一次。跟上面相同的道理，假如临界层在第87层，总共经历了9+（87-81+1）=16次试验；最坏的情况当然是临界层在第99层，你要试验10+（99-91+1）=19次。
    显而易见，如何把大楼“分段”成为解决问题的关键。“段”分得合理，就可以让试验次数减少。那么，是让每段包含的层数均匀分布好一些，还是让投掷次数分布均匀好一些呢？如果是前者，平均分段后那么19次就是最优策略了。如果是后者，首先的解决方案是：尝试逐渐减少分段所包含的层数（否则随着第一枚棋子测试层数的累加，最坏的情况下总的投掷次数也有所增加），我们假设第一次扔棋子的层数为n，之后逐层递减，可以考虑这样一个不等式：
    n+(n-1)+(n-2)+...+2+1<=100
    也就是：
    n(n+1)/2<=100
    n^2+n<=200
    可以得到（取整数）
    n<14
    于是就有了我们的方案：从第14层开扔第一枚棋子，如果它没有破碎，则从第14+13=27层开始扔，还是没有破碎就从14+13+12=39层开始扔，以此类推；如果第一枚棋子39层破碎了，则以第二枚棋子从第28层试验到第38层，总共试验次数为3+（38-28+1）=14次。
    按照这个策略，可测试到第14+13+12+...+4=99层。假如第99层还没有破碎，那么临界层就是第100层，总共测试了11次。如果99破碎了，那么分别在第96，97，98层用第二枚棋子进行第12，13，14次投掷（第10次投掷第一枚棋子在95层），最坏的情况是98层破碎，总共试验次数也是14次。
    《程序员》3月号的解答的起始测试层是第13层，但没有说具体操作方法。13+12+...这样扔下去肯定是搞不定的，但13+13+12+...也有效（虽然失去了数学美感），第一次投掷如果碎了，最坏的情况变成了12+1=13次测试，但13+13+12...最后是累加到98层，如果还没有碎，99和100还要分别测试1次。所以，我觉得从第13层起始缺少一种和谐感（-_,-)。
    分析到这里，你一定觉得这个题目很简单，但这个14层的策略是我憋了一个晚上才搞出来的。如果这真是Google面试的题目，恐怕是要当场作答的。（/////）我发现我已经把我从前学的数学知识忘的一干二净，这件事又进而让我想到，目前我知道的一切，可能有一天也要忘记的一干二净，什么都不剩下。我们的大脑是多么不可靠……
    这个题目应该可以用数学的思想去解决，推广到n层楼，m个棋子的情况……
    事实上，也许这样一个班里只有第一名才能迅速的解答此类题目，第一名，总是占有着所有的荣誉，可是世界上绝大部分的价值，都是第二名到最后一名之间的这些人创造的……

    按照棋子理论，把棋子换成人，把第二名到最后一名扔下大楼，大部分人都不会死，而第一名是必定升仙的，那么我们是不是应该安身立命，不要苛求过多呢……