求助：基于阶乘计算贝尔数的C程序问题排查

嘿，咱们一步步拆解你的问题，帮你把贝尔数的程序捋顺～

你提到的{n k}其实是第二类斯特林数的符号，它表示把n个不同元素分成k个非空子集的方式数，完全不是你当前用的组合数公式C(n,k) = n!/(k!(n-k)!)！这是你计算逻辑的核心问题——贝尔数Bₙ是所有k从0到n的第二类斯特林数S(n,k)的总和，不是组合数的和哦。

把阶乘函数声明为float会带来两个大问题：

• 阶乘的结果是整数，但float的精度只有约6-7位有效数字，当n≥13时，13! = 6227020800，已经超过了float能精确表示的整数范围（最多到2^24≈16777216），之后的阶乘结果会丢失精度，出现完全错误的计算值。
• 建议改用无符号64位整数类型unsigned long long，它能精确表示到18446744073709551615，足够计算到n=20左右的阶乘（20!≈2.43e18，刚好在范围内）；如果需要计算更大的n，可以考虑用数组模拟大数乘法。

给你两种常见的靠谱实现方式，按需选择：

方式1：基于第二类斯特林数的递推 #

第二类斯特林数的递推公式是：

S(n, k) = S(n-1, k-1) + k * S(n-1, k)
边界条件：S(0,0)=1；S(n,0)=0（n>0）；S(0,k)=0（k>0）

贝尔数就是所有k从0到n的斯特林数之和，代码示例：

#include <stdio.h>

unsigned long long stirling(int n, int k) {
    unsigned long long s[n+1][k+1];
    s[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        s[i][0] = 0;
        for (int j = 1; j <= k && j <= i; j++) {
            s[i][j] = s[i-1][j-1] + j * s[i-1][j];
        }
    }
    return s[n][k];
}

unsigned long long bell(int n) {
    unsigned long long sum = 0;
    for (int k = 0; k <= n; k++) {
        sum += stirling(n, k);
    }
    return sum;
}

int main() {
    int n;
    printf("Enter n: ");
    scanf("%d", &n);
    printf("Bell number B_%d is %llu\n", n, bell(n));
    return 0;
}

方式2：用贝尔数自身的递推公式 #

贝尔数也有直接的递推公式，不需要计算斯特林数，适合小范围的n：

Bₙ₊₁ = Σ（k=0到n）C(n,k) * B_k
边界条件：B₀=1

代码示例：

#include <stdio.h>
#include <stdlib.h>

unsigned long long factorial(int n) {
    unsigned long long res = 1;
    for (int i = 1; i <= n; i++) {
        res *= i;
    }
    return res;
}

unsigned long long combination(int n, int k) {
    if (k > n) return 0;
    return factorial(n) / (factorial(k) * factorial(n - k));
}

unsigned long long bell(int n) {
    if (n == 0) return 1;
    unsigned long long* b = malloc((n+1) * sizeof(unsigned long long));
    b[0] = 1;
    for (int i = 1; i <= n; i++) {
        b[i] = 0;
        for (int k = 0; k < i; k++) {
            b[i] += combination(i-1, k) * b[k];
        }
    }
    unsigned long long res = b[n];
    free(b);
    return res;
}

int main() {
    int n;
    printf("Enter n: ");
    scanf("%d", &n);
    printf("Bell number B_%d is %llu\n", n, bell(n));
    return 0;
}

可以先手动计算几个小的贝尔数来验证程序正确性：

• B₀=1，B₁=1，B₂=2，B₃=5，B₄=15，B₅=52
  跑这些值，如果输出一致，说明逻辑没问题啦。

内容的提问来源于stack exchange，提问作者von