Doğum günləri#1317

Doğum günləri (Həll təhlili)

Əvvəlcə $n$ nəfərdən ibarət bir qrupda bütün doğum günlərinin fərqli olma ehtimalını $p (n)$ \overline{p(n)} hesablayacağıq. Əgər $n$ 365-dən böyükdürsə, bu ehtimal Dirichlet prinsipinə görə sıfıra bərabərdir. Əgər $n$ 365-dən böyük deyilsə, bu qaydada düşünürük.

Birinci şəxsi seçirik və onun doğum gününü yadda saxlayırıq. Sonra ikinci şəxsi seçirik: onun doğum gününün birincinin doğum günü ilə üst-üstə düşməməsi ehtimalı $1 - 1/365$ 1 - 1 / 365-ə bərabərdir. Üçüncü şəxs üçün isə onun doğum gününün ilk ikisinin doğum günləri ilə üst-üstə düşməməsi ehtimalı $1 - 2/365$ 1 - 2 / 365-ə bərabərdir.

Eyni qaydada davam edərək, sonuncu şəxs üçün onun doğum gününün bütün əvvəlki doğum günləri ilə üst-üstə düşməməsi ehtimalı $1 - (n - 1) /365$ 1 - (n - 1) / 365-ə bərabərdir.

Bu ehtimalları bir-birinə vuraraq, qrupdakı bütün doğum günlərinin fərqli olma ehtimalını əldə edirik:

p (n) = 1 \cdot (1 - \frac{1}{365}) \cdot (1 - \frac{2}{365}) \cdot ... \cdot (1 - \frac{n - 1}{365})

\overline{p(n)} = 1 \cdot \left(1 - \frac{1}{365}\right) \cdot \left(1 - \frac{2}{365}\right) \cdot ... \cdot \left(1 - \frac{n - 1}{365}\right)

O zaman $n$ nəfərdən ən azı ikisi üçün doğum günlərinin üst-üstə düşmə ehtimalı, bütün doğum günlərinin fərqli olma ehtimalının birini çıxmaqla müəyyən edilir:

p (n) = 1 - p (n)

p(n) = 1 - \overline{p(n)}

Alqoritmin Reallaşdırılması

$p [i]$ massivində müvafiq ehtimalları $p (i)$ saxlayaq.

double p[401];

$p [1] = 1$ p[1] = 1 olsun. Digər $p [i]$ massiv dəyərlərini məsələnin analizi ilə verilmiş formul ilə hesablayırıq.

p[1] = 1.0;
for (i = 2; i < 401; i++)
  p[i] = p[i-1] * (1.0 - (i - 1.0) / 365);

Hər bir $n$ giriş dəyəri üçün müvafiq ehtimalı hesablayır və nəticəni çıxarırıq.

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