Путаница с двумя яйцами

Question

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

• Вам дают 2 яйца.
• У вас есть доступ к 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 (преобразование этой функции выполняется с арифметической серией точной суммой арифметической последовательности), теперь, если вы решите для 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

Правильное и оптимальное решение - 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 4

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

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

Answer 5

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

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

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

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

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

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

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

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

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

В качестве задания попробуйте сделать это за 3 яйца.

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

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

Answer 6

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

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

• бинарный поиск первого яйца (рискуя узнать, где нам нужно искать вверх) O (двоичный журнал)
• Поиск последовательности Фибоначчи 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 до 50, увеличивая на 1, если не бросаем его с 50 + 100/2 (75), если он ломался, мы ищем от 50 до 75, если не бросаем это от 75 + 100/2 (87), если оно сломалось, мы ищем от 75 до 87, начиная по одному этажу за раз, и так далее, и так далее.

2. пример фиброзности: то же самое: мы пробуем 1,2,3,5,8.13, ... если первое яйцо сломал мы возвращаемся к минимуму последнего интервала и увеличиваем на 1.

Answer 7

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

Объяснение проблемы с двумя яйцами в первый раз может сбить с толку некоторых людей, поэтому мы можем понять решение следующим образом: учитывая, что x - это пол, мы начинаем сбрасывать яйца: - если оно сломается, общее количество испытаний внаихудший случай - x + (x - 1) - Если он не сломается, как мы должны перейти на следующий этаж?Мы можем перейти на пол (х + х) й , (х + х + 1) й ... Но это увеличит количество испытаний, мы можем попробовать при х =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. И все.

Answer 9

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

Answer 10

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

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

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

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

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

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