Итак, ИТТ - задача из собеседования в кремниевую долину:
>Есть дом в некоторое число этажей и некоторое число яиц, которые разбиваются, если их бросить с определенной высоты. Яйца можно выбрасывать из окна и использовать снова, если они не разобьются. Найти минимальное число бросков, за которое можно вычислить эту высоту.
Допустим, есть дом высотой два этажа и одно яйцо, тогда ответ - 2.
ТРИ УРОВНЯ ЗАДАЧИ, ОТ ПРОСТОГО К СЛОЖНОМУ
1. Два яйца и дом высотой в 100 этажей
2. Три яйца и дом высотой в произвольное число этажей
3. Общая формула для случая с 4-мя и более яйцами. Бонус за простой алгоритм для произвольного числа яиц
>Конкурс на имя самого умного двачера объявляется открытым.
1.
>ум это способность знать какую то дисциплину
лол
>задача из собеседования в кремниевую долину
Вся суть всех этих ебнутых собеседований:
> нужны специалисты, которые будут пилить круды и админки для нашего стартапа
> справшиваем хуету про круглые люки, яйца и сколько мячиков помещается в автобус
> удивляемся, почему наши круды говно, лагают и глючат
> которые разбиваются, если их бросить с определенной высоты.
>Яйца можно выбрасывать из окна и использовать снова, если они не разобьются.
>1. Два яйца и дом высотой в 100 этажей
>2. Три яйца и дом высотой в произвольное число этажей
>3. Общая формула для случая с 4-мя и более яйцами. Бонус за простой алгоритм для произвольного числа яиц
Этажи/2 - тестим яйцо. Повторить в верх или в низ в зависимомти от результата.
Золотое сечение.
вот этого двачну
Сбросил с 50-го - разбилось. Сбросил с 25-го - разбилось, всё яйца закончились, искомый номер был 9.
Хуйню какую-то написал. Не важно, сколько у тебя яиц, если нужно найти мин. число бросков, стратегия расчёта от этого не изменится. Уже выше написали, высота / 2, а там по результату новая высота / 2.
Не работает
Почему?
Это оптимальный алгоритм. Не факт, что каждый раз найдется решение, но можно сузить область поиска. пиздец, такие очевидные вещи зумерам надо пояснять
Нахуя нужен алгоритм, который находит решение в 2% случаев?
И? Это оптимальный вариант найти высоту.
>>246922270
Верно, тралина. Или пруфаешь своим решением, или задача решена.
Тред не читал, в математике и пограмировании ничего не понимаю. Задача стоит "Найти минимальное число бросков, за которое можно вычислить эту высоту":
Два броска. Кинули с третьего, яйцо не разбилось, кинули с четвертого - разбилось.
>>246922329
Может есть еще чуть более оптимальный чем этаж/2 но 100% решения нет.
Один бросок. Они разобьются при падении с любой высоты.
Кидаем с 10. Если разбилось, берём второе яйцо и с 1 по 9 тестим. Если уцелело, идём на 20. Уцелело? Идём на 30. И т.д. пока не разобьется. Изи алгоритм.
Если кол-во яиц x >= log2(n), где n - кол-во этажей, то чекаем этаж по принципу двоичного кодирования, т.е. n/2 и кидаем. Если уцелело, то промежуток от n/2 до n делим на 2, кидаем и повторяем алгоритм.
Если кол-во яиц < логарифма, то скачем по второму алгоритму, пока не останется одно яйцо. А там уже в промежутке оставшемся по первому алгоритму находим
Мимочмоха, не прогер.
Ебашим яйцо с кол-ва этажей на 2, если разбилось, забиваем на те, что выше, не разбилось - ниже. Повторяем пока не очтанется одно яйцо. Далее тупо перебираем по очереди этажи, на которые не забили
>1. Два яйца и дом высотой в 100 этажей
Бросаешь первое йацо с 50-ого - если разбилось - начинаешь бросать с 1-ого этажа второе йацо до этажа разбития. Если не разбилось, то бросаешь второе с 51 до этажа разбития. В итоге сложность O(n/2), в худшем случае 49 бросков. Вряд ли есть вариант оптимальнее. Над остальными уровнями задачи думать лень.
мимо прогер 12 лет опыта.
а ты докажи что это оптимальное решение
Вот тут >>246922859 самый хуевый случай 18 бросков.
Ну ты и дебс
Почему?
2. Не существует решения
3. Тут вообще условие кривое
Есть.
>>246923172
Да, по сути бинарный рекурсивный поиск (я не дописал в >>246923086, что можно продолжить и искать бинарно пока первое йацо не бито). Но для первого условия задачи (два йаца сто этажей) худший кейс - 49 бросокв.
Решение есть и оно простое, можно на калькуляторе в запросто посчитать даже для нескольких яиц и дохуища этажей любой случай в одну строчку.
>>246923470
Не сагай мразь.
>Сбросил с 50-го - разбилось. Сбросил с 25-го - разбилось, всё яйца закончились, искомый номер был 9.
НУ значит еще можно яиц в магазине купить, хули ты такой тупой?
>Но для первого условия задачи (два йаца сто этажей) худший кейс - 49 бросокв.
Какие нахуй 49? Если кидать через 10 этажей, а как разобьется то проверять вторым яйцом по этажу, то в самом хуёвом случае, когда нужный этаж 100, потребуется 18 бросков. На 10, 20, 30, 40, 50, 60, 70, 80, 90, 91, 92, 93, 94, 95, 96, 97, 98 и 99 этажах.
Есть, но в первом должно быть минимум 7 яиц,а во-втором этажей максимум 8
Уже был в таком треде пол-года кажись назад.
Вот решение для двух яиц и 100 этажей:
первое яичко скидываем поочередно с 14 этажа, потом на 13 этажей выше, потом на 12 этажей выше, потом на 11 и так до 99 когда яичко разобьется мы найдем промежуток
Вычислив промежуток, например, пятый, мы поочередно скидываем второе яичко с минимального по максимальный этаж, пока оно не разобьется
формулу сами можете написать
Для остальных случаев решение аналогичное
/тред
>мы поочередно скидываем второе яичко с минимального по максимальный этаж
этого промежутка
быстрофикс*
https://datagenetics.com/blog/july22012/index.html
Мимо-ходил в гугл в Дублине, остановился на фейсбуке там-же
Сажи дауну
А, забыл про произвольное число этажей.
Берём корень из n и округляем в большую сторону, например для 300 шаг будет 18. И работаем по прежним чертежам
кол-во яиц - 1 определили сколько попыток.
Если попыток > 0
Oпределяем минимальную высоту. высота/2 далее в зависимости от результата и кол-ва попыток.
С последним яйцом как дауны поднимаеся либо от 1го этажа либо от последней высота/2 с которой не разбилось.
Да, примерно так.
Но если улучшить этот способ, то самый оптимальный вариант будет такой - >>246923804
>собеседования в кремниевую долину
А нахуй оно нужно? Там же кодинговые мартышки обитают. Зачем им мыслить в реальном времени, решать какую-то хуйню? Без негатива даже
Нихуя. У тебя матожидание все равно будет стремиться к большему количеству бросков, даже с учетом того, что худший случай меньше бросков.
У этих кодинговых мартышек зп от 100к$ в год. Ты столько за всю свою жизнь не сможешь зарабоать, пидорашка.
Так, и че?
поржал с нищей спидеращки, ббгггг.
мимо держу галеру с нищими спидоранами и хахлами
Оче просто:
Кидаем окно с первого этажа - оно разбивается. Вот и выяснили.
То, что они умнее тебя во столько же раз, во сколько больше их зп и соотвественно умения.
Кидаем яйцо, конечно же, бля*
Минимально потребуется два броска. Первым мы рандомно угадываем нужную высоту, вторым кидаем на 1 этаж выше, оно разбивается, максимальная высота найдена.
Если пытаться в алгоритмы, то в первом случае прост кидаем яйцо на значения кратные двум, пока не разобьётся, а вторым кидаем на 1 меньше того, где разбилось. Второй аналогично, но кратное трём. Третий думаю уже поняли.
Как эта задача выглядит ИРЛ определи с какого этажа яйцо разобьется. Бить яйца нельзя.
мимо нищий рабсиянин
>Если пытаться в алгоритмы, то в первом случае прост кидаем яйцо на значения кратные двум
У тебя два яйца, кидай на кратные трем.
Кинул с третьего - разбилось.
Кидаешь со второго - разбилось, значит искомый этаж - первый.
берем бросаем методом разделяй и властвуй k - 1 раз
в самом хуевом случае если все k - 1 яиц разбились остается интервал n / (2 ^ (k - 1)). опять же в самом хуевом случае в конце этого интервала искомый этаж, тогда понадобится n / (2 ^ (k - 1)) - 1 бросков.
итого (k - 1) + n / (2 ^ (k - 1)) - 1 бросков в худшем случае
естественно вся эта хуйня работает если в справедливо раз n больше чем k, нужно рассмотреть отдельные случаи
Про говночистов по дворце Путина не в курсе, школьник? Сколько у них там зп?
Допустим у тебя N этажей и M яиц.
Перебираем этажи здания снизу с переодичностью M если яйцо не разбилось, то высота лежит выше, если разбилось, то мы нашли промежуток длинной M в котором находится искомая высота. Дальше итерируем на найденом промежутке, так оставшихся яиц хватит.
Чего-то я не вдупляю. Я могу перейти на любой этаж?
Если так, то в чем проблема, всегда требуется 2 броска.
Кидаем с первого этажа, замеряем время до падения, предположим 7 секунд. Идем на последний, кидаем, замеряем. 70 секунд. Делим время последнего этажа на первый, т.е. 70/7 получаем 10 этажей. Можно чутка округлить, поскольку бросаем с половины этажа, а не с начала.
Нужно найти высоту с которого яйцо разобьется?
Ну тогда везде 1
Двачую
бросаем яйцо с серединного этажа, если разбилось, то кидаем его с с этой высоты, поделенной на два, если не разбилось, то с соответственно, в середине между верхним этажом и изначальным. повоторяем, пока не останется одно яйцо, которое мы докидываем единичками поднимаясь от наивысшей позиции, откуда яйцо не разбивалось
Хуита какая то, у тебя же всегда будет получаться озф и ты не будешь знать с какого конкретно этажа начинается >пук
ОП, в чем я тут не прав? >>246925064
Да, тебе нужно найти этаж с которого яйцо при падении разобьется. Идешь на первый этаж - бросаешь - яйцо разбилось? да ты нашел нужный этаж высоту, нет ты идешь на второй этаж и бросаешь оттуда. Твоя задача придумать способ чтобы не обходить каждый этаж
Хотя я хуй знает как это сделать, тут предлагают бинарный поиск но как он тут помогает, если условие составлено так что этаж может быть рандомным
Просто идешь на последний
>которые разбиваются, если их бросить с определенной высоты
Ну я так понял это значит что яйцо разобьется только если его бросить, например, с 50 этажа, а вот с 51 уже не разобьется.
Ну и причем тут тогда этажи?
Чет хуйня какая-то, не привязанная к реальности. Лови реальную задачу. Тебе нужно рассчитать движение тела в произвольном сильном гравитационном поле согласно ОТО, какую систему уравнений ты засунешь в ODE solver? Гравитационными волнами и вращением можно пренебречь
Бинарный поиск единственное, что тут можно.
А двух людей можно использовать? Или сетку на балкон растелить, чтобы поймать
Это что, требуется для веб дизайнеров такое?
2 чая
Да, нарисовать систему Гаргантюа из интерстеллара с помощью html5
А смысл бинарного поиска? Ну что тебе даст что яйцо упавшее с 50 этажа не разбилось? Что нужно идти вниз? Или вверх? Ты не будешь сужать поиск. Просто исключать этаж при каждом броске, но такого эффекта ты добьешься если будешь просто подряд перебирать этажи
Бинарный поиск по этажам пока не останется одна попытка. Когда остается одна попытка, кидаем с нижнего уровня последнего окна бинарного поиска до верхнего с шагом в 1 этаж. В таком случае мы не проебем последнее яйцо так и не узнав ответ, как другие дауничи из этого треда.
>А смысл бинарного поиска?
Дает максимальный процент поиска
но возможно оп пидрила затралил нас всех
>но возможно оп пидрила затралил нас всех
Загуглите задачу и все. Если ее нет в инете, оп врет
Да? Не знал. Я думал он просто позволяет сузить область поиска в отсортированных данных отсекая с каждым шагом половину. Но если есть доказательство что так ищется лучше, то не буду спорить
Это задача на понимание методов оптимизации
тащем то понимать этц хуйню взрослому нормальному человеку не обязательно, исключительно ит фича
Загуглил, оп неправильно условие задачи дал
Дано 100-этажное здание. Если яйцо сбросить с высоты N-го этажа (или с большей высоты), оно разобьется. Если его бросить с любого меньшего этажа, оно не разобьется. У вас есть два яйца. Найдите N за минимальное количество бросков.
Вот эту часть он не написал. Пидар
Хмм, тогда кидаем с половины, оставшуюяс часть прочесываем с первого этажа
>1. Два яйца и дом высотой в 100 этажей
семь?
https://tproger.ru/problems/two-egg-hundred-floors/
Вот разбор если интересно
Бинарный поиск, число бросков O(n) = log2(n)
/thread
Ты че, еблан? Если яйцо уронить с высоты метра - оно разобьется. При чем тут этажи тогда нахуй? Отсоси.
Мой ответ: ОП -ХУЙ
ответ: 1 бросок. берем самый высокий этаж и кидаем оттуда
/thread
Хинт к решению - треугольные числа, n(n+1)/2.
В таком треугольнике любая точка достигается за минимум ходов.
Следующий уровень - треугольники, где каждая линия тоже представлена треугольником, и так до k уровней вложенности.
Вы что тут все тупые?
Просто кидаете яйцо с первого этажа и по возрастающей, пока оно не разобьется.
Пиздец, что я тут делаю с этими имбицилами.
Там требуется минимизировать число бросков, в твоём случае оно будет 99. Можно найти за 14.
Минимизировать максимальное
Быстрофикс
Не сработает - например, для 2 яиц и высоты в 15.
>Можно найти за 14
Пруфы?
Это чисто алгоритмические задачи, мне лень.
Бросить первое яйцо с 14. Если разбилось, то искать с 1, если нет - то бросить с 27, и т.д.
Говорю же, треугольные числа надо применять >>246932147
Да, звучит логично.