找到大数的组合

Question

什么是一种有效的方法来找到从N个礼物中选择礼物的数量,其中N可以非常大(N~10 ^ 18).那就是我们必须计算N(C)K或N选择K.K也可以是N的量级.

Answer 1

我想没有快速计算如此大数字的方法.您可以使用斯特林的公式来近似它

@Alexandre C:嗯,你怎么能这么说？斯特林的公式近似于"n!".所以你近似于`n!,k!和(n - k)!`并得到n的近似值!/(k!*(n - k)!)`.如果你想得到`C(n,k)`的行为的渐近意义那么,是的,你需要`k`和`n`之间的关系,但要近似,不. (3认同)