鸵鸟蛋测试

一场活动要测试鸵鸟蛋的坚固性。要让蛋从高楼上落下而不破,进而依据不破的最高楼层决定蛋的硬度。测试的高楼共101层。测试员意识到,如果他只带一颗鸵鸟蛋的话,他需要从第1层开始往上依次每一层把蛋投下以判定蛋的硬度。

如果他带两颗鸵鸟蛋(假定坚固性一样),那么在最坏的情况下他需要测试多少次呢?

我的解法是反过来考虑,假设可以测试n次,那么最乐观的情况可以测试到几层。

1.      最高应选择第 n 层。假设破了,第2颗蛋从第1层开始….;假设没破,按下面2继续。

2.      继续往上n-1 层。假设破了,第2颗蛋从第n+1层开始…;假设没破,同理继续下去。

….

不难得出,最乐观的情况可以测试到 n+(n-1)+(n-2)+…+1 层。所有有下面的不等式:

                                           $n+(n+1)+...+1=\frac{(n+1)n}{2}\ge 101 $

解得 n 要大于等于 14 次。所以最坏的情况需要测试14次。测试方法是,第一次选择14层。假设破了,第2颗蛋从第1层开始…;假设没破,第2次选择14+(14-1)=27层开始…

考虑下3颗的情况。

假设$f_2(n) \quad f_3(n) $ 分别表示2颗3颗蛋投n次可测试的最大层数。同理第1次,最高可选择$f_2(n-1) $+1 层,如果破了,还剩2颗,n-1 次,按2颗蛋的方案即可;如果没破,第2次继续往上 $f_3(n-1) $ 层。显然就又下面的递推关系

$f_3(n)=f_2(n-1)+1+f_3(n-1)$

展开该数列:

$f_3(n)=f_2(n-1)+1+\\f_2(n-2)+1+\\...+f_2(0)+1\\=(1+2+...n-1)+1+\\(1+2...+n-2)+1+\\....+1\\=(1+2+...n-1)+\\(1+2...+n-2)\\+....+(1)+n$

看到这个数列,我当时想太美了,居然跑出个通项为等差数列的数列求和。联想到之前自己推前n项平方和、前n项立方和公式的情形。那时我已经推出了该公式:

$1+(1+2)+...+(1+2+...+n)\\=\frac{n(n+1)(n+2)}{6}$

所以不难计算出:

$f_3(n)=\frac{(n-1)n(n+1)}{6}+n\\=\frac{n(n^2+5)}{6} $

所以最坏情况9次即可。

同理可推4颗 … k 颗蛋的情况,公式将变得更加复杂。


下一篇 n 皇后问题

欢迎关注我的微信公众号[边玩边学]:长按"识别图中二维码";或打开微信扫一扫。

评论(0)