Berechnung Birthday-Wahrscheinlichkeit für große Zahlen

Question

Die Wahrscheinlichkeit, dass zwei Personen den gleichen Geburtstag in einem Raum voller n Menschen haben, ist 1-p. Wo:

p = 365!/365^n(365 - n)! 

Offensichtlich sind die Zahlen zu groß sein, um diese Gleichung zu lösen, was ist ein kreativer Weg, um dies zu realisieren?

Ich löste das bereits auf andere Weise mit Hilfe von Simulation, aber ich dachte, die Formel könnte eleganter sein.

Answer 1

Sie können die Vorteile von 365 nehmen/(365-n)! = 365 * 364 * ... * (365- (n-1))

Also um diesen Begriff zu berechnen (sei es A = 365!/(365-n)!) Können Sie einfach die obigen Zahlen mögen Dieses:

unsinged double A=1; // to make sure there is no overflow 
for(int i=0;i<n;i++) A*=365-i; 

Um es noch einen Schritt weiter: p = A/365^n = (364 * 363 * ... * (365- (n-1)))/365^(n-1) = 364/365 * 363/365 * ... (365- (n-1))/365.

Ich denke, das sollte funktionieren

unsigned double p=1; 
for(int i=0;i<n;i++) p*= (365-i)/365.0; 

in linearer Zeit:: P

Answer 2

Sie möchten nicht die vollständige Fakultät berechnen. Berechnen Sie stattdessen jeden Ausdruck und multiplizieren Sie ihn mit dem Ergebnis.

• 1 Person: 364/365
• 2 Personen: 364/365 * 363/365
• 3 Personen:

  Die Wahrscheinlichkeit, Sie mit einem Geburtstag nicht teilen 364/365 * 363/365 * 362/365

• ...

dies angesichts calcuate Sie p wie folgt.

int n = 30; 
int i; 
double p = 1; 
for (i = 1; i < n; i++) { 
    p *= (365 - i)/365.0; 
    printf("i=%d, p=%f\n", i, 1-p); 
} 

Answer 3

Ich würde eine Funktion schreiben, die wie folgt aussieht:

double p(int n){ 
    double res = 1; 
    while (n>0){ 
     res *= (365 - (n--))/365.0; 
    } 
    return res; 
} 

Answer 4

Eine andere Lösung (eine Näherung):

Die Wahrscheinlichkeit, zwei Menschen nicht mit dem gleichen Geburtstag 364/365 . In einem Raum mit n Personen gibt es C (n, 2) = n (n - 1)/2 Paare. Also:

p(n) = 364/365^(n * (n-1)/2) 

Und für Werte größer als n = 100, Sie sicher in der nächsten Tabelle verwenden können:

n p(n) 
1 0.0% 
5 2.7% 
10 11.7% 
20 41.1% 
23 50.7% 
30 70.6% 
40 89.1% 
50 97.0% 
60 99.4% 
70 99.9% 
100 99.99997% 
200 99.9999999999999999999999999998% 
300 (100 − (6×10−80))% 
350 (100 − (3×10−129))% 
365 (100 − (1.45×10−155))% 
366 100% 
367 100% 

Answer 5

tgamma(n+1) ist ganz in der Nähe n!

so kann p wie diese calcuated werden. Keine Notwendigkeit, Hunderte von Zeiten zu wiederholen, was die Genauigkeit verringern kann, da jeder *, / eine Fraktion von einer Bitgenauigkeit mit jeder Iteration verliert.

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <float.h> 

long double fact(int n) { 
    return roundl(tgammal(n + 1)); 
} 

double bd_prob(int n) { 
    return fact(365)/(powl(365,n)*fact(365-n)); 
} 

int main(void){ 
    // No problem with 365! 
    printf("fact(365) %Le\n", fact(365)); 
    // No problem with 365 to the 365 power 
    printf("365^365 %Le\n", powl(365, 365)); 

    printf("prob(22) %f\n", bd_prob(22)); 
    exit(EXIT_SUCCESS); 
} 

Ausgabe

fact(365) 2.510413e+778 
365^365 1.725423e+935 
prob(22) 0.524305 

Answer 6

Holly Makkaroni! Was für ein Auftritt!

Wie dem auch sei, richtige Weg, solche Dinge mit großen Zwischenprodukte zu berechnen ist zu log(), um sie

p = exp(log(p)) 

log(p) = log(365!) - n*log(365) - log((365 - n)!) 

Für faktorielles verwenden Gamma-Funktion, G (n + 1) = n !, und es ist sehr praktisch, Funktion in C-Bibliothek, die log (G (x)) berechnet: lgamma (x)

nicht mehr Schleifen, keine langen Doppelzimmer, keine bignum Bibliotheken, keine überläuft ...

-Code

#include <math.h> 
#include <stdio.h> 

double b(int n) { 
    double l = lgamma(365.0 + 1.0) - 
       (double)n * log(365.0) - 
       lgamma(365.0 - (double)n + 1.0); 

    return exp(l); 
} 

int main() { 
    double p = b(20); 
    printf("%e %e\n", p, 1.0 - p); 

    return 0; 
}