Contexte

Le paradoxe de l'anniversaire est un problème populaire dans la théorie des probabilités qui défie (la plupart des gens) l'intuition mathématique. L'énoncé du problème est le suivant:

Étant donné N personnes, quelle est la probabilité qu'au moins deux d'entre elles aient le même anniversaire (sans tenir compte de l'année).

Le problème est généralement simplifié en ignorant complètement les jours bissextiles. Dans ce cas, la réponse pour N = 23 est P (23) ≈ 0,5072972 (comme exemple courant). L'article Wikipedia lié explique comment arriver à cette probabilité. Alternativement, cette vidéo Numberphile fait un très bon travail.

Cependant, pour ce défi, nous voulons le faire correctement et ne pas ignorer les années bissextiles. C'est un peu plus compliqué, car maintenant le 29 février doit être ajouté, mais cet anniversaire particulier est moins probable que tous les autres.

Nous utiliserons également les règles de l' année bissextile complète :

• Si une année est divisible par 400, c'est une année bissextile.
• Sinon, si une année est divisible par 100, ce n'est pas une année bissextile.
• Sinon, si une année est divisible par 4, c'est une année bissextile.
• Sinon, ce n'est pas une année bissextile.

Confus? Cela signifie que les années 1700, 1800, 1900, 2100, 2200, 2300 ne sont pas des années bissextiles, mais 1600, 2000, 2400 le sont (ainsi que toute autre année divisible par 4). Ce calendrier se répète tous les 400 ans et nous supposerons une distribution uniforme des anniversaires sur ces 400 ans.

Le résultat corrigé pour N = 23 est maintenant P (23) ≈ 0,5068761 .

Le défi

Étant donné un nombre entier 1 ≤ N < 100, déterminez la probabilité qu'au Nmoins deux personnes aient le même anniversaire en tenant compte des règles de l'année bissextile. Le résultat doit être un nombre à virgule flottante ou à virgule fixe, précis à au moins 6 décimales. Il est acceptable de tronquer les zéros de fin.

Vous pouvez écrire un programme ou une fonction, en prenant des entrées via STDIN (ou l'alternative la plus proche), l'argument de ligne de commande ou l'argument de la fonction et sortir le résultat via STDOUT (ou l'alternative la plus proche), la valeur de retour de la fonction ou le paramètre de la fonction (out).

Votre solution doit être capable de produire une sortie pour les 99 entrées en quelques secondes. C'est principalement pour exclure les méthodes Monte Carlo avec des tonnes d'échantillons, donc si vous utilisez un algorithme principalement rapide et exact dans un langage ésotérique excessivement lent, je suis prêt à laisser une marge de manœuvre sur cette règle.

Cas de test

Voici le tableau complet des résultats:

 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

(Bien sûr, P (99) n'est que de 1,0 en raison de l'arrondissement. La probabilité n'atteindra pas exactement 1,0 avant P (367) .)

Pyth, 31 34 octets

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

Démonstration , test de harnais

Cela fonctionne de manière similaire à l'ancienne version, sauf qu'au lieu de générer séparément la valeur (366 + n * (.2425 - 1)) et de la multiplier, elle commence par générer une liste qui s'étend de 366 à 365 - n + 2, modifie ensuite le 366 en place pour devenir (366 + n * (.2425 - 1)), puis prend le produit de la liste. De plus, les constantes 366 et -.7575 sont utilisées à la place de 365 et .2425.

Ancienne version:

Pyth, 34 octets

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

Il y a deux façons possibles pour qu'il n'y ait pas de paire de personnes avec le même anniversaire: tout le monde a des anniversaires différents, et personne n'a d'anniversaire le 29 février, et quelqu'un pour avoir un anniversaire le 29, et tout le monde pour avoir différent anniversaires les jours normaux.

La probabilité de la première occurrence est (365 * 364 * ... 365 - n + 1) / (365.2425 ^ n).

La probabilité de la deuxième occurrence est (365 * 364 * ... 365 - n + 2) * .2425 * n / (365.2425 ^ n)

Ceux-ci peuvent être écrits ensemble comme (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).

Il s'agit de la probabilité de l'absence de paires, donc la probabilité d'au moins une paire est un moins le nombre ci-dessus.

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

Python, 179 178 144 143 140 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)donne le résultat. Passez .2425à fractions.Fraction(97,400)pour obtenir un résultat exact.

Python 155 153 151 142 140 octets

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)

Appelez a(n)pour le résultat. Pour des résultats exacts, enveloppez-les ddans une fraction.

Testez ici

Utilise la même technique qu'ici , mais avec des constantes modifiées.

80386 code machine, 43 octets

Hexdump du code:

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

Je suis parti de la formule suivante (pour la probabilité complémentaire):

(voici d = 366 * 400 - 303le nombre de jours en 400 ans)

Voici le code c ++ qui l'implémente (il est déjà un peu optimisé):

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

Le code est organisé de sorte qu'il nécessite le nombre minimum de constantes - seulement deux ( 400 / det 303 / d). J'utilise le floattype pour les représenter car il occupe moins d'espace (4 octets par constante). De plus, je ne voulais pas multiplier const2par k - 1(car cela nécessiterait une conversion k - 1en float); le code soustrait à const2plusieurs reprises à la place.

Voici la liste des langages d'assemblage:

    ; // 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