大输入参数下nCr组合数计算代码结果错误问题分析

第一段代码的问题 #

这段代码存在两处致命问题：

• 计算过程中数值溢出：long类型的最大值为9223372036854775807，但组合数C(200,100)的实际值远大于该范围，导致long数组存储的中间结果提前溢出，计算过程就已经出错。
• 返回时强制类型转换错误：即便中间结果正确，代码最后将long类型值强制转为Integer返回，而Integer的最大值仅为2147483647，远小于目标结果，溢出后得到错误数值。

第二段代码的问题 #

这段代码用BigInteger解决了计算过程中的溢出问题，但返回环节的类型转换依然导致错误：
代码最后调用arr[r].intValue()将BigInteger转换为Integer返回，而C(200,100)的数值远超Integer的取值范围，转换时直接溢出，最终输出错误结果。

正确改进方案 #

将函数的返回类型改为BigInteger，避免任何不必要的类型转换，确保结果完整保留。修正后的示例代码：

BigInteger ncr(Integer n, Integer r) {
    if(n < r)
        return BigInteger.ZERO;
    BigInteger[] arr = new BigInteger[n+1];
    
    arr[0] = BigInteger.valueOf(1);
    for(int i = 1; i <= n; i++){
        for(int j = i; j > 0; j--){
            if(arr[j] == null)
                arr[j] = BigInteger.ZERO;
            arr[j] = arr[j].add(arr[j-1]);
        }
    }
    
    return arr[r];
}

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