"Супер яйца"

[Balash]

Задача:
Пусть у вас есть 2 супер-яица и вы живете в 100-этажном доме.  Известно, что любое супер-яйцо не разбивается при броске с первого по некоторый этаж.  Вам необходимо определить за которое наименьшее количество бросков можно однозначно определить самый большой номер этажа, с которого брошенное вниз супер-яйцо не разобьется.  Обратите внимание, если в результате некоторой попытки яйцо не разбилось, то оно может быть использовано в последующих попытках.
Ответ 14.
Подскажыте как получить такой результат, какой алгоритм исполизовать?

[hripunov]

Попробую объяснить это на корявом, не математическом языке...

У нас есть возможность  разбить два яйца. Тогда оптимальная процедура состоит в том, чтобы разделить все этажи на неравные интервалы, отличающиеся друг от друга на 1.
Первое яйцо бросаем с 14 этажа, затем /если яйцо не разбилось/ с 27-го, то есть, кажый раз уменьшаем интервал на 1
Интервалы  между бросками первого яйца, если оно не разбивается, таковы: 14, 13, 12, 11, 10, 9, 8, и т.д.
 Если яйцо разбивается, у нас есть возможность начиная  с этажа , который на один выше последней удачной попытки, бросать второе яйцо, каждый раз поднимаясь на один этаж, пока оно не разобьется. И в любом случае количество бросков не превысит 14.

[Balash]

А если имеется n яиц и k этажей, то как найти ответ? Например 10 яиц и 786599 єтажей - ответ 21.

[Смекалистый]

Идея точно такая же, действуем по индукции.

Обозначим S(i,j) - кол-во этажей, которое можно проверить с помощью i яиц и j бросков.

1) n=1
Очевидно S(1,0)=0, S(1,1)=1,....,S(1,i)=i,....
Нужно найти наименьшее m такое, что S(1,m)>=k
m>=k
Значит, m=k.

2) n=2
Возьмем m интервалов с длинами:
(1+S(1,m-1)), (1+S(1,m-2)),..., (1+S(1,1)), (1+S(1,0))
Нужно найти наименьшее m такое, что
S(2,m)=(1+S(1,m-1)) + (1+S(1,m-2)) +...+ (1+S(1,1)) + (1+S(1,0)) >= k

1) Проверим этаж (1+S(1,m-1)).
Если разбилось, то за m-1 бросков 1 яйцом проверим S(1,m-1) этажей
Итого в худшем случае: 1+(m-1)=m бросков.

2) Проверим этаж (1+S(1,m-1)) + (1+S(1,m-2)).
Если разбилось, то за m-2 бросков 1 яйцом проверим S(1,m-2) этажей
Итого в худшем случае: 2+(m-2)=m бросков.

.... и т.д..........

m-1) Проверим этаж (1+S(1,m-1)) + (1+S(1,m-2)) +...+ (1+S(1,1)).
Если разбилось, то за 1 бросков 1 яйцом проверим S(1,1) этажей
Итого в худшем случае: m-1+1=m бросков.

m) Проверим этаж (1+S(1,m-1)) + (1+S(1,m-2)) +...+ (1+S(1,1)) + (1+S(1,0))
Итого: m бросков.

Для n=2 можно получить формулу:

S(2,m) = (1+(m-1)) + (1+(m-2)) + .... + (1+1) + 1 = m(m+1)/2
Нужно найти наименьшее m такое, что m(m+1)/2>=k.
Для n=2, k=100:
13*14/2<100
14*15/2>=100
Значит, m=14.


3) n=3
Нужно найти наименьшее m такое, что
S(3,m)=(1+S(2,m-1)) + (1+S(2,m-2)) +...+ (1+S(2,1)) + (1+S(2,0)) >= k

i) n=i
Нужно найти наименьшее m такое, что
S(i,m)=(1+S(i-1,m-1)) + (1+S(i-1,m-2)) +...+ (1+S(i-1,1)) + (1+S(i-1,0)) >= k


S(i,j)=(1+S(i-1,j-1)) + (1+S(i-1,j-2)) +...+ (1+S(i-1,1)) + (1+S(i-1,0))
Заметим, что:
S(i,j)=(1+S(i-1,j-1)) + S(i,j-1)

Теперь получается такой алгоритм вычисления:
Вычисляем ряды чисел:

S(1,0)     S(1,1)    S(1,2)  ...  S(1,j-1)     S(1,j) ...  S(1,k-n)
S(2,0)     S(2,1)    S(2,2)  ...  S(2,j-1)     S(2,j) ...  S(2,k-n)    S(2,k-n+1)
...........
S(i-1,0)  S(i-1,1)  S(i-1,2)  ... S(i-1,j-1)  S(i-1,j) ... S(i-1,k-n)  ...............  S(i-1,k-n+i-2)
S(i,0)     S(i,1)     S(i-1,2)  ... S(i,j-1)     S(i,j)    ... S(i,k-n)  ...............     ...............      S(i,k-n+i-1)
......................................
S(n,0)     S(n,1)    S(n,2)  ...  S(n,m-1)<k     S(n,m)>=k ..........................................S(n,k)


S(i,j) равен элементу слева + элемент слева-сверху + 1

В n-м ряду остановимся, когда S(n,m-1)<k     S(n,m)>=k,  m - ответ.



С программной точки зрения нужно 2 массива:

Spred длиной k+1 - S "предыдущее"
Stek длиной k+1   - S "текущее"


Псевдокод вроде этого:

Spred={0,1,2,....,k-n}  // заполнить числами S(1,0), S(1,1),...,S(1,k-n)
l=k-n                         // номер последнего элемента

Цикл1: i=2..n
    Stek[0]=0

    Цикл2: j=1..l+1
        Stek[j]=Stek[j-1]+Spred[j-1]+1;
    Конец цикл2

    Spred <-> Stek //поменять местами
    l=l+1
Конец цикла1

Если интересно, то есть код программы на Java во вложении. Ответы совпали 

[Balash]

Большое спасибо за ответ.

[zer0]

Задача с сайта braingames.ru:
У Мегамозга есть два одинаковых стеклянных шарика. За какое минимальное число бросков можно гарантированно определить, начиная с какого этажа 100-этажного здания шарики разбиваются? 1 и 2 правильными ответами не являются! Пишите решение.

Типа "я тут спрошу, а там отвечу"...

[Entspannen]

Прошу прощения за глупость, но никак не могу понять, какая именно формула будет для 3 яиц и 231 этажа. И по какому принципу будет проверяться для 3 яиц?

[ira-sm]

Задача с сайта braingames.ru:
У Мегамозга есть два одинаковых стеклянных шарика. За какое минимальное число бросков можно гарантированно определить, начиная с какого этажа 100-этажного здания шарики разбиваются? 1 и 2 правильными ответами не являются! Пишите решение.

Типа "я тут спрошу, а там отвечу"...

Это очень старая задача. Не удивительно, что Вы ее можете найти на разных сайтах в различных вариациях (типа, яйца, шарики и т.п.). Вовсе не значит, что автор один и тот же.

[ira-sm]

А если имеется n яиц и k этажей, то как найти ответ? Например 10 яиц и 786599 єтажей - ответ 21.

Скажите, а по какому предмету Вам задали задачу (для произвольного числа яиц)?
Если по информатике, то алгоритм уже был представлен в этой теме.
Если по алгебре, то у меня получилось длиннющее уравнение для нахождения числа попыток. Пока не представляю себе как его можно решить.
Для вашего примера:
(x^10+x^9+4x^8+8x^7+16x^6+32x^5+64x^4+128x^3+256x^2+512x)/512=786599

[Entspannen]

По избранным главам теории чисел. Там аналитически доказывается через реррентную формулу. для 2, 3 яиц просто оказалось, а вот дальше - не знаю

[YERokez]

Хм...А если яйца не бъются в принципе? Золотые...

[Леонид]

Хм...А если яйца не бъются в принципе? Золотые...

Тогда пилите.