C语言组合数（nCr）计算程序大数值输出错误问题咨询

错误根源 #

1. 整数溢出：你的程序用int类型存储阶乘结果，而int的最大取值通常是2147483647。当n≥13时，13! = 6227020800已经超出这个范围，计算时会触发溢出，导致fact变成无意义的错误值，最终组合数计算结果完全错误（比如18C2得到3就是溢出后的错误计算结果）。
2. 低效的计算逻辑：直接计算n!的方式会快速放大数值，加速溢出，没有利用组合数的数学性质优化计算流程。

你提到的(24 * 23)/2错误，大概率也是类似的溢出问题（可能测试了更大的数值），int类型无法承载超出范围的中间计算结果。

修正方案 #

通过两个关键优化解决问题：

• 改用更大范围的数值类型long long，它能存储到2^63-1，足以覆盖更大的组合数计算。
• 利用组合数的对称性和逐步约分逻辑，避免直接计算大阶乘。

修正后的代码 #

#include <stdio.h>

int main() {
    int n, r;
    scanf("%d %d", &n, &r);
    
    // 取r和n-r中的较小值，减少计算次数
    if (r > n - r) {
        r = n - r;
    }
    
    long long result = 1;
    // 逐步计算并约分，保证每一步都是整数运算
    for (int i = 1; i <= r; i++) {
        result = result * (n - r + i) / i;
    }
    
    printf("the ncr is %lld", result);
    return 0;
}

代码说明 #

• 类型优化：用long long存储结果，避免小范围数值溢出。
• 对称性优化：组合数C(n,r) = C(n,n-r)，取较小的r可以减少循环次数，提升效率同时降低溢出风险。
• 逐步约分：通过先乘后除的方式，每一步计算都是整数（组合数必然是整数），不会产生过大的中间值，彻底避免溢出问题。比如计算18C2时，先算1*18/1=18，再算18*17/2=153，全程数值都在安全范围内。

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