Скачать: CL | DM;

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

← →
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]

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

---

← →
MBo ©   (2005-03-06 11:42) [6]

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

---

← →
Alx2 ©   (2005-03-06 11:45) [7]

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

---

← →
Sha ©   (2005-03-06 12:18) [8]

//интересно, почему я добрый такой?
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;


---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.025 c