扔蛋问题
文章目錄
扔蛋问题说的是,100层楼,给两个特制鸡蛋。从某层扔下鸡蛋,鸡蛋就会碎。问至少要测试多少次才能试出这个层数。对于这个问题,许多人都可以背出答案14层。但如果是200层呢?
事实上,还可以对这题进行扩展,假设n层,e个鸡蛋,求至少要测试多少次,才能测出这个层数。
对于这题,可以用动态规划。还是在面4399时,面试官要我解释什么是动态规划,当时没能解释清楚。现在想来,动态规划有两个重要的因素,一个是最优子结构,还有一个是重叠子问题。按我的理解,最优子结构说的是,当前的最优解包含了子问题的最优解。重叠子问题说的是,子问题具有重叠部分。
而对于这题,可以写出一个递推公式,设n为楼层数,e为鸡蛋数。
f(n,e) = 1 + min{max{f(n - r, e),f(r - 1, e -1)}} 其中r属于{2,3,…,n - 1},初始条件为f(n,1) = n, f(1,e) = 1, f(2,e) = 2. 这里要求n,e都是正整数。
写成程序如下:
1 | def egg(n, e=2): |
对于鸡蛋数为2时,还有特殊的解法。在鸡蛋数为2时,楼层数与测试次数如下:
1 1
2 2
3 2
4 3
5 3
6 3
7 4
8 4
9 4
10 4
11 5
…
于是可以猜测,对于楼层数n ,只要找到第一个x ,使得 x * (x + 1) / 2 >= n即可,对于100,正好是14。类似地,对于开头提出的鸡蛋数为2,楼层数为200时,测试层数也可以类似的求解