在c ++中使用牛顿二项式系数的问题

Question

我的牛顿二项式系数程序存在问题.首先它打印负数,但改变阶乘函数类型unsigned long long似乎已经解决了打印负数的问题.该程序适用于max n = 20,在它上面开始打印零,一和二.不知道如何解决这个问题,希望有人可以帮我一臂之力.

#include <iostream>
using namespace std;

unsigned long long factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n*factorial(n - 1);
}

void Binom(int n ,int k) {
    unsigned long long factorialResult;
    if (k > n) {
        return;
    }
    factorialResult = factorial(n) /(factorial(k) * factorial(n - k));
    cout << factorialResult << " ";
    if (n >= k) {
        Binom(n, k + 1);
    }
}

Answer 1

阶乘通常非常大,所以这里只有一个整数溢出.要解决此问题,您可以实现任何其他C(n, k)不使用阶乘的计算算法,例如:

unsigned long long C(unsigned n, unsigned k) {
    if (n == k || k == 0) {
        return 1; // There's exactly one way to select n or 0 objects out of n
    }
    return C(n - 1, k - 1) * n / k;
}

这里使用以下循环规则:C(n, k) = C(n - 1, k - 1) * n / k.从那以后很容易证明C(n, k) = n! / (k! (n-k)!) = (n/k) * (n-1)! / ((k-1)!(n-1-k+1)!).