大楼扔鸡蛋问题的求解

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

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

这道问题其实可以扩展到任意个鸡蛋,但现在还是只看 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) 也成立

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

21,349 次阅读

6 thoughts on “大楼扔鸡蛋问题的求解

  1. 没看懂,因为你的 f 函数表示的有些乱,一开始是 2 个参数影响 f() 函数,过一会变成了一个参数影响 f() 函数了。

发表评论

电子邮件地址不会被公开。

back to top