大楼扔鸡蛋问题的求解

有道经典的算法题，两个一模一样的鸡蛋，某层之上扔鸡蛋就会碎。假如运气最差的话，问要测试多少次才能找出这层楼来。

如果只有一个鸡蛋，我就只能一层一层试验。两个的话关键就是找着第一个鸡蛋试验的位置，第二个鸡蛋还是只能一层一层试验。

这道问题其实可以扩展到任意个鸡蛋，但现在还是只看 2 个鸡蛋的情况。

2 个鸡蛋只有 n 层的最优解求出来假使为 k，那么，n+1 层的时候，把第一个鸡蛋在第 k 层释放，只有两种情况（n+1 只是分解成两个<=n 的子问题，这两个都是已经有解了的）：

（1）破碎，于是只有之后就只能遍历从地面到第 k-1 层，一层层遍历，不能偷懒，最坏的情况在此要尝试 k 次；

（2）没碎，那问题不就变成了要在 n-k 层里面求解的子问题了吗？

假设最优解 y=f(2,n)，所以得到：

f(2,n+1) = max(k, f(2,n-k)+1)

接下去的递归求解就豁然开朗了。

我本以为问题就差不多可以结了，赶紧去写代码吧，可是小罗同学叫住我了：

表急，好像有更简单的解法：

找一个 k  k(k+1)/2>=100，k 可取的最小整数值就是最优解 

这个好像是猜出来的，得证明一下。

• （a）要证明 k(k+1)/2>=n 里面 k 是可以准确找出这层楼的解；
• （b）当 k<=k-1 的时候，不等式恒不成立

这样才能得出这个 k 是最优解。

小罗同学说，可以用数学归纳法证明这第（a）点：

k=1 时，1(1+1)/2>=1 成立。 现在用数学归纳法，根据 f(k-1)=(k-1)(k-1+1)/2>=n-k，得出 f(k)=k(k+1)>=n，依据是前面提到了碎和没碎两种情况的分类讨论。 

当然，还可以用“ 递降法”：

要证明 k(k+1)>n  只需要证明 (k-1)(k-1+1)/2>=n-k  只需要证明 (k-2)(k-2+1)/2>=n-k-(k-1)  ……  只需要证明 0>=n-(k+k-1+k-2+…1)  等价于 k(k+1)/2>=n 

无论如何，这只完成了上面的第（a）点，还有第（b）点没有证明呢，即：

当 k<=k-1 的时候，不等式恒不成立，又即下面的不等式恒成立：

(k-1)k/2<n 

走到这一步似乎没法进行下去了……

谁来为我指指路呢？呵呵。

—————————————————————————————————————-

2012-2-3 晚上补充：

上式的解决办法，还是数学归纳法：

f(k) 的时候，第一次测试不能高于 k 层（因为第一次测试高于 k 的时候，如果碎了，就肯定不能保证 k 次测试出来了）  如果 f(k)=x, 第一次不能高于 k，那么剩下至少是 x-k 是吧   剩下的次数是 k-1 次是吧   所以 x-k>=f(k-1)=(k-1)(k-1+1)/2 所以 x>=k(k+1)/2 又显然 f(1)=1(1+1)/2=1 所以对于 f(k-1) 成立的话，f(k) 也成立

文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》

×Scan to share with WeChat