Взял на курсере курс по алгоритмам. Курс состоит из задания без оценки и с оценкой. Те, что без оценки нужны лично для тебя и их никто не проверяет. Что-то типа факультатива.
Один из таких вопросов вызвал затруднение :



Нулевой вопрос понянет - просто идём перебором снизу вверх
Первый тоже понятен. Количество попыток равно количеству яиц и яйца нет нужды экономить.

Вот начиная с второго затруднения несмотря на подсказку.

n-количество этажей и оно известно
T-минимальный этаж начиная с которого яйцо разобьётся
Я так понимаю у нас есть lgT яиц и 2* lgT попыток.

Если вдруг яйцо бьётся с первого этажа, то количество яиц будет 0 - это странно... и попыток тоже
Если вдруг яйцо бьётся с второго(третьего) этажа, то количество яиц будет 1 а попыток 2
Если вдруг яйцо бьётся с четвертого(5 6 7) этажа, то количество яиц будет 2 - а попыток 4
Если вдруг яйцо бьётся с восьмого(до 15) этажа, то количество яиц будет 3 - а попыток 6


Что-то я в буквах этих запутался. Подскажите пожалуйста стратегию

в интернетах нашёл решение:

авторVersion 2
Start test at floor 0 and exponentially grow (2^t) floor number until first egg
breaks. The value of T must be between 2^t and 2^(t-1). This range can then
be searched in ~lgT tosses using the technique from version 1.

Допустим ответ это 17 этаж.

По этой логике проверяем

1 2 4 8 16 32 (6 попыток)

на 32 понимаем, что яйцо бъётся

Делаем вывод, что искомый этаж с 17 по 31.

Ищем бинарным поиском:

17+31 = 48

Проверяем (17+31)/2 = 24. Не бъётся значит 17-23
Проверяем (17+23)/2 = 20. Не бъётся значит с 17 по 19
Проверяем (17+19)/2 = 18. Бъётся. Но может быть бЪётся и на 17
Проверяем 17 и удостоверяемся, что бъёься.

Итого получилось, что яиц потратили 4(lg17 = 4 - вписались), а попыток сделали аж 10. Что не есть 2 Lg(T). Ожидплось сделать это за 8 попыток.


Я что-то не так делаю?

забыл никДержи в курсе
обязательно)

Any thoughts?

ivanraПо-моему, все ждут, когда ты разбитые яйца пересчитаешь

В моём примере побилось 3. Даже одно осталось получается

Sergunka https://brilliant.org/wiki/egg-dropping/

здесь детальное объяснение по данной задачи.

А если русским по белому?