Смотрите, есть задача про броски яиц.
Допустим у нас есть n яиц и m попыток проверить. Я такой странный и хочу узнать с какого этажа разобьется яйцо. Ну и собственно, цель задачи - определить максимальный этаж для пары (n,m), с которого можно проверить с точностью 100% что яйцо разобьется.
Приведу свои рассуждения.
Пусть h(n,m) - максимальный этаж на котором можно со стопроцентной уверенностью говорить о том разобьется ли яйцо или нет.
Рассмотрим случай n||m==0, тогда, очевидно h = 0, т.к. если нет яиц или попыток, то мы не можем ничего проверить в любом случае. Таким образом h(0,0) = 0.
Так же заметим, что если число яиц больше числа попыток, то случаи когда есть лишние яйца можно не рассматривать,
т.е. при n>m h(n,m)= h(m,m)
Рассмотрим случай когда у нас всего одно яйцо. Опять же, очевидно, что в данном случае максимальный этаж который мы можем проверить определяется числом попыток. Т.е. h(1,m) = m.
Теперь давайте рассмотри случай, если яиц - два. В данном случае мы можем уже подниматься не на один шаг. Оптимально будет для каждой проверки делать шаг размером в количество оставшихся попыток до тех пор, пока одно из яиц не разобьется, затем спуститься на оставшееся пройденные с прошлого шага число этажей и проверять этот диапазон пока не найдем нужный этаж. Т.е. формально, h(2,m) = 1+ h(1,m-1)+ h(2, m-1).
Попробуем вывести общий случай. h(n,m) = 1 + h(n-1,m-1)+h(n, m-1), при n&&m > 1
Проверим, пусть у нас 2 яйца и 2 попытки.
Таким образом, h(2,2) = 1 + h(1,1) + h(2,1), т.е. 3. Если проведем это по шагам, то на первом шаге мы прошли с 0 этажа попали на 2, сделали порверку, независимо от результата, мы теперь можем подняться на 3й этаж, он и будет максимальным для данной пары яиц-попыток.
В общем как-то так.
Ну и собственно, мне интересно, правильно ли я рассуждал? Просто увидел эту задачку на кодворсе и дня два думал-думал. Вот, вроде придумал, закодил это а оно не проходит времени, т.к. числа оч большие ожидаются, плюс у меня там рекурсия, ну вы поняли, но для тестовых примеров что там даны, вроде норм. Ну и перед тем как оптимизировать решения, я хочу узнать правильно ли я рассуждал? Просто со школы задачек не решал и как-то подзабыл как это делается.
