两个蛋的问题混淆

Question

两个蛋的问题：

• 您将得到2个鸡蛋。
• 您可以使用100层高的建筑物。
• 鸡蛋可能非常硬或非常脆弱，意味着如果从一楼掉下来，鸡蛋可能会破损，或者如果从100层跌落，鸡蛋可能不会破损。两个鸡蛋都是相同的。
• 你需要弄清100层建筑物的最高楼层，鸡蛋可以放下而不会断裂。
• 现在的问题是你需要做多少滴。你可以在这个过程中打破2个鸡蛋

我相信两个鸡蛋问题（上面提到的）已经被充分讨论过了。然而，有人可以帮助我理解为什么下面的解决方案不是最优的。

假设我使用段大小为s的段和扫描算法。 所以，

d (100/s + (s-1)) = 0 [ this should give the minima, I need '(s-1)' scans per segment and there are '100/s' segments] 
- 
ds 

=> -100/s^2 + 1 = 0 
=> s^2 = 100 
=> s = 10 

所以根据这个我需要最多19滴。但最佳的解决方案可以用14滴做到这一点。

那么问题出在哪里？

Answer 1

您似乎假设尺寸相同。对于一个最佳的解决方案，如果第一个分段的大小为N，那么第二个分段的大小应为N-1，等等（因为当你开始测试第二个分段时，你已经为第一个分段放下一个蛋分割）。

Answer 2

所以，你需要解决n+(n-1)+(n-2)+...+1<=100，从那里(n)(n+1)/2<=100（此功能转换与arithmetic series做又名一个等差数列的总和），现在如果你解决N（wolframalpha：Reduce[Floor[n + n^2] >= 200, n]）你14.现在你知道你需要做的下降一楼是14楼，下一个将是（14 + 14-1）楼和整个序列：

14; 27; 39; 50; 60; 69; 77; 84; 90; 95; 99; 100 

如果你打破第一个鸡蛋，你回去的最后一个并线性检查所有选项，直到你打破第二个蛋，当你这样做时，你得到了你的答案。没有魔法。

http://mathworld.wolfram.com/ArithmeticSeries.html

Answer 3

我也想好了这个同样的想法。我还试图找到你说的确切方法。我按照其中一位成员的解释清除了这个解决方案。但如果可能的话，这里有更多解释。

N被定义为所需搜索的最小数量。

我想找到一个no：n，这样它就是我必须做的搜索的最小号码。

所以我开始在第x楼我有2个场景，

1） 它打破了，我要做X-1检查更多的（因为我只有1个多鸡蛋）。所有在那里的公平。总计是1+ x-1 = x搜索。

现在我们已将此值定义为n。因此x = n！ [PS：这可能是微不足道的，但这有一些微妙的国际海事组织]

2） 它没有破 - 我已经用尽了我的n个可能之一！ 现在可以进一步搜索的是n - 1。只有这样，总搜索次数才是N，那就是N的定义。 现在这个问题已经成为100个楼层有2个鸡蛋的小问题。 如果现在选择一些地板 - 最坏的情况应该是n - 1。 （n-1）层满足这个条件。

因此，你得到的模式去nth , n + (n -1)th floor , n + (n - 1) + (n - 2)th floor ....解决这个100楼，你会得到N。 我认为，你开始的地板和no：的搜索是巧合。

要获得最大值n = 14，您可以考虑使用n个灯泡同时发光2个灯泡。 这将需要至少14个灯泡来覆盖鸡蛋可能破碎的所有可能组合。

作为一个挑战尝试做3个鸡蛋。

在你的逻辑基本上，搜索进度如何是不对称的。 对于第一组10个元素，该算法快速找到。 我建议尝试和检查

http://ite.pubs.informs.org/Vol4No1/Sniedovich/一些explnation也尝试想象这个问题是如何在网络中的真实案例可见。

Answer 4

正确和最佳的解决方案是13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100其中，鸡蛋打破发现地板的平均尝试次数最少，假设鸡蛋打破的地板是随机选择的。

基于这些信息，我们可以写一个递归函数，以尽量减少平均试验，给出的

13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100 

的解决方案，具有以下每层步

13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14 

这是最大的试验显然比天真的解决方案要好得多，假设从14开始的差距缩小了。在这种情况下，55％的时间你只需要13次试验。这是非常接近从n (n+1)/2 >= 100得出最优的解决方案，使n = 13.651和我们的最佳解决方案是(13*5+14*9)/14即13.643

这里是一个快速的实现：

import sys 

def get_max_trials(floors): 
    pf = 0 
    trials = [] 
    for i, f in enumerate(floors): 
     trials.append(i+f-pf) 
     pf = f 
    return trials 

def get_trials_per_floor(floors): 
    # return list of trials if egg is assumed at each floor 
    pf = 0 
    trials = [] 
    for i, f in enumerate(floors): 
     for mid_f in range(pf+1,f+1): 
      trial = (i+1) + f - mid_f + 1 
      if mid_f == pf+1: 
       trial -= 1 
      trials.append(trial) 
     pf = f 
    return trials 

def get_average(floors): 
    trials = get_trials_per_floor(floors) 
    score = sum(trials) 
    return score*1.0/floors[-1], max(trials) 

floors_map = {} 
def get_floors(N, level=0): 
    if N == 1: 
     return [1] 
    if N in floors_map: 
     return floors_map[N] 
    best_floors = None 
    best_score = None 
    for i in range(1,N): 
     base_floors = [f+i for f in get_floors(N-i, level+1)] 
     for floors in [base_floors, [i] + base_floors]: 
      score = get_average(floors) 
      if best_score is None or score < best_score: 
       best_score = score 
       best_floors = floors 

    if N not in floors_map: 
     floors_map[N] = best_floors 
    return best_floors 

floors = get_floors(100) 
print "Solution:",floors 
print "max trials",get_max_trials(floors) 
print "avg.",get_average(floors) 

naive_floors = [14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100] 
print "naive_solution",naive_floors 
print "max trials",get_max_trials(naive_floors) 
print "avg.",get_average(naive_floors) 

输出：

Solution: [13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100] 
max trials [13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14] 
avg. (10.31, 14) 
naive_solution [14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100] 
max trials [14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 12] 
avg. (10.35, 14) 

Answer 5

这里有一个解决方案在Python中。如果你将鸡蛋放在某个楼层f，它会打破或者不打开，并且在每种情况下你都有一定数量的楼层，你仍然需要检查（这是一个子问题）。它使用递归和查找字典使计算速度更快。

neededDict = {} 

# number of drops you need to make 
def needed(eggs, floors): 

    if (eggs, floors) in neededDict: 
     return neededDict[(eggs, floors)] 

    if eggs == 1: 
     return floors 

    if eggs > 1: 

     minimum = floors 
     for f in range(floors): 
      #print f 
      resultIfEggBreaks = needed(eggs - 1, f) 
      resultIfEggSurvives = needed(eggs, floors - (f + 1)) 
      result = max(resultIfEggBreaks, resultIfEggSurvives) 
      if result < minimum: 
       minimum = result 

     # 1 drop at best level f plus however many you need to handle all floors that remain unknown 
     neededDict[(eggs, floors)] = 1 + minimum 
     return 1 + minimum 


print needed(2, 100) 

Answer 6

这个问题不应该是你需要做多少滴吗？但我不知道它应该找到最小数量的下降，以便知道鸡蛋打破的位置，我在careercup上看到了这个问题，下面是我想到的算法：

有两种方法可以解决这个问题：

• 第一个蛋二进制搜索（冒知道我们需要看看 上）O（二进制日志）
• Fibonaccy序列搜索1,2,3,5,8,13,21,34 ，55,89为第一个蛋O（log）http://en.wikipedia.org/wiki/Fibonacci_search_technique

一旦第一个蛋坏了，我们知道在哪个区间，我们需要看看：

1. 二进制例如：

   我们尝试100/2（50），如果它打破了我们的1从1搜索到50递增如果不是我们把它从50 + 100/2（75）扔掉，我们从50找到75，如果不是我们从75 + 100/2（87）扔掉，如果它破坏了，我们从75到87搜索一层楼一次等等等等。

2. fibonacy例如：同一件事：我们尝试1,2,3,5,8.13，...如果第一个蛋 打破了我们的1

Answer 7

回到过去的时间间隔的最小值和增量

我在下面的链接中找到的解决方案的一个非常好的解释。 The Two Egg Problem

它解释如何得到n+(n-1)+(n-2)+...+1<=100
1.蛋的问题 - 线性复杂度为O（100）
和多个（无限）蛋的问题 - 对数复杂度为O（LOG 2（100））。

Answer 8

嘿这个方法怎么样。

试试这个顺序：

1,2,4,8,16,32,64,100

而且一旦你发现鸡蛋被打破，你也得到一个宽广的工作空间。 让我们假设@ 64个鸡蛋休息。那么答案在32 & 64之间。

我们可以在这两个数字之间使用正常的二进制搜索。 我们将检查@ 48（32 + 64）/ 2，然后我们将获得上半部分或下半部分的候选空间。并重复

在这种情况下，最坏的情况是发言权在99.这将需要14次尝试。

Answer 9

我会说100层有两个鸡蛋的最佳解决方案是13次尝试不是14.
13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100是最佳答案，但如果达到99我不需要尝试100.这显然是没有尝试正确的答案，从100层下降鸡蛋：d