ncr в с (комбинации)
Я пытаюсь вычислить ncr (комбинации) в c, используя дп. Но это терпит неудачу с 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 (например, умножение и деление bignum), потому что это деликатный предмет алгоритмического характера (вы все равно можете получить степень доктора наук).
Я предлагаю использовать некоторую существующую библиотеку Bignum, такую как GMP.
Некоторые языки или реализации (в частности, SBCL для Common Lisp) предлагает родные bignum операции. Но стандарт C или C ++ этого не делают.
Другие решения
Сделайте деление до умножения.
a * b / c = (a / c) * b, где вторая лучше для переполнения, которое кажется вашей проблемой.