Расчет вероятности летного исхода для больших чисел

Question

Вероятность того, что у двух человек одинаковый день рождения в комнате, полной n человек: 1-p. Где:

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

Очевидно, что цифры будут слишком большими, чтобы решить это уравнение, что творческий путь идти об этом?

Я уже решил это по-другому, используя моделирование, но я решил, что формула может быть более элегантной.

Answer 1

Вы можете воспользоваться 365/(365-п)! = 365 * 364 * ... * (365- (n-1))

Таким образом, чтобы рассчитать этот термин (пусть это будет A = 365!/(365-n)!), Вы можете просто использовать приведенные выше цифры, например это:

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

Для того, чтобы сделать еще один шаг дальше: р = А/365^п = (364 * 363 * ... * (365- (п-1)))/365^(п-1) = 364/365 * 363/365 * ... (365- (n-1))/365.

так р может быть, как это Расчетный:

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

в линейное время

Я думаю, что это должно работать: P

Answer 2

Вы не хотите рассчитать полный факториал. Вместо этого вычислите каждый член и умножьте его на результат.

Вероятность вы не разделяете день рождения с:

• 1 человек: 364/365
• 2 человека: 364/365 * 363/365
• 3 человека: 364/365 * 363/365 * 362/365
• ...

Учитывая это, вы calcuate p следующим образом.

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

Я хотел бы написать функцию, которая выглядит следующим образом:

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

Answer 4

Другим решением (приближение):

Вероятность любых двух людей, не имеющих один и тот же день рождения 364/365 , В комнате, содержащей n людей, есть C (n, 2) = n (n - 1)/2 пары людей. Итак:

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

И для значений больших, чем n = 100, вы можете смело использовать следующую таблицу:

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) очень близко к n!. Не нужно ставить сотни раз, что может уменьшить точность, так как каждый *, / теряет фракцию с точностью до каждой итерации.

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

Выход

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

Answer 6

Холли Макароны! Какое шоу!

Во всяком случае, правильный способ вычислить такие вещи с большими интермедиатами для входа() их

p = exp(log(p)) 

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

Для факториала используйте функцию Gamma, G (п + 1) = п !, и есть очень удобно функция в библиотеке C, которая вычисляет журнал (G (х)): lgamma (х)

Нет больше петель, нет длинной парных, ни bignum библиотеки, не переполняется ...

кода

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