Tính xác suất sinh nhật cho số lớn

Question

Xác suất hai người có cùng ngày sinh trong một căn phòng đầy đủ là n mọi người là 1-p. Trong đó:

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

Rõ ràng các con số sẽ quá lớn để giải phương trình này, cách sáng tạo để giải quyết vấn đề này là gì?

Tôi đã giải quyết vấn đề này theo cách khác bằng mô phỏng, nhưng tôi đã tìm ra công thức có thể thanh lịch hơn.

Answer 1

Bạn có thể tận dụng lợi thế của 365/(365-n)! = 365 * 364 * ... * (365- (n-1))

Vì vậy, để tính toán thuật ngữ này (hãy để nó là A = 365!/(365-n)!) Bạn có thể chỉ đơn giản là các con số trên như này:

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

Để thực hiện thêm một bước: p = A/365^n = (364 * 363 * ... * (365- (n-1)))/365^(n-1) = 364/365 * 363/365 * ... (365- (n-1))/365.

nên p có thể được calcuated như thế này:

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

trong thời gian tuyến tính

Tôi nghĩ rằng điều này sẽ làm việc: P

Answer 2

Bạn không muốn tính giai thừa đầy đủ. Thay vào đó, hãy tính từng cụm từ và nhân với kết quả.

Xác suất bạn không chia sẻ một sinh nhật với:

• 1 người: 364/365
• 2 người: 364/365 * 363/365
• 3 người: 364/365 * 363/365 * 362/365
• ...

vì điều này, bạn calcuate p như sau.

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

Tôi sẽ viết một chức năng mà trông như thế này:

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

Answer 4

Một giải pháp khác (xấp xỉ):

Xác suất của hai người bất kỳ không có cùng ngày sinh là 364/365 . Trong phòng chứa n người, có C (n, 2) = n (n - 1)/2 cặp người. Vì vậy:

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

Và đối với giá trị lớn hơn n = 100, bạn có thể yên tâm sử dụng bảng tiếp theo:!

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) rất gần với n!. Không cần phải lặp lại hàng trăm lần có thể làm giảm độ chính xác như mỗi *, / mất một mặt của độ chính xác bit với mỗi lần lặp.

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

Output

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

Answer 6

Holly Macaroni! Quả là một chương trình!

Dù sao, đúng cách để tính toán những việc như vậy với trung gian lớn là để đăng nhập() chúng

p = exp(log(p)) 

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

Đối với thừa, sử dụng Gamma chức năng, G (n + 1) = n !, và có rất tiện dụng chức năng trong thư viện C mà tính log (G (x)): lgamma (x)

không có nhiều vòng, không có đôi dài, không có thư viện bignum, không tràn ...

Mã

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