Помогите найти алгоритм

← →
Vasya.ru © (2005-03-05 23:13) [0]

есть формула N <= (L*(L+1)*...*(L+K)) / K!, N, K известны, и меньше 1 000 000 000. Надо вычислить L, ясно, что прогонять в цикле L и искать подходящее значение не дело. Уже 4 дня бьюсь, но что - то никак не додумаюсь, как это по другому рассчитать

← →
GuAV © (2005-03-05 23:42) [1]

N <= (L*(L+1)*...*(L+K)) / K!,

При L = 1 числитель равен K! * (K+1)
При L = 2 числитель равен (K! * (K+1)) * (K+2) / 1
При L = 3 числитель равен (K! * (K+1)) * (K+2) / 1 * (K+3) / 2
При каждом L числитель равен <предыдущий_числитель> * (K+L) / (L-1)
Думаю лучше чем прогонять в цикле не придумаешь.

← →
Vasya.ru © (2005-03-05 23:49) [2]

Думаю лучше чем прогонять в цикле не придумаешь
проблема в том, что N, K известны, и меньше 1 000 000 000, цикл будет дооолго работать, пока переполнение типа не произойдет

← →
GuAV © (2005-03-06 00:14) [3]

Может попробовать оценить L, и потом искать перебором или бин поиском в известых границах.

N*K! <= (L*(L+1)*...*(L+K))

если L > 1, то

(L+K)^K > (L*(L+1)*...*(L+K)) > L^K

(L)^K > (L*(L+1)*...*(L+K)) => N*K! ,следовательно L < (N*K!)^(1/K) - K

← →
GuAV © (2005-03-06 00:16) [4]

В написанном в [3] сомневаюсь, но что-то подобное можно попробовать...

← →
Vasya.ru © (2005-03-06 11:38) [5]

мда, прийдется искать принципиально другое решение задачи

Лучше исходную задачу скажи, а то уже второй пост с большими факториалами пишешь...

Вместо факториалов можно попробовать суммы логарифмов.

//интересно, почему я добрый такой? procedure TForm1.Button1Click(Sender: TObject); var F, K, L, N: int64; begin //есть формула N <= (L*(L+1)*...*(L+K)) / K!, N, K известны, //и меньше 1 000 000 000. Надо вычислить L (минимальное?) //ввод данных N:=1000*1000*1000; K:=1; //ищем L:=1; F:=1; // F(1) = 1 * (1+1) ... (1+K) div K! if (N<=0) or (K<=0) then begin L:=N; F:=N; end else while F<N do begin inc(L); F:=F * (K+L) div (L-1); end; //выводим ShowMessage(Format("%d %d %d %d",[F, K, L, N])); end;

Помогите найти алгоритм Найти похожие ветки