Huper

昨天早早睡觉，一觉睡到中午11点多，起来一看玻璃上一层浓重的雾水，赶快起床去厨房的窗户一看，发现竟然映入眼帘的是一幅白色的世界。

按我妈的说法，似乎去年一个冬天都没有下过这么大的雪。之间我家附近的大杨树和榕树甚至连叶子还没来得及黄，就已经被一片白色所覆盖。树枝被压得弯弯的，是不是就有一大片雪从树上掉落。

美景不必多说，大家走出家门去感受一下吧。

不过……真tm冷……

md，今儿太激动了，可惜没捞到票，晚上家里还有事，没能去工体亲眼看。

不过看得我真热血沸腾，估计要是在现场肯定得哇哇大哭吧……

门清手持12344568条 234万 345饼，外面已经出了两个8条。

毅然放弃三面听打掉1条，转手自摸8条。

虽然是国标，但是如果是日麻的话，也是立直、一发、自摸、断幺。30符4翻……久部长知道也会很欣慰吧……

今天有几个人来我们公司面试，走了以后我就和同事们聊起来面试，这时候Charlie跟我们说要给我们出一个当年他见到的笔试(or面试）题：

有三个材质一样的玻璃球，一个300层高的楼。问最少试验几次可以保证一定能够知道玻璃球的承受能力（假设玻璃球从300层扔下一定会碎，就是说承受能力肯定小于300层）。注：只有三个球，碎了就不能用了。每扔一个球算实验一次。有可能承受能力是0层（就是在一层扔也有可能会碎）

然后我和Bart还有小栗就一起研究，还算不错，大概10分钟左右就想出来了答案，觉得还蛮有意思的，所以决定记录下来。

-----------------------分割线，下面是答案----------------------------







首先，我们设一个函数F(x,y)，表示x个球试y次最多可以在多少层楼的范围内保证测试出来。

然后我们先从两个球入手，做这么一道题：把三个球改成两个，然后考虑如果两个球，可以试n次，最多可以试多少层楼呢？

这个题的思路自然是分段试验，先用一个球从低往高进行分段试验，找到范围，然后再用剩下的一个球在那个范围内从低到高逐层试验。

不妨我们都用一号球先来试，一旦一号球碎了，再用二号球一层一层的试。实验开始：

（1）假设第一次把一号球放在n0层，碎了。
这时候我们就要考虑n0是多少。因为可以试n次，我们用一号球试了一次，还剩下n0-1次，二号球用n0-1次只能在n0-1层的范围内逐一试验，最坏的情况要试到n0-1层才得出答案，因此n0应该等于n。
（2）假设第一次把一号球放在n0层（也就是n层），没碎。
那么我们要在n0层上面的某层再试一号球。这时候一号球试验了两次，第二个球最多只能再试验n-2次，因此二号球能够逐一扫过n-2层楼的范围，加上一号球的第二次试验，就等于这个阶段一共扫过了n-1层的范围。

以此类推，一号球每多试验一次，二号球就要少试验一次，也就是少扫过一层的范围。因为一号球最多可以试n次，所以一共可以扫过的层数就是：
n+(n-1)+(n-2)+...+1=n(n+1)/2层

所以：F(2,n)=n(n+1)/2。

比如说两个球试10次，就可以让第一个球分别在10, 19, 27, 34, 40, 45, 49, 52, 54, 55层进行试验，只要碎掉，就用第二个球在得出的区间内从低到高逐层试验。可以保证在F(2,10)=55层之内都可以得到结果。

---------------------------------------------

至此，两个球的问题已经解决了。然后我们来解决三个球的问题，那就是三个球试n次最多可以测多少层楼呢。

由于我们已经有了两个球的思路，三个球的思路就比较明了了。

（1）假设第一个球我们放在n0层，碎了
此时我们仍然要算一下n0是多少。既然可以试n次，第一个球占去了一次，还剩下n-1次。由两个球的结论，两个球n-1次试验可以测出n(n-1)/2层的范围，所以n0=n(n-1)/2+1。

（2）假设第一个球我们放在n0层，没碎
由两个球的思路，第一个球每多一次试验，后两个球就少了一次试验。第一个球可以试验1到n次，把相应的剩下的两个球可以测出的楼层数相加，再加上第一个球自己所测的n层即可。

所以：

　　　　n
F(3,n)=sigma (F(2,n-i)+1)
　　　　i=1

把F(2,n)的公式带入
　　　　n　　　　　　　　　　　　n-1
F(3,n)=sigma ((n-i)(n-i+1)/2+1)=sigma (i(i+1)/2+1)
　　　　i=1　　　　　　　　　　　i=0
展开以后得：
F(3,n)=(n^3+5n)/6

回到原题，只要F(3,n)>=300即可，取n的最小整数值。我们可以得到F(3,12)=298, F(3,13)=377。

所以最少只需要13次就能保证在300层以内一定可以找到。

---------------------------------------------

然后我们可以把这个题扩展到求x个球试y次。我们可以得到如下的递归公式：
　　　　y　　　　　　　　　　y-1
F(x,y)=sigma(F(x-1,y-i)+1)=sigma(F(x-1,i)+1)
　　　　i=1　　　　　　　　　i=0

这样，我们就可以用程序来解决这个问题了，写一个递归的程序看起来会非常的简单。

函数如下（Java）：

    private static int run (int number, int times) {

        int s = 0;
        //终止条件：试验次数为0的时候结果为0，球的数量为1的时候结果就是试验次数。
        if (times == 0)
            s = 0;
        else if (number == 1)
            s = times;
        else {
            for (int i = 0; i < times; i++)
                s += run (number - 1, i) + 1;
        }
        return s;
    }

其中number表示球的数量，times表示试的次数。