0

dp を使用して c で ncr(combinations) を計算しようとしています。しかし、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) です

4

2 に答える 2

2

中間積(unsigned long long) (c[i-1]) * (unsigned long long)( n-i+1)は非常に大きな数であり、64 ビット ワードをオーバーフローしています。

bignumsを使用することもできます。独自の bignum 関数 (bignum の乗算と除算など) を開発しないことを強くお勧めします。これはアルゴリズムのデリケートな問題であるためです (それでも博士号を取得できる可能性があります)。

GMPのような既存の bignum ライブラリを使用することをお勧めします。

一部の言語または実装 (特にCommon Lisp のSBCL ) は、ネイティブの bignum 操作を提供します。しかし、標準の C または C++ はそうではありません。

于 2013-02-09T11:58:34.043 に答える
-1

掛け算の前に割り算をします。a*b/c = (a/c) *b ここで、問題と思われるオーバーフローに 2 番目の方が適しています。

于 2013-02-09T12:08:52.120 に答える