【算法】鸡蛋问题

如果你有两枚鸡蛋,同时,你想知道,从楼上将鸡蛋摔下而不让它碎掉的楼层极限是多少,你会怎么做?

1.1 一个鸡蛋

鸡蛋必须临界层仍小的时候碎,所以唯一的策略是从1层往上逐层投掷,此时最高的投掷次数为 \(T_{max}\)

1.2 两个鸡蛋

利用多的这个鸡蛋缩小查找的范围,因而把楼层分成若干段:先利用一个鸡蛋来确定临界层所在的段,再利用另一个鸡蛋确定临界层,总的投掷次数等于确定临界段的次数 \(n_1\)和确定临界层的次数 \(n_2\)的和。

  • 现在把总楼层平均分成n段,有
    $$T_{max} = (n-1) + {S_n \over n - 1} = n + {S_n \over n} - 2$$

由均值不等式可知 \(n = \sqrt {S_n}\) 时,

$$T_{max} = 2 \times \sqrt {S_n} - 2$$

把\(S_n\)层分成若干段,从下往上,每段的层数减少1,这样使得在最坏的情况下,\(n_1\)增加1的同时\(n_2\)减少1,因而\(n_1\)和\(n_2\)的综合不变,为确定n的值,解不等式\(n+(n-1)+(n-2)+\cdots+1 \ge S_n\)

1.3 推广

从上面的讨论可以看书,此问题的关键是高阶等差数列, k个鸡蛋时:
$$ \sum_{i=1}^n C^k_i \ge S_n $$

Yunjie Zhang wechat
扫一扫上面的二维码加我微信