广义双蛋之谜 [英] Generalised Two-Egg Puzzle

问题描述

下面是问题描述：

假设我们想知道这在A N层的楼层是安全的，从砸蛋，这将导致鸡蛋打破降落。我们做一些假设： 是生存下降一个鸡蛋可以再次使用。

Suppose that we wish to know which stories in a N-story building are safe to drop eggs from, and which will cause the eggs to break on landing. We make a few assumptions: An egg that survives a fall can be used again.

• 系统破蛋必须丢弃。
• 下降的效果是相同的所有的鸡蛋。
• 如果在下降鸡蛋破裂，那么它会打破，如果从更高的窗口下降。
• 如果一个鸡蛋生存下降那就更短的秋天生存。
• 在这不排除是一楼的窗户打破的鸡蛋，也不是排除了第N层楼的窗户不会导致鸡蛋破裂。

给定的N层大楼以及d鸡蛋，音响第二最小化（在最坏的情况下）以测定断裂FL OOR实验滴数的策略的供给

Given an N story building and a supply of d eggs, find the strategy which minimizes (in the worst case) the number of experimental drops required to determine the breakfloor.

我看见了，解决了这个问题鸡蛋2个，其中回答出来是14，N = 100。 我试图了解使用DP维基推广的解决方案，但不明白什么是他们想要做的事情。请告诉他们如何到达DP和它是如何工作的？

I have seen and solved this problem for 2 eggs where answer comes out to be 14 for N=100. I tried to understand the generalized solution from wiki using DP but couldn't Understand what are they trying to do. Please tell how they arrived at the DP and how it is working ?

编辑：

在<一的复发定href="http://www.scribd.com/api_user_11797_WebGuru/d/7217370-Egg-Puzzle-Generalized-Solution-for-Any-Number-of-Eggs"相对=nofollow>这个文章为最高的FL OOR能与D滴剂和电子鸡蛋进行测试如下：

The Recurrence given in this Article for the The highest floor that can be tested with d drops and e eggs is as follows :

f[d,e] = f[d-1,e] + f[d-1,e-1] + 1

复发是好的，但我无法理解它是如何得出？

The recurrence is fine but i not able to understand how it is derived ?

的解释并不清楚，我....我只是希望有人来解释这个复发来我更清楚的话。

The explanation is not clear to me....i just want someone to explain this recurrence to me in more clear words.

推荐答案

（1）考虑的首次下降打破蛋的情况。，然后你可以决定breakfloor当且仅当它是顶多F [D-1，E-1]。因此，你不能启动高于F [D-1，E-1] + 1（且不应启动过程中的低，）。

(1) Consider the case that the first drop breaks the egg. Then you can determine the breakfloor if and only if it is at most f[d-1, e-1]. Therefore you can't start higher than f[d-1, e-1] + 1 (and shouldn't start lower, of course).

（2）如果你的第一滴不打破鸡蛋，你在F [D-1，E]的情况下，刚开始你的第一次下降的地板+ 1而不是1楼。

(2) If your first drop doesn't breaks the egg, you are in the case of f[d-1, e], just starting at the floor of your first drop + 1, instead of floor 1.

所以，最好你能做到是开始在地板F下降鸡蛋[D-1，E-1] + 1（因为（1）），你可以得到最多F [D-1，E]高于楼层（因为（2））。这是

So, the best you can do is to start dropping eggs at floor f[d-1, e-1] + 1 (because of (1)), and you can get up to f[d-1, e] floors higher than that (because of (2)). That's

f[d, e] = f[d-1, e-1] + 1 + f[d-1, e]

这篇关于广义双蛋之谜的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！