14

我只是在阅读两个鸡蛋问题：

两个鸡蛋问题

你会得到两个鸡蛋，并可以进入一座 100 层高的建筑。两个鸡蛋是一样的。目的是找出鸡蛋从该楼层的窗户掉出时不会破裂的最高楼层。如果一个鸡蛋掉下来并且没有破裂，它就完好无损，可以再次掉下。然而，一旦一个鸡蛋被打破，那就是那个鸡蛋。

如果一个鸡蛋从地板上掉下来n就碎了，那么它也会从上面的任何地板上碎掉。如果一个鸡蛋在坠落中幸存下来，那么它会在任何比这更短的坠落中幸存下来。

问题是：你应该采取什么策略来最小化找到解决方案所需的鸡蛋滴数？. （最坏的情况是什么？）

我一直跟着，直到“看，我可以做三个”部分。作者指出，在第一个鸡蛋破裂后，它会退化为 2-egg 问题，并且可以递归解决。

这很好，但是当使用 3 个鸡蛋而不是 2 个（第一个鸡蛋）时，我们不想选择更大的步长吗？我们从哪一层扔第一个鸡蛋？

有1个鸡蛋，我们必须从1楼开始。
有2个鸡蛋，我们求解n(n+1)/2=k并四舍五入，哪里n是起始楼层，k是楼层数。
使用 3... 我无法想出一个公式。

再想一想，如果有 2 个鸡蛋，最大掉落数等于我们掉落第一个鸡蛋的楼层数。例如，有 2 个鸡蛋和 100 个楼层，解决方案是 14，这意味着我们从 14 层丢下第一个鸡蛋，如果它坏了，我们必须再丢 13 次，对于 1-13 层。

用 3 个鸡蛋，解决方案是 9（如图所示）。但是我们不想把第一个鸡蛋扔到第 9 层，我们可以把它扔得更高，因为我们不必在中间进行 1 秒的迭代。

如果我们再次从 14 楼扔出去，它坏了，那么我们就递归。n(n+1)/2=k现在 13在哪里k...但是这给了我们 4.815，如果我们 ceil 和那个并加上我们之前的下降，我们得到 6，这低于实际的解决方案，所以这里有问题...

4

5 回答 5

12

如果我们再次从 14 楼扔出去，它坏了，那么我们就递归。n(n+1)/2=k 其中 k 现在是 13...但是这给了我们 4.815，如果我们 ceil 和那个加上我们之前的下降，我们得到 6，这低于实际的解决方案，所以这里是错误的...

如果不破怎么办？那么你有一个 86 层的三个鸡蛋的问题，它可能比 100 层的问题少一滴解决。

假设你从 50 楼掉下第一个鸡蛋。如果它坏了，你有一个 49 层的两个鸡蛋问题，最多需要 10 次额外的下降。因此，最坏的情况是 11 滴（因为如果它没有破裂，那么 50 层的三个鸡蛋问题最多需要额外滴 7 滴）。

如果第一滴选择37层，如果破了，就是36层的二蛋问题，最多需要8个额外的滴。如果它没有破裂，那么你还有一个 63 层的三蛋问题。你想用最多 8 滴来解决这个问题，所以如果下一滴打破鸡蛋，剩下的双蛋问题应该最多 7 滴可以解决，因此你可以为第二滴选择的最高楼层是37 + 28 + 1 = 66，因为28 层是你最多可以用 7 滴和两个鸡蛋解决的最高层。如果鸡蛋没有破，你就有了一个 34 层的三蛋问题，还剩 7 滴。如果鸡蛋破裂是21（6 * 7 / 2），你当然可以用剩下的6滴解决最高，所以你可以选择地板66 + 21 + 1 = 88. 如果鸡蛋没有破，你还有 12 层楼剩下 6 滴，这已经可以只用两个鸡蛋了。

系统地，你当然可以用d水滴和e鸡蛋解决的最高楼层数是

          / 1, if d == 1
F(e,d) = |  d, if e == 1
          \ F(e-1,d-1) + 1 + F(e,d-1), if e > 1 and d > 1

如果你只有一滴，你别无选择，只能选择你还不知道鸡蛋不会破的最低层。如果它打破了它，并且你尝试了更高的楼层，你不知道一楼打破了鸡蛋。

如果您只有一个鸡蛋，则必须按顺序检查每个楼层，直到鸡蛋破裂或用完为止。

否则，如果第一滴是来自高于F(e-1,d-1) + 1的楼层，如果鸡蛋破裂，您可能找不到第一个破地板。d-1如果第一滴是从较低的楼层，如果鸡蛋不破，你就不能达到那么高，所以第一滴应该是从地板上F(e-1,d-1) + 1。如果它坏了，你可以用剩下的e-1鸡蛋和d-1假设来解决。如果没有，你可以用剩下的水滴和鸡蛋解决下F(e,d-1)一层。

f相反，要找出铺有鸡蛋的地板可能需要多少滴e，您必须找到

D(e,f) = min { d | F(e,d) >= f }

你可以通过计算F(e,d)矩阵来发现，也可以使用动态规划：

如果您选择s第一次下降的地板，如果鸡蛋破裂，您需要最多D(e-1,s-1)下降以确定地板。如果鸡蛋没有破裂，则需要最多D(e,f-s)滴下才能确定地板。s所以第一次下降选择地板的最坏情况是

WC(s,e,f) = 1 + max { D(e-1,s-1), D(e,f-s) }

最坏的情况是最好的

D(e,f) = minimum { WC(s,e,f) | 1 <= s <= f }

（当然在哪里D(e,0) = 0）。

于 2012-07-22T22:04:18.380 回答
4

这个问题可以通过以下 3 种方法（我知道）来解决：

  1. 动态规划
  2. 使用二叉搜索树的解决方案
  3. 通过获得可以测试或覆盖给定数量的鸡蛋和给定的滴数的最大楼层数的直接数学公式来解决

让我先定义一些符号如下：

e = number of eggs
f = number of floors in building
n = number of egg drops 
Fmax(e, n) = maximum number of floors that can be tested with e eggs and n drops

动态规划方法的关键在于以下 Fmax 的递归公式：

Fmax(e, n) = 1 + Fmax(e-1, n-1) + fmax(e, n-1)

而获得 Fmax 的直接数学公式的关键在于以下 Fmax 的递推公式：

Fmax(e, n) = { ∑Fmax(e-1,i) for i = 1 to n } - Fmax(e-1, n) + n

对于这个问题，使用二叉搜索树 (BST) 的替代解决方案也是可能的。为了方便我们的分析，我们画出BST，稍作修改如下：

1.    If egg breaks then child node is drawn on left down side
2.    If egg does not break then child node is drawn straight down side

如果我们用上述表示形式绘制 BST，则 BST 的宽度（即 BST 中的垂直列数）表示鸡蛋的数量。

任何具有 f 个节点的 BST，以上述表示形式绘制并受到 BST <= e（鸡蛋数）的约束宽度是一个解决方案，但它可能不是最佳解决方案。

因此，获得最优解相当于获得 BST 中节点的排列方式，其最小高度受到约束：BST 的宽度 <= e

有关以上 3 种方法的更多详细信息，请查看我的博客：解决广义蛋掉落问题的 3 种方法

于 2016-12-23T11:04:17.453 回答
2

这与我在Egg Drop Printing Solutions提供的答案相同。我在这里为任何想要查看整个决策树和推理的人提供它。

# This uses dynamic programming to find the basic information.
def optimal_solution(floors, eggs):
    # dp[drops][eggs] = max_floors
    dp = []

    # With no drops, we can do no floors
    dp.append([0 for x in range(eggs+1)])

    # With one drop and any eggs, we can do 1 floor
    one_drop = [1 for _ in range(eggs+1)]
    one_drop[0] = 0 # Except no eggs is still no floors
    dp.append(one_drop)

    # Keep adding drops until we have our answer
    # Note, in python array element -1 is shorthand for the end of the array.
    while dp[-1][eggs] < floors:
        # 0 floors for 0 eggs.  1 more for one egg
        next_drop = [0, dp[-1][1] + 1]
        for i in range(2, eggs+1): # Python for 2..eggs
            # The best we can do is drop at floor dp[-1][i-1].
            # If the egg breaks, we can find the answer using that solution.
            # If the egg holds, we can find another dp[-1][i] floors.
            next_drop.append(dp[-1][i] + dp[-1][i-1])
        dp.append(next_drop)

    return dp

# This turns that optimal solution into a decision tree.    
def dp_to_decision_tree(dp, floors, start_floor=None, eggs=None, drops=None):
    # Figure out defaults if needed.
    if start_floor is None:
        start_floor = 0
    if drops is None:
        drops = len(dp) - 1
    if eggs is None:
        eggs = len(dp[0]) - 1

    # Are we done?
    if floors == start_floor:
        return start_floor
    elif dp[drops][eggs] < floors - start_floor:
        return None

    # Do we need all of our drops?
    while floors - start_floor < dp[drops-1][eggs]:
        drops -= 1

    drop_at = start_floor + dp[drops-1][eggs-1]
    if eggs == 1:
        drop_at = start_floor + 1
    if floors < drop_at:
        drop_at = floors
    return [
        drop_at,
        dp_to_decision_tree(dp,  floors,     drop_at,   eggs, drops-1),
        dp_to_decision_tree(dp, drop_at-1, start_floor, eggs-1, drops-1),
        {'eggs': eggs, 'floor_range': (start_floor, floors)}
        ]

# This prints the decision tree in a human readable format.
def print_decision_tree(tree, indent="", label="start"):
    if tree is None:
        print(f"{indent}{label}: ?")
    elif isinstance(tree, int):
        print(f"{indent}{label}: {tree} found")
    else:
        print(f"{indent}{label}: {tree[0]} {tree[3]}")
        print_decision_tree(tree[1], indent + "    ", label="held")
        print_decision_tree(tree[2], indent + "    ", label="broke")

# And this calls the previous functions.
def print_optimal_decisions(floors, eggs):
    print_decision_tree(
        dp_to_decision_tree(
            optimal_solution(floors, eggs), floors))

# And now we can try it.
print_optimal_decisions(36, 3)
于 2020-11-03T17:27:51.067 回答
1

您可以使用简单的动态规划解决方案。n - 楼层数。k - 鸡蛋的数量。D[n,k] = 你回答（最小投掷次数）。对于每个 1 <= j <= n，D[j,1] = n-1。

计算 k>1 的 D[n,k] 的主要思想：

D[n,k] = 最大值 1 <= j <= n-1 { 最大值{ D[j,k-1]+1, D[nj,k]+1 }。

于 2012-07-22T20:30:36.580 回答
0

这里的博客解释了 1000 层的 3 个鸡蛋的数学方法：

https://sankalpiitr.wordpress.com/2012/03/02/the-2-eggs-problem-extended-to-3-eggs/

根据这个博客公式将是

P = N + ( N * ( N + 1 ) * ( N – 1 ) ) /6

其中 P 是楼层数，N 是所需的最小下降次数。

所以求解 P=100，我们得到 N 为 8.2

于 2018-09-13T22:21:56.710 回答