关键词：抛小球，抛鸡蛋，楼层
恩，是有关键词，为了让搜索引擎找到这个文章。
题目的原型是这样的：
有100层楼，给你两个玻璃球，在某一层楼R将球扔下，球会碎，而R-1楼就不会碎，设计一个方案，确保找到这个R，这个方案最少要尝试多少次。
这是个相当相当经典的公司面试笔试题目，目前网上流传各种版本。其他版本还包括300层楼，3个球等等。总之实际上这个问题对于要找工作的同学来说，是有好好琢磨一下的必要的。
首先，我们先考虑一个更为一般，但更为直接的问题：如果给你n个球，允许你尝试不超过k次，那么最多你能检查多少层楼？（看出这个问题和上面那个问题的关系了吧）
在解决这个问题的时候，我们先来考虑这样的情况，假设我们第一次抛球，在第q层抛球，那么有两种可能的结果，一种是球碎了，一种是球没碎对吧（到目前为止全是废话）。如果球碎了，那么你肯定往下检查对吧，这时候你手里还有n-1个球，最多还能抛k-1次对吧？因此q-1层一定是你用n-1个球，抛k-1次能检查的最大楼层，这样就能保证下面不会有任何疏漏了。那么，要是球没碎呢，你肯定往上检查对吧。那么现在你手里还有n个球，还能最多抛k-1次对吧。那么在q层之上，情况实际上和q层之下是一样的，就是你还能检查的层数实际是用n个球，抛k-1次能检查的最大楼层数对吧。所以，我们可以得到一个递推的关系：假设有n个球，抛k次，最多检查F(n,k)层楼。那么就有
F(n, k) = F(n-1, k-1)+F(n, k-1)+1
别忘了最后那个1哦，那个就是你第一次尝试的第q层的那一层。
接着，要是你一个球都没有呢？显然F(0, k) = 0
当然，一次也不许你尝试呢？显然F(n, 0) = 0
因此，我们只要在上述的边界条件下，解上面的那个递推关系，呃，对它也叫差分方程对吧。
具体怎么用母函数法解差分方程这里不讨论。求解的结论是这样的：
F(n, k) = C(n-1, 0) + C(n-1, 1) + … + C(n-1 , m) – C(n-1, 0) – C(n-1, 1) –…– C(n-1, n-m-1) + exp(2, n-1) – 1 (当n<k时)
F(n, k) = exp(2, k) -1 (当n >= k时)
其中C(p, q)是组合数,exp(a,b)是指数，a是底数。
C(p, q)=p!/[q!(p-q)!]，exp(a, b) = a^b。
有了这个结论，为了求解原问题，设原问题要求N个楼层，n个球，设最少要抛k次，只要求解
F(n, k-1) < N 且F(n,k)>=N的不等式组即可求得k。
本blog中关于差分方程求解结果采用了 网友 随机漫步 和 水木社区 Locke 网友的意见。