Сильно отредактировано из-за исправления вопроса
Рассмотрим функцию f (x, y), которая дает количество этажей, которые вы можете протестировать с ограничением x бросков и y смертей. Если первый бросок приводит к смерти, у вас есть броски x-1 и оставшиеся смерти y-1, так что вы можете проверить f (x-1, y-1) этажей. Если первый бросок не приводит к смерти, у вас есть x-1 бросков и y смертельных случаев, так что вы можете проверить f (x-1, y) этажей выше того, из которого вы бросили. Следовательно, мы имеем рецидив f (x, y) = f (x-1, y-1) + f (x-1, y) + 1. Базовые условия: f (x, 0) = 0 (потому что если Вы делаете даже один бросок, рискуете смертью, поэтому вы не можете делать броски и даже не можете проверить первый этаж), и f (1, x) = 1, где x> 0 (вы должны сделать единственный бросок из первый этаж, потому что если вы бросите с верхнего этажа и получите смерть, у вас не будет результата).
Теперь рассмотрим функцию g (x, y) = SUM 1 <= r <= y из <sup>x C r . (Это биномиальный коэффициент, х выберите г. Я не думаю, что нотация TeX поддерживается на этом сайте). Утверждение состоит в том, что f (x, y) = g (x, y). Чтобы проверить базовые случаи, рассмотрим, что g (x, 0) является суммой по 0 элементам, так что это соответствует; и g (1, y), где y> 0 дает 1 C 1 = 1. Поэтому остается только проверить, что g удовлетворяет повторению.
g (x-1, y-1) + g (x-1, y) + 1 = SUM 1 <= r <= y-1 <sup>x-1 C r + СУММА 1 <= r <= y <sup>x-1 C r + 1
g (x-1, y-1) + g (x-1, y) + 1 = СУММА 2 <= r <= y <sup>x-1 C r-1 + СУММА 1 <= r <= y <sup>x-1 C r + 1
g (x-1, y-1) + g (x-1, y) + 1 = SUM 2 <= r <= y <sup>x-1 C r-1 + СУММА 1 <= r <= y <sup>x-1 C r + x-1 C 0
г (х-1, у-1) + г (х-1, у) + 1 = СУММА 1 <= r <= у <sup>х-1 С р-1 + СУММА 1 <= r <= y <sup>x-1 C r
g (x-1, y-1) + g (x-1, y) + 1 = SUM 1 <= r <= y (<sup> x-1 C r-1 + x-1 C r )
g (x-1, y-1) + g (x-1, y) + 1 = СУММА 1 <= r <= y (<sup> x C r )
г (х-1, у-1) + г (х-1, у) + 1 = г (х, у)
QED
Фактически это может быть получено непосредственно, рассматривая это как комбинаторную проблему. Если мы в полной мере используем каждый бит полученной информации, то каждая возможная последовательность выживания или смерти соответствует разному максимальному полу. Например. для трех бросков одна допустимая смерть, возможна смерть; Выживание смерть; выживание выживание смерть; или выживание-выживание-выживание. Тем не менее, мы должны игнорировать случай, когда нет смертельных случаев, потому что в этом случае мы не определили пол. Поэтому, если у нас есть x бросков и y разрешенных смертей, у нас может быть фактическое количество смертей r от 1 до y, и для каждого из них у нас есть x C r возможных последовательностей. (Если r = y, то любые «пережитки» после смерти y th на самом деле «не бросили»).
Решение jdmetz для F состоит из оценки g (D, B). Это нельзя сделать за время, превышающее O (min (D, B)), поскольку для этой суммы не существует замкнутой гипергеометрической формы (этот факт можно доказать с помощью алгоритма Госпера).
Добавление
Фактически, все три части исходной задачи могут быть выполнены за линейное время (предполагая, что умножение и арифметика являются операциями с постоянным временем, что у нас пока - не правда, но мы оставим это в стороне). Операция O (n lg n) в решении jdmetz находит наименьший D такой, что f (D, B)> = F.
Если мы объединим наше первоначальное повторение f (D, B) = f (D-1, B-1) + f (D-1, B) + 1 с термином, отличным от вида g, f (D , B) = f (D, B-1) + D C B , получаем f (D, B) = 2 * f (D-1, B) + 1 - Д-1 C B . Затем мы можем использовать a C b = a-1 C b * a / (a - b) для обхода D из 1.
private static int d_opt(final long f, final int b)
{
int d = 0, dCb = 0;
long f_db = 0;
while (f_db < f)
{
dCb = (d == b) ? 1 : d * dCb / (d-b);
f_db = 2 * f_db + 1 - dCb;
d++;
}
return d;
}