Eyni toplar#1316

Eyni toplar (Həll təhlili)

$X$ əks hadisəsinin ehtimalını hesablayaq — yəni sonuncu çıxarılan şarların müxtəlif rəngdə olması hadisəsini. Bunun üçün ilk $n - 2$ n - 2 çıxarılan şarın düz yarısı ağ, digər yarısı isə qara olmalıdır.

Bernulli sınaq sxemini nəzərdən keçirək, burada uğur ehtimalı (məsələn, ağ şarın çıxması) $p = 1/2$ p = 1/2-ə, uğursuzluq ehtimalı isə $q = 1 - p = 1/2$ q = 1 - p = 1/2-ə bərabərdir. Çıxarılan $n - 2$ n - 2 şarın arasında dəqiq $(n - 2) /2$ (n - 2) / 2 ağ şarın olması ehtimalı aşağıdakı düstur ilə hesablanır:

P (X) = C_{n - 2}^{n /2 - 1} p^{n /2 - 1} q^{n /2 - 1} = \frac{( n - 2 )!}{( ( \frac{n}{2} - 1 ) ! ) ^{2}} (\frac{1}{2})^{n - 2}

P(X) = C_{n-2}^{n/2-1} p^{n/2 - 1} q^{n/2 - 1} = {(n - 2)! \over \left(\left({n \over 2} - 1\right)!\right)^2} \left({1 \over 2}\right) ^ {n - 2}

Hər daxil edilən $n$ üçün $P (X)$ qiymətini hesablamaq və $1 - P (X)$ 1 - P(X)-i çap etmək qalır.

$P (X)$ $0$ -dan $1$ -ə qədər (daxil olmaqla) hüdudlarda olsa da, onun birbaşa hesablanması ədədi problemlərə səbəb ola bilər. Bundan qaçmaq üçün loqarifmi hesablayaq:

l n P (X) = l n (n - 2)! - 2 \cdot l n (\frac{n}{2} - 1)! - (n - 2) \cdot l n 2

ln P(X) = ln(n - 2)! - 2 \cdot ln\left({n \over 2} - 1 \right)! - (n - 2) \cdot ln~2

Bərabərliyin sağ tərəfini hesabladıqdan sonra $P (X)$ -i bərpa etmək üçün $e$ -ni alınan qiymətə qaldıraq. Faktorialın loqarifmini loqarifmlərin cəmi kimi hesablayaq:

l n n! = l n 1 + l n 2 + l n 3 + ... + l n n

ln~n! = ln~1 + ln~2 + ln~3 + ... + ln~n

Proqramın girişinə bir neçə test veriləcəyi üçün bütün cavabları əvvəlcədən hesablayıb massivdə saxlamaq lazımdır.

Misal

$n = 6$ n = 6 üçün sonuncu çıxarılan şarların müxtəlif rəngdə olması ehtimalı belədir:

C_{4}^{2} p^{2} q^{2} = 6 \cdot (\frac{1}{2})^{4} = \frac{6}{16} = \frac{3}{8}

C_4^2~p^2q^2 = 6 \cdot \left({1 \over 2} \right)^4 = {6 \over 16} = {3 \over 8}

Sonuncu çıxarılan şarların eyni rəngdə olması ehtimalı isə belədir:

1- \frac{3}{8} = \frac{5}{8} = 0, 625

1 – {3 \over 8} = {5 \over 8} = 0,625

Alqoritmin reallaşdırılması

Lazımi massivləri elan edək. $an s [i]$ xanasında $C_{i - 2}^{i /2 - 1} p^{i /2 - 1} q^{i /2 - 1}$ C_{i-2}^{i/2-1} p^{i/2 - 1} q^{i/2 - 1} qiymətini saxlayacağıq.

#define MAX 100001
double lf[MAX], ans[MAX];

$l f$ massivini dolduraq, burada $l f [i]$ $l ni!$ qiymətini saxlayır.

res = lf[1] = 0.0;
for (res = 0, i = 2; i < MAX; i++)
{
  res += log((double)i);
  lf[i] = res;
}

Hər $i$ qiyməti üçün $l n C_{i - 2}^{i /2 - 1} p^{i /2 - 1} q^{i /2 - 1}$ ln~C_{i-2}^{i/2-1} p^{i/2 - 1} q^{i/2 - 1} hesablayaq və nəticəni $an s [i]$ -də saxlayaq.

for (i = 2; i < MAX; i += 2)
{
  res = lf[i/2-1];
  res = lf[i-2] - (i - 2) * log(2.0) – res - res;
  ans[i] = exp(res);    
}

Hər daxil edilən $n$ qiyməti üçün cavabı hesablayıb çap edirik.

while (scanf("%d",&n) == 1)
  printf("%.8lf\n",1 - ans[n]);