Фон

Парадокс дня рождения является популярной проблемой в теории вероятностей, бросает вызов ( у большинства людей) математическая интуиция. Постановка проблемы:

Учитывая N человек, какова вероятность того, что по крайней мере два из них имеют одинаковый день рождения (без учета года).

Проблема обычно упрощается за счет полного игнорирования високосных дней. В этом случае ответом для N = 23 является P (23) ≈ 0.5072972 (в качестве общего примера). В связанной статье Википедии объясняется, как прийти к такой вероятности. Кроме того, это видео Numberphile делает действительно хорошую работу.

Тем не менее, для этой задачи мы хотим сделать это правильно и не игнорировать високосные годы. Это немного сложнее, поскольку теперь нужно добавить 29 февраля, но этот конкретный день рождения менее вероятен, чем все остальные.

Мы также будем использовать правила полного високосного года :

Если год делится на 400, это високосный год.
Иначе, если год делится на 100, это не високосный год.
Иначе, если год делится на 4, это високосный год.
Иначе, это не високосный год.

Смущенный? Это означает, что 1700, 1800, 1900, 2100, 2200, 2300 лет не являются високосными, а 1600, 2000, 2400 (как и любой другой год, делимый на 4). Этот календарь повторяется каждые 400 лет, и мы будем предполагать равномерное распределение дней рождения в течение этих 400 лет.

Исправленный результат для N = 23 теперь равен P (23) ≈ 0.5068761 .

Соревнование

Учитывая целое число 1 ≤ N < 100, определите вероятность того, что среди Nлюдей как минимум двое имеют одинаковый день рождения при рассмотрении правил високосного года. Результатом должно быть число с плавающей точкой или число с фиксированной запятой с точностью не менее 6 десятичных знаков. Допустимо усекать конечные нули.

Вы можете написать программу или функцию, принимая ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции и выводить результат через STDOUT (или ближайшую альтернативу), возвращаемое значение функции или параметр функции (out).

Ваше решение должно быть в состоянии произвести вывод для всех 99 входов за считанные секунды. Это в основном исключает методы Монте-Карло с тоннами выборок, поэтому, если вы используете принципиально быстрый и точный алгоритм на чрезмерно медленном эзотерическом языке, я хочу дать свободу в этом правиле.

Тестовые случаи

Вот полная таблица результатов:

 1 => 0.000000
 2 => 0.002737
 3 => 0.008195
 4 => 0.016337
 5 => 0.027104
 6 => 0.040416
 7 => 0.056171
 8 => 0.074251
 9 => 0.094518
10 => 0.116818
11 => 0.140987
12 => 0.166844
13 => 0.194203
14 => 0.222869
15 => 0.252642
16 => 0.283319
17 => 0.314698
18 => 0.346578
19 => 0.378764
20 => 0.411063
21 => 0.443296
22 => 0.475287
23 => 0.506876
24 => 0.537913
25 => 0.568260
26 => 0.597796
27 => 0.626412
28 => 0.654014
29 => 0.680524
30 => 0.705877
31 => 0.730022
32 => 0.752924
33 => 0.774560
34 => 0.794917
35 => 0.813998
36 => 0.831812
37 => 0.848381
38 => 0.863732
39 => 0.877901
40 => 0.890932
41 => 0.902870
42 => 0.913767
43 => 0.923678
44 => 0.932658
45 => 0.940766
46 => 0.948060
47 => 0.954598
48 => 0.960437
49 => 0.965634
50 => 0.970242
51 => 0.974313
52 => 0.977898
53 => 0.981043
54 => 0.983792
55 => 0.986187
56 => 0.988266
57 => 0.990064
58 => 0.991614
59 => 0.992945
60 => 0.994084
61 => 0.995055
62 => 0.995880
63 => 0.996579
64 => 0.997169
65 => 0.997665
66 => 0.998080
67 => 0.998427
68 => 0.998715
69 => 0.998954
70 => 0.999152
71 => 0.999314
72 => 0.999447
73 => 0.999556
74 => 0.999645
75 => 0.999717
76 => 0.999775
77 => 0.999822
78 => 0.999859
79 => 0.999889
80 => 0.999913
81 => 0.999932
82 => 0.999947
83 => 0.999959
84 => 0.999968
85 => 0.999976
86 => 0.999981
87 => 0.999986
88 => 0.999989
89 => 0.999992
90 => 0.999994
91 => 0.999995
92 => 0.999996
93 => 0.999997
94 => 0.999998
95 => 0.999999
96 => 0.999999
97 => 0.999999
98 => 0.999999
99 => 1.000000

(Конечно, P (99) только 1,0 из-за округления. Вероятность не достигнет точно 1,0, пока P (367) .)

code-golf probability-theory Мартин Эндер
источник

7

1. Если вы собираетесь быть педантичным, вам следует учитывать, что дни рождения не распределены равномерно в течение года. 2. Точная актуальность правил високосного года зависит от того, какие предположения сделаны относительно продолжительности жизни человека. Является ли идея амортизации в течение всего 400-летнего цикла?

Питер Тейлор

1

@PeterTaylor Да, предположим, равномерное распределение в течение полного 400-летнего цикла. Я никогда не говорил, что группа из N человек была жива одновременно. ;)

Мартин Эндер

6

Pyth, 31 34 байта

Jt.2425K366-1c.xX0rK-KQ*JQ^+KJQ

Демонстрация , Испытательный жгут

Это работает аналогично старой версии, за исключением того, что вместо отдельной генерации значения (366 + n * (.2425 - 1)) и его умножения оно начинается с генерации списка, который расширяется с 366 до 365 - n + 2, затем изменяет 366 на месте, чтобы стать (366 + n * (.2425 - 1)), а затем берет произведение из списка. Кроме того, константы 366 и -7575 используются вместо 365 и .2425.

Старая версия:

Pyth, 34 байта

J.2425K365-1c*+hK*QtJ.xrK-hKQ^+KJQ

Есть два возможных способа, чтобы не было пары людей с одинаковым днем рождения: у всех разные дни рождения, и у кого-то нет дня рождения 29 февраля, и у кого-то день рождения 29-го, и у всех остальных день рождения разные. дни рождения в обычные дни.

Вероятность первого появления равна (365 * 364 * ... 365 - n + 1) / (365,2425 ^ n).

Вероятность второго появления (365 * 364 * ... 365 - n + 2) * .2425 * n / (365.2425 ^ n)

Они могут быть записаны вместе как (365 * 364 * ... 365 - n + 2) * (365 - n + 1 + .2425 * n) / (365.2425 ^ n) = (365 * 364 * ... 365 - n + 2) * (365 + 1 + (.2425 - 1) * n) / (365,2425 ^ n).

Это вероятность отсутствия пар, поэтому вероятность, по крайней мере, одной пары, равна одному минус вышеуказанное число.

J = .2425
K = 365
.xrK-hKQ = (365 * 364 * ... 365 - n + 2)
+hK*QtJ = (365 + 1 + n * (.2425 - 1))
^+KJQ = (365.2425 ^ n)

isaacg
источник

5

Питон, 179 178 144 143 140 136 135 133

f=.2425
g=365+f
a=lambda n:(n and(365-n)*a(n-1)or 365)/g
b=lambda n:(n<2and f or(367-n)*b(n-1)+a(n-2)*f)/g
p=lambda n:1-a(n-1)-b(n)

p(n)дает результат. Перейдите .2425на, fractions.Fraction(97,400)чтобы получить точный результат.

orlp
источник

Вам не нужно пространство между 2и and.

Исаак

Вы можете не ставить в 1/течение gи разделить на ней вместо этого?

xnor

@xnor Да, со временем эти вещи теряются :) То, что раньше было оптимизацией, позже становится неоптимальным.

orlp

Вы можете ввести e=365и заменить 365 на е и 367 на е + 2

Виллем

@ Виллем Это не короче.

orlp

2

Python 155 153 151 142 140 байт

d=146097
b=d/400
c=97/d
e=lambda n:n<2and 1-97/d or e(n-1)*(366-n)/b
f=lambda n:n<2and c or f(n-1)*(367-n)/b+e(n-1)*c
a=lambda n:1-e(n)-f(n)

Позвоните a(n)для результата. Для точных результатов заверните dв дробь.

Тест здесь

Использует ту же технику, что и здесь , но с измененными константами.

Номер один
источник

Вам не нужно пространство между 2и and.

Исаак

Я думал, что это был 98 (хотя, возможно, я сошел с ума из-за ошибки вычисления ...)

Тим

1

80386 машинный код, 43 байта

Hexdump кода:

68 75 6e 33 3b 68 5a eb 07 3b 8b c4 49 d9 e8 d9
e8 d8 00 d9 e8 d9 40 04 de ea d8 c9 d9 00 de eb
e2 f3 d8 ca d9 e8 d8 e1 58 58 c3

Я начал со следующей формулы (для дополнительной вероятности):

$\ Прод \ limits_ {I = 0} ^ {к-2} (1- \ гидроразрыва {97 + 400 * я} {} d) * (1- \ гидроразрыва {303 * (к-1)} {д})$

(Вот d = 366 * 400 - 303 количество дней в 400 лет)

Вот код C ++, который его реализует (он уже немного оптимизирован):

double it_opt(int k)
{
    double d = 366 * 400 - 303; // number of days in 400 years
    double result = 1; // probability of no coincidences
    const float const1 = float(400 / d);
    const float const2 = float(303 / d);
    double v1 = 1 + const2;
    double v2 = 1;

    for (int i = 0; i < k - 1; ++i)
    {
        v1 -= const1;
        result *= v1;
        v2 -= const2;
    }
    result *= v2;
    return 1 - result;
}

Код устроен так, что для него требуется минимальное количество констант - только две ( 400 / dи 303 / d). Я использую floatтип для их представления, потому что он занимает меньше места (4 байта на константу). Кроме того, я не хотел умножать const2на k - 1(потому что это потребовало бы преобразованияk - 1 в float); код вычитаетconst2вместо этого несколько раз.

Вот листинг на ассемблере:

    ; // fastcall convention - parameter k is in ecx
    ; // result must be returned in st
    push dword ptr 0x3b336e75; // const1 = [esp + 4]
    push dword ptr 0x3b07eb5a; // const2 = [esp]
    mov eax, esp;              // use [eax] instead of [esp] - 1 byte less
    dec ecx;                   // calculate k - 1
    fld1;                      // initiaze result = 1
    fld1;                      // initialize v1
    fadd [eax];
    fld1;                      // initialilze v2
myloop:
    fld dword ptr [eax + 4];
    fsubp st(2), st;            // update v1
    fmul st, st(1);             // update result
    fld dword ptr [eax];
    fsubp st(3), st;            // update v2
    loop myloop;                // loop
    fmul st, st(2);             // update result by v2
    fld1;
    fsub st, st(1);             // complement result
    pop eax;                    // restore stack
    pop eax;                    // restore stack
    ret;                        // return

anatolyg
источник

(Несколько) Педантический Парадокс Дня Рождения

Фон