问题：

奥林匹克大厦楼层高100层，当楼层低时，从楼上扔下鸡蛋不会碎，当楼层高时，从楼上扔下鸡蛋会破碎。现在你有两个鸡蛋，你扔多少次，可以计算得出鸡蛋不会碎的楼层？

方式一：

从一层开始扔，每层递增，那么每次增加1，最多试100次就出结果了。
结果：最少1次就碎，最多100次碎。
同时这个是在只有一个鸡蛋下的最优解
最终的次数的结果区间为(1， 100)

方式二：平衡二叉树法

每次取中间值楼层，如：50,25,13,7,4,2,1。如果第一次取50碎了，那说明临界点在50以内，就剩下一个鸡蛋，又开始第一种方式。
最终的次数的结果区间为(7， 50)
为了最优反向取，如：1,2,4,7……。最优1次就碎，最差75碎了，50没碎，那么就是(1,8+24)。
最终的次数的结果区间为(1， 32)

方式三：

假设我从N层扔，每次楼层一样,那么：N x N >= 100, N取10层，如：10,20,30,40……100，一共10份。
如果第一次扔10碎了，说明区间在1到10直接。最差的结果在100层扔碎了，区间在91层到99层之间。既(1+9, 10+9)。
最终的次数的结果区间为(10， 19)

方式四：最优方案递归

不过二分查找似乎并没有对我们解决问题有什么特别好的启发，我们只好另辟蹊径。我们可不可以通过 分而治之 的思想来解决这个问题呢？

首先，基线条件很好确定：

在有 2 个鸡蛋的情况下，如果只有一层楼，只需要试一次；如果有两层楼，只需要试两次；如果没有楼，那就干脆不用试了（看似是废话，但是是很重要的边界条件）。
如果只有 1 个鸡蛋，只能老老实实从下往上尝试，也就是在最坏的情况下，有几层楼就要试几次。
接下来，我们就要思考递归条件了。如何能将问题简化。

令在有 2 个鸡蛋时，最坏的情况下，N 层楼所需要尝试的最少次数为 TN。

假设总共有 N 层楼，我们在第 K 层楼进行一次尝试。那么此时，就会分成两种情况：

鸡蛋在 K 层碎掉了，也就说明临界楼层在 K 层以下。但是此时，我们只剩下 1 个鸡蛋，最坏的情况下还要检测 K−1 次才能找到临界楼层
鸡蛋在 K 层没有碎，临界楼层在 K 层以上。此时我们还是有 2 个鸡蛋，还剩下 N−K 层楼需要检测，那么最坏的情况下，还需要检测 TN−K 次。很显然 N−K 要比 N 少，我们顺利实现对问题的简化。
最坏的情况显然是 K−1 和 TN−K 两个数的最大的那一个再加上 1，因为我们先试了一次。这个最大的数，就是 TN。

不过这里面有一个 K 是不能确定的。为了找到合适的 K，我们需要把 K 从 1 到 N 的情况全部计算出来，找到使得 TN 最小的情况即可。

用代码来解决这个问题就是：

def two_egg(n: int) -> int:
    """
    双蛋问题的递归求解
    :param n: 楼层数
    :return: 最坏情况下，找到临界楼层所需最少尝试次数
    """
    if n == 0:    # 没有楼就不需要试
        return 0
    elif n == 1:   # 有一层楼，试一次
        return 1
    result_list = []
    for k in range(1, n + 1):    # 在每一层都试一下
        result_list.append(max(k - 1, two_egg(n - k)) + 1)    # 把每一层的情况都记录下来
    return min(result_list)    # 最好的结果就是我们想要的


# 用 1 到 11 的数字测试，不用 100 是因为电脑性能不够，测到 11 是因为 10 和 11 的结果不同
for f in range(1, 12):
    print(f'{f} -------> {two_egg(f)}')

递归法解决普遍双蛋问题
用二分查找，可以解决鸡蛋数目不限的情况，递归查找可以解决只有 2 个鸡蛋的情况。现在，我们把问题进一步扩展：如果我们有 M 个鸡蛋，N 层楼，在最坏的情况下，至少需要测试多少次能够找到临界楼层？

基线条件根上面的差不多一样：

不管有多少个鸡蛋，如果只有一层楼，只需要试一次；如果没有楼，那就干脆不用试了。
如果只有 1 个鸡蛋，只能老老实实从下往上尝试，也就是在最坏的情况下，有几层楼就要试几次。
递归条件其实也很类似，只是因为鸡蛋数目的引入，会稍微复杂一丁丁点点。

令在有 M 个鸡蛋时，最坏的情况下，N 层楼所需要尝试的最少次数为 TM, N。

依旧假设总共有 N 层楼，我们在第 K 层楼进行一次尝试。那么此时，还是会分成两种情况：

鸡蛋在 K 层碎掉了，也就说明临界楼层在 K 层以下。但是此时，我们只剩下 M−1 个鸡蛋，最坏的情况下还要检测 TM−1, K−1 次才能找到临界楼层
鸡蛋在 K 层没有碎，临界楼层在 K 层以上。此时我们还是有 M 个鸡蛋，还剩下 N−K 层楼需要检测，那么最坏的情况下，还需要检测 TM, N−K 次
上面的两种情况，要么简化了鸡蛋数量，要么简化了楼层数量，最终都可以通过递归来找到答案。最终的结果需要是 TM−1, N 和 TM, N−K 这两个数中最大的那一个加上 1，因为我们最开始的时候在 K 层测试了一下。

同样地，我们需要遍历测试当 K 为 1 到 N 时的各种情况，取其中所需步骤最少的，就是我们要的结果。

用代码表示就是：

def two_egg_general(m: int, n: int) -> int:
    """
    普遍双蛋问题的解决
    :param m: 鸡蛋数量
    :param n: 楼层总层数
    :return: 最糟糕的情况下，找到临界楼层所需最少尝试数目
    """
    if n == 0:    # 如果没有楼，不需要试
        return 0
    elif n == 1:    # 只有 1 层楼，试一次就足够
        return 1
    if m == 1:    # 只有 1 个蛋，有几层楼就要使几次
        return n
    result_list = []
    for k in range(1, n + 1):
        result_list.append(max(two_egg_general(m - 1, k - 1), two_egg_general(m, n - k)) + 1)
    return min(result_list)


for i in range(1, 12):
    for j in range(1, 12):
        print(f'({i}, {j}) --> {two_egg_general(i, j)}', end=' | ')
    print()
赏