美文网首页
鸡蛋掉落问题解析

鸡蛋掉落问题解析

作者: 卖女孩的小火柴18 | 来源:发表于2020-01-07 22:48 被阅读0次

    问题定义

    原始题目来源于LeetCode https://leetcode-cn.com/problems/super-egg-drop/comments/

    你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
    每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。
    你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
    每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。
    你的目标是确切地知道 F 的值是多少。
    无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?
    示例 1:
    输入:K = 1, N = 2
    输出:2
    解释:
    鸡蛋从 1 楼掉落。如果它碎了,我们肯定知道 F = 0 。
    否则,鸡蛋从 2 楼掉落。如果它碎了,我们肯定知道 F = 1 。
    如果它没碎,那么我们肯定知道 F = 2 。
    因此,在最坏的情况下我们需要移动 2 次以确定 F 是多少。
    示例 2:
    输入:K = 2, N = 6
    输出:3
    示例 3:
    输入:K = 3, N = 14
    输出:4
    提示:
    1 <= K <= 100
    1 <= N <= 10000

    问题解析

    第一反应,二分法。但是鸡蛋数量是有限的。比如K=2,N=6的情况。第一次先扔3楼,3楼如果没碎,则在4-6楼中继续试验;3楼碎了的话,则只能从1楼开始进行,最多次数3。
    不过,不适合用于鸡蛋数量少,楼层高的情况。比如K=2,N=50的情况。第一次扔25楼,如果碎了,就必须从1楼还是扔。则最多有25次。如果第一次扔10楼,不碎的话扔20楼,一直到40楼,这样最多的次数为4+10=14次。可见,直接二分的方法不通用。按照几等分的方法也不通用。

    第二反应,动态规划。和背包问题有些像,也是基于上一个条件来得出最优解。本题的关键点就转换为找到状态转移方程,以及结束条件。

    状态转移方程

    使用 dp(K,N) 表示状态转移,表示在有 K 个鸡蛋,N楼时候需要扔鸡蛋的次数。如果在第 i 层扔鸡蛋。

    1. 鸡蛋碎了,在 dp(K-1, i -1) 中找最大值。即现在剩余鸡蛋数目 -1 ,查找 i 层以下的楼层
    2. 鸡蛋没碎,在 dp(K , N - i) 中找最大值。即现在剩余鸡蛋数不变,查找 i ~ N层之间的楼层,即 i+1, i+2, 到 N,总楼层数为 N - i
    3. 于是可以得到状态转移方程如下所示:
      dp(k,N) = max(dp(K -1, i-1), dp(K, N - i) + 1 );
    结束条件

    状态的终止条件:

    1. 只有1个鸡蛋了,还有多少层没测完就还需要扔多少次
    2. 楼层全部测完了,不管还剩几个鸡蛋都结束
    3. 于是可以得出结束条件有两个
      if (N ==0) {
      dp(k,N) = 0;
      } else if (K == 1) {
      dp(k,N) = N;
      }
      这种做法有点像数学归纳法的证明方式。


      egg_drop.jpg
    时间复杂度

    由于不知道起始扔鸡蛋的位置,所以在设置起始位置时候,需要遍历来进行查找。
    所以 动态规划的时间复杂度 = N * dp(K,N),其中 dp 为一个循环,即O(N),最后得到的复杂度为 O(N^2)。

    代码

    egg_drop.c

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <unistd.h>
    
    #define min(x,y) ({ typeof(x) _x = (x); typeof(y) _y = (y); (void) (&_x == &_y); _x < _y ? _x : _y; })
    #define max(x,y) ({ typeof(x) _x = (x); typeof(y) _y = (y); (void) (&_x == &_y); _x > _y ? _x : _y; })
    
    /**
     * dp - 状态转移函数
     * @K: 鸡蛋个数
     * @N: 总共楼层
     *
     * return: 需要扔鸡蛋次数
     */
    int dp(int K, int N)
    {
        int i, ret, cnt;
        ret = 0;
    
        /* 最开始扔鸡蛋位置不确定,需要遍历 */
        for (i = 1; i <= N; i++) {
            /**
             * dp(K - 1, i - 1) 为鸡蛋碎了后,用K-1个鸡蛋测i-1层楼
             * dp(K, N - i) 为鸡蛋没碎后,用K个鸡蛋测(i - 1)层楼
             * +1 表示已经扔了一次,次数++
             */
            cnt = max(dp(K - 1, i - 1), dp(K, N - i)) + 1;  /* 最坏情况下的次数 */
            if (i == 1) {
                ret = cnt;
            } else {
                ret = min(ret, cnt);                            /* 查找不同楼层丢,找到丢次数最少的楼层,即找到最少次数 */
            }
        }
    
        return ret;
    }
    
    /**
     * superEggDrop - 获取最小扔鸡蛋次数
     * @K: 鸡蛋个数
     * @N: 总共楼层
     *
     * return: 需要扔鸡蛋次数
     */
    int superEggDrop(int K, int N)
    {
        int i, ret, cnt;
    
        ret = 0;
        if (N == 0) {    /* 到最低层,不需要再扔鸡蛋了 */
            return 0;
        } else if (K == 1) {    /* 鸡蛋只有一个,有几层最多扔几次鸡蛋 */
            return N;
        }
    
        /* 最开始扔鸡蛋位置不确定,需要遍历 */
        for (i = 1; i <= N; i++) {
            /* 第一次从i层丢下后,需要的次数 */
            cnt = max(dp(K, N - i), dp(K - 1, i - 1)) + 1;
            if (i == 1) {
                ret = cnt;
            } else {
                ret = min(ret, cnt);
            }
        }
    
        return ret;
    }
    
    int main (int argc, char *argv[])
    {
        int K, N;
        int ret;
    
        /* 打桩验证 */
        K = 3;
        N = 14;
    
        ret = superEggDrop(K, N);
        printf("superEggDrop ret:%d\n", ret);
    
        return ret;
    }
    
    

    Makefile:

    CC = gcc
    CFLAGS = -g 
    LIBS = -lrt
    ELF = egg_drop
    
    SRC1 = egg_drop.c
    OBJ1 = $(SRC1:%.c=%.o)
    
    all:    ${ELF}
    
    egg_drop: $(OBJ1)
        ${CC} ${CFLAGS} -o $@ $^ ${LIBS}
    
    $(OBJ1): %.o: %.c 
        ${CC} ${CFLAGS} -c -o $@ $<
    
    clean:
        rm -f ${ELF} *.o *.d
    

    执行效果
    ./egg_drop
    superEggDrop ret:4

    相关文章

      网友评论

          本文标题:鸡蛋掉落问题解析

          本文链接:https://www.haomeiwen.com/subject/lazdactx.html