1209. Faktoriallı funksiya

Verilmiş cüt natural n ədədi üçün aşağıdakı funksiyanın qiymətini hesablayın:

f(n) =

Giriş verilənləri. Cüt natural n ədədi (1 £ n £ 100000).

Çıxış verilənləri. Onluq nöqtədən sonra dörd rəqəm olmaqla f(n) funksiyasının qiyməti.

Giriş verilənlərinə nümunə

4

Çıxış verilənlərinə nümunə

0.5000

HƏLLİ

riyaziyyat

Alqoritmin analizi

f(n) = bərabərliyi loqarifmləyək:

ln f(n) = ln(n – 2)! – –

Bərabərliyin birinci hissəsini hesablayaq və onu e əsasına görə yazaq. f(n) funksiyasını alacağıq. Faktorialın loqarifmini loqarifmlərin cəmi kimi hesablayaq:

ln n! = ln 1 + ln 2 + ln 3 + … + ln n

Alqoritmin reallaşdırılması

Qlobal massivlər təyin edək.

#define MAX 100001

double lf[MAX], ans[MAX];

lf massivini dolduraq, burada lf[i] = lni!.

res = lf[1] = 0.0;

for(res = 0, i = 2; i < MAX; i++)

{

res += log((double)i);

lf[i] = res;

}

ans massivini dolduraq, burada ans[i] = f(i).

for(i = 2; i < MAX; i += 2)

{

res = lf[i/2-1];

res = lf[i-2] - (i - 2) * log(2.0) - res - res; // res = ln f(i)

ans[i] = exp(res);

}

scanf("%d",&n);

printf("%.4lf\n",ans[n]);

Java reallaşdırılması

import java.util.*;

import java.io.*;

public class Main

{

public static final int MAX = 100001;

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out,true);

int i, n = con.nextInt();

double lf[] = new double[MAX],

ans[] = new double [MAX];

double res = lf[1] = 0.0;

for(res = 0, i = 2; i < MAX; i++)

{

res += Math.log(i);

lf[i] = res;

}

for(i = 2; i < MAX; i += 2)

{

res = lf[i/2-1];

res = lf[i-2] - (i - 2) * Math.log(2.0) - res - res;

ans[i] = Math.exp(res);

}

out.printf(Locale.US,"%.4f\n",ans[n]);

}

}