扔鸡蛋问题

img 菜鸡第一次看算法题,这篇笔记还是不要看比较好

题目

x星球的居民脾气不太好,但好在他们生气的时候唯一的异常举动是:摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试,并且评定出一个耐摔指数来,之后才允许上市流通。

x星球有很多高耸入云的高塔,刚好可以用来做耐摔测试。塔的每一层高度都是一样的,与地球上稍有不同的是,他们的第一层不是地面,而是相当于我们的2楼。

如果手机从第7层扔下去没摔坏,但第8层摔坏了,则手机耐摔指数=7。
特别地,如果手机从第1层扔下去就坏了,则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏,则耐摔指数=n

为了减少测试次数,从每个厂家抽样3部手机参加测试。

某次测试的塔高为1000层,如果我们总是采用最佳策略,在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢?

解决方案

这东西就是传统的扔鸡蛋问题。

二分法

通常使用此方法的前提是 鸡蛋个数 ≥ ⌈log2M⌉ (M表示楼层个数)例如,9~16层楼在最坏情况下都需要多达 4 个鸡蛋才能得出结果。

倘若鸡蛋个数少,当只剩最后一个鸡蛋时,只能最保守地在一个较大的区间内逐层向上扔鸡蛋,显然会徒增尝试次数,不宜使用。

动态规划

动态规划思想是利用对已求解的重复子问题进行记忆化存储,然后避免重复计算,利用最优化原理得出结果。说人话就是粗暴地递归找。

此方法需要寻找“状态转移方程式”,并依此“倒推”求解

先设一个函数 f(m,n) m 表示楼层数(不是楼高),n 表示鸡蛋数,返回值为最优解在最恶劣情况下需要尝试的次数。

假设第一个鸡蛋在 x 层 (1≤x≤m) 扔出,将出现两种情况:

  1. 鸡蛋在 x 层抛出后碎了
  2. 鸡蛋在 x 层抛出后没碎

鸡蛋碎了

显然接下来应从 (1≤y≤x-1) 层扔出鸡蛋,由于鸡蛋碎了,鸡蛋个数将 -1,同时尝试过一次了,所以尝试次数 +1

根据上面所设函数,可以将这种情况用同样的函数表示为 f(x-1, n-1) +1

鸡蛋没碎

由于鸡蛋没有碎,可以确保小于等于此层数的都没有问题,并且鸡蛋个数没有减少
剩余待测试层数为 m-x,可以用函数表示为 f(m-x, n) +1

这个函数描述在剩下 m-x 个楼层,n 个鸡蛋,返回值为最优解在最恶劣情况下需要尝试的次数。

为什么是 m-x ?

如果在思考这里的时候,代入的一个 x 值比较大,则容易在这里面绕进去。

受平时写业务代码的影响,此处的 f(m-x, n) 易被理解为具有判断鸡蛋是否摔碎的功能,但之前定义 f(a,b) 只是一个用于计算摔鸡蛋所需次数的函数,并非处理业务逻辑的函数,即并不是判断鸡蛋会不会摔碎的函数。

也就是说,尽管已经知道 在 m-x 层的鸡蛋并不会碎(业务逻辑),但仍需假设鸡蛋会碎,并求出在 m-x 层、有 n 个鸡蛋时需要尝试多少次。

f 的第一个参数压根就不是表示楼高的,而是楼层的个数!个数!

得出公式

在从 x 层扔鸡蛋的条件下,此处尚不知道到底鸡蛋碎还是不碎是更加恶劣的情况(需要进一步尝试的次数多),因此需要同时求出上述两种情况,并取最大者:

f(m,n)=max{ f(x-1, n-1)+1, f(m-x, n)+1 }

题设要求我们解出哪层(x)扔鸡蛋可以在最恶劣的情况下(上式)所得值最小,因此需要遍历x (1≤x≤m),分别代入 1≤x≤m 求出值,取最小者,函数返回值即为最优解在最恶劣情况下需要尝试的次数,而使这个返回值成立的x即为所求x(即所求最优解)

综上,易得公式:

f(m,n)=min{ max{f(1-1, n-1)+1, f(m-1, n)+1}, max{f(2-1, n-1)+1, f(m-2, n)+1}, max{f(3-1, n-1)+1, f(m-3, n)+1}, ..., max{f(m-1, n-1)+1, f(m-m, n)+1} }

代码实现

以从 100 楼下落,持有 2 个鸡蛋为例

public class Main {
    private static final int Floor = 100;
    private static final int Egg = 2;

    private static int f(final int m, final int n) {
        int min = 0;
        boolean isInitialized = false;

        if (m == 0)
            return 0;

        for (int x = 1; x <= m; x++) {
            int result = Math.max(f(x-1, n-1)+1, f(m-x, n)+1);

            if(!isInitialized || min > result) {
                isInitialized = true;
                min = result;
            }
        }

        System.out.printf("progress: m=%d value=%d \n", m, min);
        return min;
    }

    public static void main(String[] args) {
        System.out.println("result: " + f(Floor, Egg));
    }
}

跑一下就可以发现,计算花费了大量的时间,这是由于递归的资源开销很大,时间复杂度大,因此效率较低,需要在上式的基础上进行优化。

不优化可以吗?原题 1000 层楼,3 个鸡蛋,我觉得跑到收卷也跑不完,更何况还是渣机。

简单的优化

尝试重新整理思路以改写成循环的形式。

首先绘制一张表格:

持有的鸡蛋数(n)/楼层数(m) 0层楼 1层楼 2层楼 3层楼 4层楼
0个鸡蛋
1个鸡蛋
2个鸡蛋
3个鸡蛋

显然:

  1. 在只有一个鸡蛋时,楼层数=尝试次数
  2. 在只有一层楼时,不管多少个鸡蛋都只尝试一次
  3. 0 层楼或 0 个鸡蛋时不需要尝试,尝试次数记为 0
持有的鸡蛋数(n)/楼层数(m) 0层楼 1层楼 2层楼 3层楼 4层楼
0个鸡蛋 0 0 0 0 0
1个鸡蛋 0 1 2 3 4
2个鸡蛋 0 1
3个鸡蛋 0 1

使用上面的公式,算出2个鸡蛋时、不同层楼的情况,再算出3个鸡蛋时、不同层楼的情况。

求解过程略,但可以发现:求解需要用到上次求解的结果,例如,在求解2个鸡蛋2层楼时,需要用到0层楼2个鸡蛋、1层楼1个鸡蛋的结果。显然,这个表格的填充顺序应是从上到下、从左到右、填完一行到下一行。

根据公式 f(m,n)=max{ f(x-1, n-1)+1, f(m-x, n)+1 }
得出:表格坐标(m,n)的值为 max{(x-1, n-1)的值+1, (m-x, n)的值+1}

持有的鸡蛋数(n)/楼层数(m) 0层楼 1层楼 2层楼 3层楼 4层楼
0个鸡蛋 0 0 0 0 0
1个鸡蛋 0 1 2 3 4
2个鸡蛋 0 1 2 2 3
3个鸡蛋 0 1 2 2 3

整理思路

整理一下上面的操作,可以分为下面的过程:

  1. 建立一个二维数组模仿上面的表格保存结果
  2. 对只有一个鸡蛋时直接返回楼层数,暂时将其他填充为最大尝试次数
  3. 2个以上的鸡蛋时,首先枚举鸡蛋个数(n)
  4. 枚举鸡蛋个数(n)时,枚举楼层数(m)
  5. 枚举楼层数(m)时,枚举从哪层楼开始扔(x)
  6. 枚举从哪层楼开始扔(x)时,算出这层楼的尝试次数
  7. 对应“坐标”的值为尝试次数的最小者
  8. 最终所求解为表格最右下角的那个值

写成代码:

import java.util.stream.IntStream;

public class Main {
    private static final int Floor = 1000;
    private static final int Egg = 3;

    private static int getMinDropEggTries(final int floorNum, final int eggNum) {
        if (floorNum < 1 || eggNum < 1)
            return 0;

        int[][] result = new int[eggNum+1][floorNum+1]; //坐标为 (鸡蛋,楼层)

        IntStream.range(1, floorNum+1).forEach(value -> result[1][value] = value);
        IntStream.range(1, eggNum+1).forEach(value -> result[value][1] = 1);

        IntStream.range(2, eggNum+1).forEach(egg ->
                IntStream.range(2, floorNum+1).forEach(floor ->
                        IntStream.range(1, floor+1).forEach(x -> {
                                    int value = Math.max(result[egg-1][x-1] + 1, result[egg][floor-x] + 1);

                                    if(result[egg][floor] == 0 || result[egg][floor] > value)
                                        result[egg][floor] = value;
                                })));

        return result[eggNum][floorNum];
    }

    public static void main(String[] args) {
        System.out.println("result: " + getMinDropEggTries(Floor, Egg));
    }
}

进一步优化

不难发现,int[][] result 实际上在后续计算中并没有使用,可以将其简化以降低空间复杂度。


转载请遵守 CC BY-NC-SA 4.0 协议并注明来自:扔鸡蛋问题