Проблема с двумя проблемами с яйцами

Ответ 1

Кажется, вы предполагаете равные сегменты. Для оптимального решения, если первый сегмент имеет размер N, второй должен быть размером N-1 и т.д. (Потому что, когда вы начинаете тестировать второй сегмент, вы уже сбросили яйцо один раз для первого сегмент).

Ответ 2

Итак, вам нужно решить n+(n-1)+(n-2)+...+1<=100, откуда (n)(n+1)/2<=100 (это преобразование функции выполняется с помощью арифметических рядов, равно как и сумма арифметической последовательности), теперь, если вы решаете для 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

Ответ 3

Правильное и оптимальное решение - это 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 i.e 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)

Ответ 4

У меня тоже была мысль. Я также пытался найти точный метод, который вы сказали. Я разрешил это решение, как объяснил один из участников здесь. Но вот немного больше объяснений, если можно.

N определяется как минимальное значение no: требуемых запросов.

Я пытаюсь найти no: n, так что это min no: запросов, которые я должен выполнить.

Итак, я начинаю с x-го этажа. У меня есть 2 сценария,

1) Это ломается, я должен сделать x-1 еще проверку (потому что у меня только еще 1 яйцо). Там все честно. Всего 1+ x-1 = x поиск.

Теперь мы определили это значение как n. Следовательно, x = n! [PS: Это может быть тривиально, но у этого есть некоторые тонкости IMO]

2) Он не сломается - и я уже использовал одну из моих возможностей! Теперь поиски разрешены далее n - 1. Только тогда общее число no: поиска будет N, и это определение N. Проблема теперь стала дополнительной проблемой 100-этажных этажей с 2 ​​яйцами. Если я сейчас нахожусь на каком-то y-м этаже - его худший случай должен быть n-1. (n - 1) -й этаж удовлетворяет этому.

Следовательно, вы получите шаблон в nth , n + (n -1 )th floor , n + (n - 1) + (n - 2)th floor.... Решите это на 100-м этаже, и вы получите N. Я думаю, что пол, с которого вы начинаете, и нет: поисков.

Чтобы получить максимумы n = 14, вы можете подумать о том, что у вас есть n лампочек с двумя лампочками, которые светятся сразу. Это потребует, по крайней мере, 14 ламп, чтобы покрыть все возможные комбинации, где яйцо может сломаться.

Как вызов, попробуйте сделать это на 3 яйца.

В вашей логике в основном есть асимметрия в том, как продвигается поиск. Для первого набора из 10 элементов алгоритм быстро обнаруживается. Я бы предложил попробовать и проверить

http://ite.pubs.informs.org/Vol4No1/Sniedovich/ для некоторого объяснения, а также попытайтесь представить себе, как эта проблема видна в реальных случаях сетей.

Ответ 5

Очень приятное объяснение решения, которое я нашел в приведенной ниже ссылке. Проблема с двумя яйцами

В нем объясняется, как вы добираетесь до n+(n-1)+(n-2)+...+1<=100
Задача 1 Яйца - линейная сложность O (100)
и множественные (бесконечные) яйца - Логарифмическая сложность O (log2 (100)).

Ответ 6

Вот решение в 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)

Ответ 7

Вопрос не в том, сколько капель вам нужно сделать? но вместо этого нужно найти минимальное количество капель, чтобы знать, где яйцо ломается, я видел эту проблему в отношении опеки, ниже приведены алгоритмы, которые я думал:

Существует два способа решения этой проблемы:

• бинарный поиск первого яйца (рискуя знать, где нам нужно искать up) O (двоичный журнал)
• Поиск последовательности фибонакки 1,2,3,5,8,13,21,34,55,89 для первого яйца O (log) http://en.wikipedia.org/wiki/Fibonacci_search_technique

Как только первое яйцо сломано, мы знаем, в каком интервале нам нужно искать:

• двоичный пример:

  попробуем 100/2 (50), если он сломается, мы ищем от 1 до 50, увеличивая на 1, если мы не выбросим его с 50 + 100/2 (75), если он сломается, мы ищем от 50 до 75, если не будем бросать он от 75 + 100/2 (87), если он сломался, мы ищем от 75 до 87, на один этаж за один раз и т.д. и т.д.

• Пример фибонатности: то же самое: мы пробуем 1,2,3,5,8,13,... если первое яйцо мы вернемся к последнему минимальному интервалу и прибавим на 1.

Ответ 8

Эй, как насчет этого подхода.

Попробуйте следующую последовательность:

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

И как только вы обнаружите, что яйцо сломано, вы хорошо получаете место для работы. позволяет предположить, что перерыв в 64 яйцах. тогда ответ лежит между 32 и 64.

Мы можем использовать обычный бинарный поиск между этими двумя номерами. мы проверим @48 (32 + 64)/2, а затем мы получим верхнюю половину или нижнюю половину как короткое место. и повторите

В этом случае наихудший случай имеет пол в 99. Это займет 14 попыток.

Ответ 9

Из-за объяснения проблемы с двумя яйцами в первый раз некоторые люди могут запутаться, поэтому мы можем понять решение следующим образом: учитывая, что x - это пол, мы начинаем сбрасывать яйца: - если оно сломается, общее количество испытаний в худшем случае это х + (х - 1) - Если он не сломается, как мы должны перейти на следующий этаж? Мы можем перейти к полу (x + x) th, (x + x + 1) th... Но это увеличит количество испытаний, мы можем попробовать при x = 10:. Если он сломается, мы должны попытаться 10 раз в худшем случае. , Если он не сломается, и мы поднимаемся до 10-го + 10-го = 20-го и пытаемся, а если он сломается, мы должны попробовать 1 (на 10-м этаже) + 1 (на 20-м этаже) + 9 = 11 раз. Точно так же, если мы поднимемся до уровня x + 1 или x + 2, это увеличит количество испытаний. На самом деле, мы хотим, чтобы количество судебных процессов было одинаковым в обоих случаях, поэтому мы будем подниматься до x - 1 этажа вместо x, x + 1. и т.д. Наконец, у нас будет общее выражение: x + (x - 1) + (x - 2) +... + 1. И это оно.

Ответ 10

Я думаю, что решение может быть достигнуто с 13 шагов.

Оптимальная последовательность этажей, из которых мы бросаем первое яйцо: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99

Предполагая, что мы разбиваем 1-е яйцо @14, мы проверяем: 1,2,3,4,5,6,7,8,9,10. Пока что мы выпустили 11 капель, разбив только одно яйцо. Теперь мы проверим 12-й этаж (и это наш 12-й шаг): если яйцо разбивается, то самый высокий этаж - 11 (находится на 12 шагах); если яйцо не разбилось, то мы проверяем этаж 13. Если яйцо разбивается, то мы нашли 12-й этаж за 13 шагов, если яйцо не разбилось, то мы нашли 13-й этаж за 13 шагов. Помните, что мы проверили 14-й этаж в самом начале, разбив 1-е яйцо.

Теперь, давайте попробуем пол 95: 1-й разбивание яиц на 99-м этаже (11 шагов): проверьте этаж 97, аналогично тому, как мы делали на 12-м этаже: если 97 разбивается, то мы нашли самый высокий этаж 96. (12 шагов ) Если 97 не сломается, то мы проверяем 98 (13-е шаги), выбираем 97 или 98 соответственно разбиванию яиц или нет.

Эта процедура может быть применена к любому другому полу оптимальной последовательности, всегда сохраняя один шаг в конце.

Ответ 11

Я бы сказал, что оптимальное решение для 100 этажей с двумя яйцами - 13 попыток. 14.
13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100 - оптимальный ответ, но если я дойду до 99, мне действительно не нужно опробовать 100. Очевидно, правильный ответ, не пытаясь отбросить яйцо со 100-го этажа: D