c-我怎样才能得到一个不超过的组合数

Question

我想写一个函数来获得一个组合n_k。以下是我所做的：

int com(int n, int k)
{
    int result = 1;
    for( int i=n; i>(n-k); i--)
        result *= i;
    for( int i=k; i>1; i--)
        result /= i;
    return result;
}

这对小数字很有效，但当它变成大数字时，结果刚好超过int的最大值。有更好的方法吗？

Answer 1

通过使用unsigned long long和一个更聪明的算法：，您可以获得稍微的上界

unsigned long long n = /* n */, k = /* k */;
unsigned long long p = 1; /* accumulates the product */
unsigned long long m = k < n - k ? k : n - k; /* min(k, n - k) */
k = m;
unsigned long long i = n - k + 1;
unsigned long long j = 1;
while (m-- > 0) {
    p = p * i++ / j++;
}

如果这还不够，那么您将不得不使用bigint库。