Java 计算 nCr 抛出算术异常的程序 "Divide by zero"

Question

以下代码尝试计算给定 n 的各种值的 nCr 值，这里 r 从 0 到 n。

输入格式如下：-

输入格式

第一行包含测试用例数量T。接下来是 T 行，每行包含一个整数 n.

约束条件

 1<=T<=200 
 1<=n< 1000

输出格式

对于每个 n 输出 nC0 到 nCn 的列表，每个列表由一个新行中的单个 space 分隔。如果数字很大，只打印最后 9 位数字。即模 10^9

所以示例输入的格式如下：-

样本输出格式如下：-

 1 2 1
 1 4 6 4 1
 1 5 10 10 5 1

这是代码

 import java.io.*;
 import java.util.*;
 import java.math.*;

public class Solution {

  public static void main(String[] args) {
      /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int j = 0;

    for(int i = 0; i < n; i++){
        int a = scan.nextInt();
        j = 0;
        while(j <= a){
              if( j == 0 || j == a){
                  System.out.print(1 + " ");
              }
              else if( j == 1 || j == (a - 1)){
                  System.out.print(a + " ");
              }else{
                  BigInteger  a1 = (Num(a,j));
                  BigInteger b1 = BigInteger.valueOf(fact(j));
                  BigInteger c1 = a1.divide(b1);
                  BigInteger x1 = BigInteger.valueOf(1000000000);
                  System.out.print( c1.mod(x1)  +" ");
              } 
            j++;
        }
        System.out.println();

    }
}

public static BigInteger Num(int a, int j){
    BigInteger prod = BigInteger.valueOf(1);
    for(int k = 0; k < j; k++){
        int z = a - k;
        BigInteger b = BigInteger.valueOf(z);
        prod = prod.multiply(b);
    }
    return prod;
}

public static long fact(long j){
    long prod = 1;
    for(long i = j; i > 0; i--){
       prod *= i; 
    }
    return prod;
 }
}

它清除了一些测试用例，但在许多测试用例中都失败了。说运行时间错误，当我在输入 1 999 时对其进行测试时它抛出了算术异常 "Divide by zero"。

这是异常日志：-

      Exception in thread "main" java.lang.ArithmeticException: BigInteger divide by zero
        at java.math.MutableBigInteger.divideKnuth(MutableBigInteger.java:1179)
        at java.math.BigInteger.divideKnuth(BigInteger.java:2049)
        at java.math.BigInteger.divide(BigInteger.java:2030)
        at Solution.main(Solution.java:25)

需要做什么来解决这个问题？

Answer 1

您必须使用 BigInteger 来计算不超过 1000 的阶乘。

public static BigInteger fact(long j){
  BigInteger prod = BigInteger.ONE;
  for(long i = j; i > 0; i--){
    BigInteger f = BigInteger.valueOf( i );
    prod = prod.multiply( f ); 
  }
  return prod;
}

Java 计算 nCr 抛出算术异常的程序 "Divide by zero"

Java Program to compute nCr throwing Arithmetic Exception "Divide by zero"

java

algorithm

combinations