1317. Дни рождения

Рожь. 1878. Пейзаж стал классическим и программным произведением, как для самого художника, так и для художественной критики его времени. На одном из эскизов к картине И.И. Шишкин сделал запись, которую можно считать его творческим кредо: «Раздолье, простор, угодье, рожь, Божья благодать, русское богатство».

Лирическое отношение к отечественной природе, воспетое И.И. Шишкиным, было ярко выражено в стихах Н.А. Некрасова:

Все рожь кругом, как степь живая,

Ни замков, ни морей, ни гор.

Спасибо, сторона родная,

За твой врачующий простор.

Известно, что в группе из 23 и более человек вероятность того, что хотя бы у двух из них совпадёт день рождения (день и месяц), превышает . Этот факт может показаться парадоксальным, поскольку вероятность рождения одного человека в определённый день года крайне мала, а вероятность совпадения дня рождения у двух людей ещё меньше. Однако результат подтверждается теорией вероятностей. Следовательно, этот факт не является парадоксом в строгом научном смысле – здесь нет логического противоречия. Парадокс заключается лишь в расхождении между нашей интуицией и результатом математического расчёта.

По заданному количеству человек вычислите вероятность того, что хотя бы у двух из них совпадёт день рождения. Считайте, что в году 365 дней.

Вход. Каждая строка является отдельным тестом и содержит количество людей n (1 < n < 400).

Выход. Для каждого значения n выведите в отдельной строке вероятность (в процентах) того, что хотя бы у двух из n человек совпадёт день рождения (день и месяц). Вероятность выведите с точностью до 8 знаков после запятой.

Пример входа	Пример выхода
2 10 23 366	0.27397260% 11.69481777% 50.72972343% 100.00000000%

РЕШЕНИЕ

теория вероятности

Анализ алгоритма

Сначала рассчитаем вероятность того, что в группе из n человек все дни рождения будут различными. Если n больше 365, то в силу принципа Дирихле эта вероятность равна нулю. Если же n не превышает 365, рассуждаем следующим образом.

Выбираем первого человека и запоминаем его день рождения. Затем выбираем второго человека: вероятность того, что его день рождения не совпадёт с днём рождения первого, равна 1 – 1 / 365. Для третьего человека вероятность того, что его день рождения не совпадёт с днями рождения первых двух, равна 1 – 2 / 365.

Продолжая аналогичное рассуждение, для последнего человека вероятность того, что его день рождения не совпадёт с днями рождения всех предыдущих, равна 1 – (n – 1) / 365.

Перемножая все эти вероятности, получаем вероятность того, что все дни рождения в группе будут различными:

Тогда вероятность того, что хотя бы у двух человек из n совпадут дни рождения, равна единице минус вероятность того, что все дни рождения различны:

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

В массиве p[i] будем хранить значения соответствующих вероятностей p(i).

double p[401];

Пусть 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);