Однакові кулі#1316

Однакові кулі (Розбір)

Обчислимо ймовірність протилежної події $X$ — того, що останніми будуть вийняті кульки різного кольору. Для цього серед перших $n - 2$ n - 2 вийнятих кульок рівно половина має бути білими, а половина — чорними.

Розглянемо схему випробувань Бернуллі, де ймовірність успіху (наприклад, появи білої кульки) дорівнює $p = 1/2$ p = 1/2, а неуспіху $q = 1 - p = 1/2$ q = 1 - p = 1/2. Ймовірність того, що серед $n - 2$ n - 2 вийнятих кульок виявиться рівно $(n - 2) /2$ (n - 2) / 2 білих, обчислюється за формулою:

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}

Залишається для кожного вхідного $n$ обчислити значення $P (X)$ і вивести $1 - P (X)$ 1 - P(X).

Хоча $P (X)$ знаходиться в межах від $0$ до $1$ включно, його безпосереднє обчислення може призвести до числових проблем. Щоб уникнути цього, обчислимо логарифм:

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

Після обчислення правої частини рівності піднесемо $е$ до отриманого значення, щоб відновити $P (X)$ . Логарифм факторіала обчислимо як суму логарифмів:

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

Оскільки на вхід програми подається декілька тестів, усі відповіді слід попередньо обчислити і зберегти в масиві.

Приклад

Для $n = 6$ n = 6 ймовірність того, що останніми будуть вийняті кульки різного кольору, дорівнює

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}

Ймовірність того, що останніми будуть вийняті кульки одного кольору, дорівнює

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

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

Реалізація алгоритму

Оголосимо необхідні масиви. У комірці $an s [i]$ будемо зберігати значення $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}.

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

Заповнимо масив $l f$ , де $l f [i]$ зберігає значення $l ni!$ .

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

Для кожного значення $i$ обчислимо $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} і збережемо результат в $an s [i]$ .

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

Для кожного вхідного значення $n$ обчислюємо і виводимо відповідь.

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