我只是读这篇文章，我被下沿，直到看看看我能做到三个一节。作者指出，第一个蛋破裂后它会降低到2蛋的问题，并可以递归来解决。

这是伟大的，但也并不是我们想用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 ，其中 K 现在是13 ...但是，这给了我们4.815，如果我们CEIL并且与添加我们我们得到6 previous下降，这是比实际溶液低，因此在这里的东西是错...

的两个蛋的问题

正在给两个鸡蛋，并获得了100层高的大楼。两个鸡蛋是相同的。这样做的目的是要找出从一个鸡蛋不会破的时候放弃了从楼窗口的最高层。如果一个鸡蛋被丢弃，不破，这是完好的，可以再次回落。然而，一旦一个鸡蛋坏了，这是它的蛋。

如果从掉到地上时，一个鸡蛋破裂 N ，那么它也会从上面的任何地面破裂。如果卵子存活的下降，那么它就会生存下来的任何下降也短。

现在的问题是：你应该采取什么样的策略，以最大限度地减少数量卵子下降才能找到解决方案的 的。 （什么是最坏的情况下滴它会是多少？）

如果我们从14楼摔一遍，它打​​破了，那么我们递归。 N（N + 1）/ 2 = k其中k是现在13 ...但是，这为我们提供了4.815，如果我们CEIL和并添加我们得到了6 previous下降，这是比实际溶液低，所以这里的东西是错误的...

如果它不破怎么办？然后你有一个三蛋的问题有86层楼，这需要也许有降少，解决比100楼的问题。

假设你把从50 的第一个蛋日地板。如果它打破了，你有一个双蛋的问题，49层楼，这需要多达10个额外的下降。这样会给你一个最坏情况下的11滴（因为如果它不破，在50楼的三蛋的问题需要最多7个额外滴）。

，如果它打破了，你有一个36层楼的两蛋的问题，需要多达8个额外的下降。如果不破，你有一个63层楼的三蛋的问题离开了。你想解决这个问题，在8滴，所以如果未来降打破了鸡蛋，剩下的两个蛋的问题应该是可以解决的，最多7滴，所以你可以选择第二个下拉最高的楼是 37 + 28 + 1 = 66 ，自28层楼是最高的，你可以与最多7滴和两个鸡蛋解决。如果鸡蛋不破，你有一个34层楼的三蛋的问题，7滴离开了。你当然可以解决，其余6滴，如果鸡蛋分成是21（6 * 7/2），这样你就可以选择楼层最高的 66 + 21 + 1 = 88 。如果鸡蛋不破，你有12层楼只剩下6滴，这已经是可行的，只有两个鸡蛋。

系统地，最高的楼层数，你当然可以解决与 D 下降和电子鸡蛋

  / 1，当d = = 1
F（E，D）= |研发，如果E == 1
          \ F（E-1，D-1）+ 1 + F（E，D-1），如果e基1和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 楼层电子鸡蛋，你必须找到

  D（E，F）=分钟{D | F（E，D）＆GT; = F}
 

您可以发现，通过计算 F（E，D）矩阵，也可以使用动态规划：

如果您选择地板取值的首次下降，如果卵子断裂，则需要多达 D（E-1，S-1 ）下降，以确定地板。如果鸡蛋不破，则需要多达 D（E，FS）下降，以确定地板。 因此，最坏的情况下选择地板取值为先降

  WC（S，E，F）= 1 +最大值{D（E-1，S-1），D（E，FS）}
 

和最好的最坏情况的是

  D（E，F）=最小{WC（S，E，F）| 1＆LT; = S＆LT; = F}
 

（当然，其中 D（E，0）= 0 ）。

I was just reading this article and I was following along until the "Look see I can do three" section. The author states that after the first egg breaks it degrades into the 2-egg problem and can be solved recursively.

That's great, but wouldn't we want to choose larger step-sizes when using 3 eggs instead of 2 (for the first egg)? From which floor do we throw the first egg?

With 1 egg, we have to start at floor 1. With 2 eggs, we solve for n(n+1)/2=k and round up, where n is the starting floor, and k is the number of floors. With 3... I'm having trouble coming up with a formula.

Thinking about this a bit more, with 2 eggs, the maximum number of drops is equal to the floor number that we drop our first egg from. For example, with 2 eggs and 100 floors, the solution is 14, which means we drop the first egg from floor 14, and if it breaks, we have to drop up to 13 more times, for floors 1-13.

With 3 eggs, the solution is 9 (as shown in the chart). But we wouldn't want to throw the first egg at floor 9, we can throw it higher, because we don't have to iterate by 1s in-between.

If we throw from floor 14 again, and it breaks, then we recurse. n(n+1)/2=k where k is now 13... but that gives us 4.815, if we ceil and that and add our previous drop we get 6, which is lower than the actual solution, so something here is wrong...

The Two Egg Problem

You are given two eggs, and access to a 100-storey building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst case for the number of drops it will take?)

If we throw from floor 14 again, and it breaks, then we recurse. n(n+1)/2=k where k is now 13... but that gives us 4.815, if we ceil and that and add our previous drop we get 6, which is lower than the actual solution, so something here is wrong...

What if it doesn't break? Then you have a three-egg problem with 86 floors, which takes maybe one drop less to solve than the 100-floor problem.

Say you drop the first egg from the 50th floor. If it breaks, you have a two-egg problem with 49 floors, which takes up to 10 additional drops. So that would give you a worst-case of 11 drops (since if it doesn't break, the 50-floor three-egg problem takes at most 7 additional drops).

If you choose the 37th floor for the first drop, if it breaks, you have a 36-floor two-egg problem, needing up to 8 additional drops. If it doesn't break, you have a 63-floor three-egg problem left. You want to solve that problem with at most 8 drops, so if the next drop breaks the egg, the remaining two-egg problem should be solvable in at most 7 drops, thus the highest floor you can choose for the second drop is 37 + 28 + 1 = 66, since 28 floors is the highest you can solve with at most 7 drops and two eggs. If the egg doesn't break, you have a 34-floor three-egg problem with 7 drops left. The highest you can certainly solve with the remaining 6 drops if the egg breaks is 21 (6*7/2), so you can choose floor 66 + 21 + 1 = 88. If the egg doesn't break, you have 12 floors left with 6 drops, which is already doable with only two eggs.

Systematically, the highest number of floors you can certainly solve with d drops and e eggs is

          / 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

If you have only one drop, you have no choice but to choose the lowest floor of which you do not yet know that the egg doesn't break. If that breaks it, and you tried a higher floor, you don't know the first floor to break the egg.

If you have only one egg, you have to check every floor in order until the egg breaks or you run out of drops.

Otherwise, if the first drop is from a floor higher than F(e-1,d-1) + 1, you possibly can't find the first breaking floor if the egg breaks. If the first drop is from a lower floor, you can't reach as high with d-1 drops if the egg doesn't break, so the first drop should be from floor F(e-1,d-1) + 1. If it breaks, you can solve with the remaining e-1 eggs and d-1 drops by assumption. If not, you can solve for the next F(e,d-1) floors with the remaining drops and eggs.

Conversely, to find how many drops you may need for f floors with e eggs, you have to find

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

You can find that by calculating the F(e,d) matrix, or you can use dynamic programming:

If you choose floor s for the first drop, if the egg breaks, you need up to D(e-1,s-1) drops to determine the floor. If the egg doesn't break, you need up to D(e,f-s) drops to determine the floor. So the worst case for choosing floor s for the first drop is

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

and the best of the worst case is

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

(where of course D(e,0) = 0).