c++ - C++中牛顿二项式系数的问题

Question

我的牛顿二项式系数程序有问题。起初它打印负数，但将阶乘函数类型更改为 unsigned long long 似乎解决了打印负数的问题。该程序适用于最大 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)!)。