大楼扔鸡蛋问题的求解

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

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

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

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

分享到:

6 comments

  1. http://usaipphonesystems.com

    大楼扔鸡蛋问题的求解 | 四火的唠叨…

  2. [...] 这道题是说,100层楼,两个一模一样的鸡蛋,某层之上扔鸡蛋就会碎。问要测试多少次才能找出这层楼来。我曾经在去年初的这篇文章里面讨论过这个问题的解法,因为只想记录一下思路和讨论过程,写得很简略。现在,我想重新整理一下这个问题,再稍稍扩展和挖掘一下。希望可以用尽可能清晰易懂的描述,把这个问题的前后说清楚。 [...]

  3. [...] 这道题是说,100层楼,两个一模一样的鸡蛋,某层之上扔鸡蛋就会碎。问要测试多少次才能找出这层楼来。我曾经在去年初的这篇文章里面讨论&#36…,因为只想记录一下思路和讨论过程,写得很简略。现在,我想重新整理一下这个问题,再稍稍扩展和挖掘一下。希望可以用尽可能清晰易懂的描述,把这个问题的前后说清楚。 [...]

  4. 王敬 说道:

    还有k表示的意思。

  5. 王敬 说道:

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

发表评论

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

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Preview on Feedage: