Palline identiche#1316

Palline identiche (Editoriale)

Calcoliamo la probabilità dell'evento opposto $X$ — ovvero che le ultime palline estratte siano di colore diverso. Per questo, tra le prime $n - 2$ n - 2 palline estratte, esattamente la metà deve essere bianca e la metà nera.

Consideriamo uno schema di prove di Bernoulli, dove la probabilità di successo (ad esempio, l'apparizione di una pallina bianca) è uguale a $p = 1/2$ p = 1/2, e di insuccesso $q = 1 - p = 1/2$ q = 1 - p = 1/2. La probabilità che tra le $n - 2$ n - 2 palline estratte risultino esattamente $(n - 2) /2$ (n - 2) / 2 bianche, si calcola con la formula:

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}

Resta, per ogni $n$ in ingresso, calcolare il valore $P (X)$ e stampare $1 - P (X)$ 1 - P(X).

Sebbene $P (X)$ sia compreso tra $0$ e $1$ inclusi, il suo calcolo diretto può portare a problemi numerici. Per evitarlo, calcoliamo il logaritmo:

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

Dopo aver calcolato il lato destro dell'uguaglianza, eleviamo $е$ al valore ottenuto per ricostruire $P (X)$ . Il logaritmo del fattoriale lo calcoleremo come somma di logaritmi:

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

Poiché in ingresso al programma vengono forniti più test, tutte le risposte devono essere precalcolate e memorizzate in un array.

Esempio

Per $n = 6$ n = 6 la probabilità che le ultime palline estratte siano di colore diverso è uguale a

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}

La probabilità che le ultime palline estratte siano dello stesso colore è uguale a

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

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

Implementazione dell'algoritmo

Dichiariamo gli array necessari. Nella cella $an s [i]$ memorizzeremo il valore $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];

Riempiamo l'array $l f$ , dove $l f [i]$ memorizza il valore $l ni!$ .

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

Per ogni valore $i$ calcoliamo $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} e memorizziamo il risultato in $an s [i]$ .

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);    
}

Per ogni valore $n$ in ingresso calcoliamo e stampiamo la risposta.

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