C语言计算组合数（N Choose K）时出现异常错误求助

问题描述 #

编写帕斯卡三角打印程序时，第14行（对应n=13）之前输出正常，之后结果错误。排查发现自定义组合数函数choose()在n≥12时计算异常，例如choose(13, 1)返回4而非正确值13。

相关代码如下：

long factorial(int value)
{
    int i;
    long running = 1;
    for (i = 1; i <= value; i++)
    {
        running *= i;
    }
    return running;
}

long choose(int n, int k)
{
    if (n < k)
        return 0; 

    return factorial(n) / (factorial(k) * factorial(n - k));
}

异常输出片段：

1   1   -4   -1   2   4   7   9   9   7   4   2   -1   -4   1   1
1   0   1   5   14   29   44   50   44   29   14   5   1   0   1
1   4   24   88   221   399   532   532   399   221   88   24   4   1 <--------- 问题起始行
1   12   66   220   495   792   924   792   495   220   66   12   1
1   11   55   165   330   462   462   330   165   55   11   1
...

已尝试将变量类型从int改为long，问题仍未解决。

问题原因 #

核心问题是阶乘计算时的整数溢出：

• 32位系统中，long类型的最大值为2147483647（约2.1e9），而13! = 6227020800，已经超过这个最大值，导致factorial(13)计算时溢出，得到错误的负数或截断值。
• 溢出后的错误阶乘值代入组合数公式，自然会得到完全错误的结果，比如factorial(13)溢出后的值除以factorial(1)*factorial(12)，结果就不是13了。

解决方法 #

方案1：使用更大的整数类型 #

将阶乘和组合数的返回类型改为unsigned long long（64位无符号整数，最大值约1.8e19），足够支撑到20!的计算：

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

unsigned long long choose(int n, int k)
{
    if (n < k)
        return 0; 

    return factorial(n) / (factorial(k) * factorial(n - k));
}

注意打印时要使用%llu格式符。

方案2：递推计算组合数，避免直接计算大阶乘 #

利用组合数的递推公式C(n,k) = C(n,k-1) * (n - k + 1) / k，从C(n,0)=1开始递推，这样不会产生超大的中间值：

long choose(int n, int k)
{
    if (n < k || k < 0)
        return 0;
    // 利用对称性 C(n,k)=C(n,n-k)，减少计算次数
    if (k > n - k)
        k = n - k;
    long result = 1;
    for (int i = 1; i <= k; i++)
    {
        result = result * (n - k + i) / i;
    }
    return result;
}

这种方法不仅避免了溢出（只要最终结果在long范围内），还提高了计算效率。

方案3：直接利用帕斯卡三角的递推性质 #

帕斯卡三角的核心是triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]，完全不需要单独计算组合数，从第一行开始逐行递推即可，这是最适合打印帕斯卡三角的方法：

#include <stdio.h>

int main()
{
    int rows = 15; // 要打印的行数
    long triangle[15][15];

    // 初始化第一行
    triangle[0][0] = 1;
    // 递推生成每一行
    for (int i = 1; i < rows; i++)
    {
        triangle[i][0] = 1;
        triangle[i][i] = 1;
        for (int j = 1; j < i; j++)
        {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
    // 打印结果
    for (int i = rows - 1; i >= 0; i--)
    {
        for (int j = 0; j <= i; j++)
        {
            printf("%ld   ", triangle[i][j]);
        }
        printf("\n");
    }
    return 0;
}

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