彻底搞懂-扔鸡蛋问题-方程-动态规划

以你之姓@ 2023-02-20 07:24 3阅读 0赞

## **1、题目：** ##

2个鸡蛋，从100层楼上往下扔，以此来测试鸡蛋的硬度，比如鸡蛋在第9层没有摔碎而在第10层摔碎了，那么鸡蛋不会摔碎的零界点就是9层，如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？

## **2、解决思路** ##

### **2.1、最笨法：** ###

把其中一个鸡蛋从第1层开始往下扔，如果第1层没碎换到第2层扔，如果第2层没碎换到第3层扔，，，如果第59层没碎换到第60层扔，如果第60层碎了，说明不会摔碎的临界点是59层，最坏情况下需要扔100次

### **2.2、二分法：** ###

把鸡蛋从50层往下扔，如果第一枚在50层碎了，就从第1层开始（一共只有两个鸡蛋，第一个鸡蛋碎了，第二个鸡蛋就只能用最保守的方式一层一层扔，假如第二个鸡蛋从25层扔，碎了，就无法判断临界点了）；如果没碎，继续使用二分法，在剩余楼层的一半（75层）往下扔，，，，最坏需要尝试50次

### **2.3、平方根法：** ###

做一个平方运算，100的平方根是10，因此我们尝试每10层扔一次，第一次从10层扔，第二次从20层扔，第三次从30层，，，一直到100层，最好情况是在第10层碎掉，尝试次数为1+9=10次；最坏情况是在第100层碎掉，尝试次数为10+9=19次

### **2.4、方程法：将思路逆转** ###

假设问题存在最优解，这个最优解的最坏情况尝试次数是x次，那么我们第一次扔鸡蛋该选择哪一层？

答案是从第x层开始，选择更高一层或更第一层都不合适

分析：假设第一次扔在第x+1层，如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层一层一层扔，一直到第x层，这样总共扔了x+1次，和假设尝试x次相悖，由此可见，第一次扔的楼层必须小于x+1次

假设第一次扔在第x-1层，如果第一个鸡蛋碎了，那么第二个鸡蛋开始一层一层扔，直到第x-2层，这样我们总共扔了x-1次，虽然没有超过假设次数，但似乎有些过于保守（什么意思，还没理解）

假设第一次扔在第x层，如果第一个鸡蛋碎了，那么第二个鸡蛋开始一层一层扔，一直到第x-1层，共x次

因此要向尽量楼层跨度大一些，又保证不超过假设的尝试次数x，那么第一次扔鸡蛋的最优选择就是第x层

更进一步。。。

如果第一次扔鸡蛋在第x层，但并没有打碎，第二次扔鸡蛋在哪一层？

如果第一次扔鸡蛋没碎，我们的尝试次数消耗了一次，问题就转为，两个鸡蛋在100-x层楼往下扔，要求尝试次数不得超过x-1次，则第二次尝试的楼层跨度为x-1层，绝对楼层是x+x-1层；如果还没碎，第三层楼层跨度是x-2，第四层是x-3！

so，x+(x-1)+(x-2)+...+1=100，左边多项式是各次扔鸡蛋的楼层跨度之和，假设尝试x次，所以该多项式共有x项，右边是总的楼层数100，解方程可得x=14（（x+1）\*x/2=100）

因此，最优解在最坏情况的尝试次数是14次，第一次扔鸡蛋的楼层也是14层，在第一个鸡蛋没碎的情况下，尝试的楼层为：14,27,39,50,60,69,77,84,90,95,99,100，假如鸡蛋不会碎临界点在65层，那么依次：14,27,50,60,69碎了，让后第二个鸡蛋从61层开始61,62,63,64,65,66碎了，即不会碎的临界点是65层

## **3、动态规划解题：**有M层楼N个鸡蛋，找到鸡蛋摔不碎的临界点，需要尝试几次? ##

可以把m层楼和n个鸡蛋的问题转化为一个函数F(m,n)，其中楼层数m和鸡蛋数n是函数的两个参数，函数的值则是最优解的最大尝试次数，假设第一个鸡蛋扔出的位置在第x层（1<=x<=m），会出现两种情况：

1).第一个鸡蛋没碎，则剩余m-x层楼和n个鸡蛋，F(m-x,n)+1

2).第一个鸡蛋碎了，则从1到x-1层尝试，剩余鸡蛋n-1，F(x-1,n-1)+1

so，我们要求m层楼n个鸡蛋条件下，最大尝试次数的最小解，即

F(m,n)= Min(Max(F(m-x,n)+1,F(x-1,n-1)+1)) . 1<=x<=m

### 3.1、eg：3个鸡蛋，4层楼 ###

首先填充第一个鸡蛋在各个楼层的尝试次数，以及任意多鸡蛋在1层楼的尝试次数，原因：只有一个鸡蛋，so只能从1层扔到最后一层，尝试次数为楼层数量；只有一个楼层，无论有几个鸡蛋，也只有一种扔法，尝试次数只能为1

![70][]

2个鸡蛋2层楼，带入状态转移方程式F(2,2)=Min( Max(F(2-x,2)+1，F(x-1,2-1)+1)) )

x可以为1和2，so：

x=1时，F(2,2)=Max(F(2-1,2)+1，F(1-1,2-1)+1))=Max(F(1,2)+1, F(0,1)+1)=Max(1+1, 0+1)=2

x=2时， F(2,2)=Max(F(2-2,2)+1，F(2-1,2-1)+1))=Max(F(0,2)+1, F(1,1)+1)=Max(0+1, 1+1)=2

取最小值即为2

依次类推

![70 1][]

先上代码（当然了，还是别人写的，看的可真费劲，话说动态规划看一次不懂一次。。。）

### 3.2、python版代码解决floor层楼仍egg个鸡蛋的问题 ###

# 我们要求m层楼n个鸡蛋条件下，最大尝试次数的最小解，即
    # F(m,n)= Min(Max(F(m-x,n)+1,F(x-1,n-1)+1)) . 1<=x<=m
    import numpy as np
    
    
    def get_min_floor(floors=100, eggs=2):
        # 第一步，创建动态规划的备忘录，即状态转移矩阵
        f = np.zeros((eggs+1, floors+1), dtype=np.int)
        # 第二步，考虑边界
        # part1: 先考虑eggs边界，eggs为0，则为0；eggs为1，肯定从第0层往上依次实验
        for i in range(floors+1):
            f[0][i] = 0
            f[1][i] = i
        # part2: 再考虑floor的边界，floors为0即为0，floors为1即为1
        for i in range(eggs+1):
            f[i][0] = 0
            f[i][1] = 1
        # 第三步就是状态方程了，鸡蛋从第2个开始算,楼层也从第2开始算
        for egg in range(2, eggs+1):
            for floor in range(2, floors+1):
                # 你还有egg个鸡蛋，一共有floor层楼的子问题
                # 定义一个变量来存储最终结果，找到在哪里扔能达到所扔次数最少的目标
                result = 100000
                # 从第drop层扔鸡蛋
                for drop in range(1, floor+1):
                    # 碎了，剩下的问题即如何在drop-1层，用egg-1个鸡蛋寻找最优解
                    broken = f[egg-1][drop-1]
                    # 没碎，在floors-drop层，用egg个鸡蛋找最优解
                    unbroken = f[egg][floor-drop]
                    # 两种情况取最大值，因为我根本不知道鸡蛋会不会碎
                    condition = max(broken, unbroken)+1
                    # 不断和上一次结果做比较，得到最少的扔次数
                    result = min(condition, result)
                f[egg][floor] = result
        # 以上步骤在不断的往状态举证填充，到这里已经填充完毕
        final_result = f[eggs][floors]
        return final_result
    
    
    if __name__ == '__main__':
        print get_min_floor(eggs=2, floors=100)  # 输出结果14
        print get_min_floor(eggs=2, floors=36)   # 输出结果8
        print get_min_floor(eggs=2, floors=39)   # 输出结果9
        print get_min_floor(eggs=3, floors=39)   # 输出结果6

参考：[https://blog.csdn.net/Autumn03/article/details/80886814][https_blog.csdn.net_Autumn03_article_details_80886814]

[https://blog.csdn.net/aBen\_Dan/article/details/90897527][https_blog.csdn.net_aBen_Dan_article_details_90897527]

[70]: https://img-blog.csdn.net/20180702210216568?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0F1dHVtbjAz/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: https://img-blog.csdn.net/20180702210201261?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0F1dHVtbjAz/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[https_blog.csdn.net_Autumn03_article_details_80886814]: https://blog.csdn.net/Autumn03/article/details/80886814
[https_blog.csdn.net_aBen_Dan_article_details_90897527]: https://blog.csdn.net/aBen_Dan/article/details/90897527