扔鸡蛋问题

题目:
你面前有一栋从 1 到 N 共 N 层的楼,然后给你 K 个鸡蛋(K 至少为 1)。现在确定这栋楼存在楼层 0 <= F <= N,在这层楼将鸡蛋扔下去,鸡蛋恰好没摔碎(高于 F 的楼层都会碎,低于 F 的楼层都不会碎)。现在问你,最坏情况下,你至少要扔几次鸡蛋,才能确定这个楼层 F 呢?
鸡蛋没有撞碎可以重复用,每个鸡蛋的抗摔能力一样,鸡蛋可以有剩余。


最好的策略是使用二分查找思路,我先去第 (1 + 10) / 2 = 5层扔一下:
如果碎了说明 F 小于 4,我就去第 (1 + 4) / 2 = 2 层试……
如果没碎说明 F 大于等于 4,我就去第 (5 + 10) / 2 = 7 层试……

实际上,如果不限制鸡蛋个数的话,二分思路显然可以得到最少尝试的次数,但问题是,现在给你了鸡蛋个数的限制 K,直接使用二分思路就不行了

比如说只给你 1 个鸡蛋,710层楼,你敢用二分吗?你直接去第 45层扔一下,如果鸡蛋没碎还好,但如果碎了你就没有鸡蛋继续测试了,无法确定鸡蛋恰好摔不碎的楼层 F 了。这种情况下只能用线性扫描的方法,算法返回结果应该是 10。

有的读者也许会有这种想法:二分查找排除楼层的速度无疑是最快的,那干脆先用二分查找,等到只剩 1 个鸡蛋的时候再执行线性扫描,这样得到的结果是不是就是最少的扔鸡蛋次数呢?

很遗憾,并不是,比如说把楼层变高一些,100 层,给你 2 个鸡蛋,你在 50 层扔一下,碎了,那就只能线性扫描 1~49 层了,最坏情况下要扔 50 次。
如果不要「二分」,变成「五分」「十分」都会大幅减少最坏情况下的尝试次数。比方说第一个鸡蛋每隔十层楼扔,在哪里碎了第二个鸡蛋一个个线性扫描,总共不会超过 20 次​。
最优解其实是 14 次。最优策略非常多,而且并没有什么规律可言。


代码实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**************************************************************** 
 * Description: 扔鸡蛋问题   egg dropping
 * Author: Alex Li
 * Date: 2023-05-21 16:28:22
 * LastEditTime: 2023-08-15 17:28:46
****************************************************************/
#include <algorithm>
#include <iostream>
#include <limits>
using namespace std;

const int MAXN=105;
const int MAXK=105;

int h[MAXN][MAXK];

//递归方法
int f(int n, int m){
    if(m==1)return n;
    if(n==0)return 0;

    int ret=numeric_limits<int>::max();
    for (int i =1; i <=n; i++)
       ret=min(ret,max(f(n-i,m),f(i-1,m-1))+1);
    return ret;        
    }
//递推方法
int g(int n,int m){
    for (int i =1; i <=n; i++)
        h[i][1]=i;
    for (int j =1; j <=m; j++)
        h[0][j]=0;
    
    for (int i = 1; i <=n; i++){
        for (int j =2; j <=m; j++){
            h[i][j]=numeric_limits<int>::max();
            for(int k=1;k<=i;k++)
                h[i][j]=min(h[i][j],max(h[i-k][j],h[k-1][j-1])+1);
        }
    }
    return h[n][m];
}

int main(){
    int n,m;// n为楼层,n为鸡蛋个数
    cin>>n>>m;
    cout<<f(n,m)<<endl<<g(n,m)<<endl;
    return 0;
}
Scroll to Top