我正在尝试使用 dp 在 c 中计算 ncr(组合)。但它在 n=70 时失败了。谁能帮忙?
unsigned long long ncr( int n , int r)
{
unsigned long long c[1001];
int i=1;
c[0]=1;
for(i=1; i<=r; i++)
c[i]= ((unsigned long long) (c[i-1]) * (unsigned long long)( n-i+1))%(unsigned long long) (1000000007)/ (unsigned long long)(i);
return c[r];
}
基本思想是 ncr = ((n-r+1)/r)* nc(r-1)
最佳答案
中间乘积 (unsigned long long) (c[i-1]) * (unsigned long long)( n-i+1)
是一个非常大的数,溢出了 64位字。
您可能想使用 bignums .我强烈建议不要开发自己的 bignum 函数(例如 bignums 的乘法和除法),因为它是一门微妙的算法学科(您仍然可以获得这方面的博士学位)。
我建议使用一些现有的 bignum 库,例如 GMP .
一些语言或实现(特别是 Common Lisp 的 SBCL)提供了 native bignum 操作。但标准 C 或 C++ 不会。
关于c++ - c 中的 ncr(组合),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14787838/