兩個蛋的問題混淆

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