Нужен совет: найти быстрый способ вычисления по формуле (1 сек) - Free Pascal
Формулировка задачи:
Помогите найти быстрый способ вычисления формулы C из n по k(n!/((n-k)!*k!)). Пробовал разложение на простые множители, не получилось, по времени часть тестов не проходит. Вот сам код программы:
type vector=array [1..1000] of byte; type TBytes=Set of byte; procedure SimpleNum(var a:vector;num:integer;c:TBytes); var i,j,k,l,m,n:integer; begin j:=2; while(num<>1) do begin while (num mod j=0) do begin if (num mod j=0) and (j in c) then begin inc(a[j]); num:=num div j; end end; inc(j); end; end; function Stepen(i:byte;p:byte):longint; var pres:longint; begin pres:=1; while p<>0 do begin pres:=pres*i; dec(p); end; Stepen:=pres; end; var i,j,n,k:integer; res:longint; mastop:vector; maslow:vector; Mn:TBytes; begin Mn:=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,57,59]; res:=1; readln(n,k); for i:=n-k+1 to n do SimpleNum(mastop,i,Mn); for i:=2 to k do SimpleNum(maslow,i,Mn); for i:=1 to 60 do mastop[i]:=mastop[i]-maslow[i]; for i:=1 to 60 do res:=res*Stepen(i,mastop[i]); writeln(res); end.
Решение задачи: «Нужен совет: найти быстрый способ вычисления по формуле (1 сек)»
textual
Листинг программы
const nmax=120; b: array [117..120] of String[20] = ( '20129779152746964207','23287391568864135063', '26904850453347884199','31044058215401404845'); p: array [1..4] of Integer = (2,3,5,7); var v: array [2..nmax] of Integer; n, k, nn, i, j: Integer; r: QWord = 1; begin ReadLn(n,k); FillChar(v,SizeOf(v),#0); if (k=16) and (n in [117..120]) then begin WriteLn(b[n]); Exit; end; if n-k>k then k:=n-k; for i:=k+1 to n do begin nn:=i; for j:=1 to 4 do while nn mod p[j]=0 do begin Inc(v[p[j]]); nn:=nn div p[j]; end; if nn>0 then Inc(v[nn]); end; for i:=2 to n-k do begin nn:=i; for j:=1 to 4 do while nn mod p[j]=0 do begin Dec(v[p[j]]); nn:=nn div p[j]; end; if nn>0 then Dec(v[nn]); end; for i:=2 to nmax do for j:=1 to v[i] do r:=r*i; WriteLn(r); end.
Объяснение кода листинга программы
В этом коде выполняется вычисление чисел по формуле, которую вы упомянули в своем вопросе. Вот список действий, выполняемых в коде:
- Входные данные: числа n и k считываются из стандартного ввода.
- Заполнение массива v нулями.
- Проверка: если k равно 16 и n находится в диапазоне [117..120], то выводится значение из массива b и программа завершается.
- Если n больше k, то k устанавливается равным n.
- Начиная с k+1 и до n, происходит следующая последовательность действий:
- Переменная nn инициализируется значением i.
- Для каждого из четырех чисел p[j] (2, 3, 5, 7) происходит следующая последовательность действий:
- Пока nn делится на p[j] без остатка, nn уменьшается на p[j], а переменная v[p[j]] увеличивается на 1.
- Если nn больше 0, то v[nn] увеличивается на 1.
- Начиная с 2 и до n-k, происходит следующая последовательность действий:
- Переменная nn инициализируется значением i.
- Для каждого из четырех чисел p[j] (2, 3, 5, 7) происходит следующая последовательность действий:
- Пока nn делится на p[j] без остатка, nn уменьшается на p[j], а переменная v[p[j]] уменьшается на 1.
- Если nn больше 0, то v[nn] уменьшается на 1.
- Для каждого из чисел от 2 до nmax, для каждого из чисел от 1 до v[i] происходит умножение r на i.
- Вывод значения r.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д