Дні народження#1317

Дні народження (Розбір)

Спочатку розрахуємо ймовірність $p (n)$ \overline{p(n)} того, що в групі з $n$ осіб всі дні народження будуть різними. Якщо $n$ більше $365$ , то за принципом Діріхле ця ймовірність дорівнює нулю. Якщо ж $n$ не перевищує $365$ , міркуємо наступним чином.

Вибираємо першу людину і запам'ятовуємо її день народження. Потім вибираємо другу людину: ймовірність того, що її день народження не співпаде з днем народження першого, дорівнює $1 - 1/365$ 1 - 1 / 365. Для третьої людини ймовірність того, що її день народження не співпаде з днями народження перших двох, дорівнює $1 - 2/365$ 1 - 2 / 365.

Продовжуючи аналогічні міркування, для останньої людини ймовірність того, що її день народження не співпаде з днями народження всіх попередніх, дорівнює $1 - (n - 1) /365$ 1 - (n - 1) / 365.

Перемножуючи всі ці ймовірності, отримуємо ймовірність того, що всі дні народження в групі будуть різними:

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)

Тоді ймовірність того, що хоча б у двох осіб з $n$ співпадуть дні народження, дорівнює одиниці мінус ймовірність того, що всі дні народження різні:

p (n) = 1 - p (n)

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

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

У масиві $p [i]$ будемо зберігати значення відповідних ймовірностей $p (i)$ .

double p[401];

Нехай $p [1] = 1$ p[1] = 1. Інші значення масиву $p [i]$ обчислюємо за формулою, наведеною в аналізі задачі.

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

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

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