Java组合数计算程序大数值输入输出0异常求助

你的程序输出0的核心问题是long类型的整数溢出。

Java中long的最大值是9223372036854775807，而50的阶乘（50!）约等于3.04140932×10^64，这个数值远远超出了long的存储范围。当计算nFactorial时，乘到某个数后就会溢出，溢出后的数值会变成负数或者0（取决于溢出的次数），最终导致nFactorial / (rFactorial * minusFactorial)的结果为0。

这里提供两种可行的修复方式：

方式一：使用BigInteger处理大数值 #

BigInteger可以支持任意大小的整数运算，完全避免溢出问题，修改后的代码如下：

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter element number: ");
        int n = scanner.nextInt();
        System.out.print("selection number: ");
        int r = scanner.nextInt();
        int minus = n - r;

        BigInteger nFactorial = BigInteger.ONE;
        BigInteger rFactorial = BigInteger.ONE;
        BigInteger minusFactorial = BigInteger.ONE;

        for(int i = 1; i <= n; i++) {
            nFactorial = nFactorial.multiply(BigInteger.valueOf(i));
        }
        for(int i = 1; i <= r; i++) {
            rFactorial = rFactorial.multiply(BigInteger.valueOf(i));
        }
        for(int i = 1; i <= minus; i++) {
            minusFactorial = minusFactorial.multiply(BigInteger.valueOf(i));
        }

        BigInteger comb = nFactorial.divide(rFactorial.multiply(minusFactorial));
        System.out.println("C(" + n + "," + r + ") combination: " + comb);
    }
}

方式二：优化计算逻辑，分步约分 #

直接计算大阶乘效率低且容易溢出，我们可以利用组合数的公式特性，分步计算并约分，减少中间结果的大小：
组合数公式可转化为：
C(n,r) = n*(n-1)*...*(n-r+1)/(r*(r-1)*...*1)
这样只需要计算r次乘法和除法，中间结果不会过大，修改后的代码：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter element number: ");
        int n = scanner.nextInt();
        System.out.print("selection number: ");
        int r = scanner.nextInt();
        
        // 取r和n-r中的较小值，减少计算次数
        r = Math.min(r, n - r);
        long result = 1;
        
        for (int i = 1; i <= r; i++) {
            // 先乘再除，保证每次除法都是整数
            result = result * (n - r + i) / i;
        }
        
        System.out.println("C(" + n + "," + r + ") combination: " + result);
    }
}

这种方式不仅避免了溢出，还提升了计算效率，对于C(50,5)的计算，中间结果始终在long的范围内，能得到正确结果2118760。

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