Давненько задач не было. Заранее прошу прощения у тех, кто эту уже знает.


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

Нам нужно определить эту прочность с двумя лампочками и 100 этажами за минимальное число попыток (бросков). Вопрос: сколько попыток нам придется сделать в худшем случае (конечно, при оптимальном алгоритме)?


Сразу поясню: если бы у нас была одна лампочка, то ответ был бы 100 - нам пришлось бы сбрасывать с 1го этажа, затем 2го и т.д. Если много лампочек, то ответ 7 - поскольку мы бы каждый раз делили оставшиеся этажи пополам, а 100 < 2^7.

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

Задачку буду решать с утреца, т.к. ща уже мозги не варят.
А вот можно узнать, под какой торговой маркой продаются лампочки, которые выдерживают падение с 31-го этажа? Я бы купил. А то наши лампочки не выдерживают падения и с метровой высоты.

У мя не варят даже чтоб понять, о чем речь...

Речь о том, как закидывать с балкона прохожих особо прочными лампочками.

с каждого третьего этажа? Вообще-то, я всегда думал, что основная характеристика лампочек выражается Ваттами а не этажами...

Не смог придумать ничего более оригинального, чем бросить пербю лампу с 50го этажа, а вторую потом бросать начинаяя с 1го или 51го в зависимости от результата.
Как то оно слишком просто. Наверняка задачка с хитростью.
Тьфу, глупость сморозил.

This post has been edited by genka on 28-02-2006, 23:02

Не могу уделить на подумать больше чем 5 минут - ночь все-таки...
За 19 раз знаю как (первую кидаем с шагом 10 этажей, разбивается на сотом, затем 91, 92.... 99 этаж разбивает вторую лампочку). Но стопроцентно можно и меньше раз кидать.
Тут надо учесть, что если решили кидать первую лампочку с шагом в 10 этажей, то после неразбития лампочки, к примеру на 10-м этаже шаг должен меняться - так как перед нами стоит новая задача про две лампочки и 90 этажей. Со следующим неразбитием задача опять новая.

Заранее извиняюсь за мой французский, но речь идет о том, как зах.ярить Иран коврово-лампочными бомбардировками, не разбив при этом ни одной лампочки.

прошу прощения... отстал от жизни..заработался... может кто-нить обьяснить кто собирается бомбить Иран и зачем?... уже не в первый раз слышу... и в новостях не пишут ничего... а может плохо искал...

Задача сводится к поиску минимального значения среди худших попыток при разном шаге. Получаем формулу max_step = 100/N + N - 1. Получаем при выборе шага от 8 до 13 максимальное число попыток равно 19. При выборе шага меньше или больше число попыток увеличивается.

ответ неверный.
Шаг не должен быть равным, ибо после первой-же попытки количество этажей и оставшихся попыток меняется.

Поясню -
кидаем с 10-го этажа: если разбиласть, то кидаем с 1, 2, 3...9 пока не разобьется. Максимум 10 попыток.

Если не разбилась, то кидаем с 19-го этажа. Не с 20-го! Если разбилась, то кидаем с 11, 12,..., 18 пока не разобьется. Максимум 10 (2+max of 8) попыток.

Если не разбилась - кидаем с 27-го. Если разбилась, то кидаем 20, 21, 22...26 пока не разобьется. Максимум 10 (3+ max of 7) попыток.

Как видите, при такой стратегии сохраняется количество попыток при начальных неудачных бросках. Однако, первоначальный бросок с 10-го этажа не самый эффективный. Ибо здание закончится на 55-м этаже. А для 100 этажей надо начать с...

Если f(N) - искомое число бросаний, то f(1)=1 и

f(N) = min_{0<n<N} max(n-1, f(N-n)+1)

Поэтому f(100)=13, и начинаем с 12, 13 или 14 этажа

100 = (А1 + An)*n/2; A1=1, n=An => An^2 + An = 200, решаем........ Done
Итого : если начнём с 14 этажа - всё получится, но, поскольку 14*15/2 = 105, то интуитивно кажется, что можно как-то улучшить результат
Тогда пытаемся начать с 13, но 13*14/2 = 91, и у нас ничего не выходит...
Что делать ?

Например, усмотреть, что вышеуказанное функциональное уравнение выполнено для вот такой F(N):

{ для n>1 выполнено F( n(n+1)/2 - 1 ) = n, а для во всех остальных N имеет место F(N)=F(N-1) }

и показать, что решение у этого уравнения единственно (что просто)

Edit: AAA! На самом деле F( n(n-1)/2 + 1 ) = n

This post has been edited by kpot on 01-03-2006, 23:59