计算大数的生日概率

Question

在一个满是n个人的房间里,两个人生日相同的概率是1-p.哪里:

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

显然这些数字太大了,无法解决这个问题,这有什么创造性的方法呢？

我已经使用模拟以不同的方式解决了这个问题,但我认为公式可能更优雅.

Answer 1

冬青通心粉!什么节目!

无论如何,用大型中间体计算这些东西的正确方法是log()它们

p = exp(log(p))

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

对于阶乘,使用Gamma函数,G(n + 1)= n !,在C库中有非常方便的函数来计算log(G(x)):lgamma(x)

没有更多的循环,没有长的双打,没有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;
}

Answer 2

您可以利用 365!/(365-n)! = 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;

更进一步： p=A/365^n = (364*363*...*(365-(n-1)))/365^(n-1)= 364/365 * 363/365 * ... (365-(n-1))/365。

所以 p 可以这样计算：

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

在线性时间内

我认为这应该有效：P