NCR在C（组合） [英] ncr in c (combinations)

问题描述

我米尝试使用DP在C来计算NCR（组合）。但它是在n = 70失败。谁能帮助？

I m trying to calculate ncr(combinations) in c using dp. But it is failing with n=70. Can anyone help?

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）

basic idea is ncr = ((n-r+1)/r)* nc(r-1)

推荐答案

中间产物（无符号长长）（C I-1）*（无符号长长）（N-1 + 1）是一个非常大的数字，并溢出64位字。

The intermediate product (unsigned long long) (c[i-1]) * (unsigned long long)( n-i+1) is a very big number, and is overflowing the 64 bits word.

您可能需要使用大数。我强烈反对开发自己的BIGNUM功能（例如，乘法和大数司），因为它是一个微妙的算法主体（你仍然可以得到一个关于博士）。

You may want to use bignums. I strongly recommend against developing your own bignum functions (e.g. multiplication and division of bignums), because it is a delicate algorithmic subject (you could still get a PhD about that).

我建议使用一些现有的BIGNUM库如 GMP 。

I suggest using some existing bignum library like GMP.

一些语言或实现（尤其是 SBCL 获得Common Lisp的）提供了本地BIGNUM操作。但是，标准C或C ++没有。

Some languages or implementations (in particular SBCL for Common Lisp) offers native bignum operations. But standard C or C++ don't.

这篇关于NCR在C（组合）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！