0

私は最近Javaを自分で学んでいます。この関数は、組み合わせを計算することです。ただし、この関数の n と k の数には非常に小さな制限があることがわかりました。たとえば 100 などの大きな n または k を入力すると、毎回

Exception in thread "main" java.lang.ArithmeticException: / by zero
at Combination.combination(Combination.java:29)
at Combination.main(Combination.java:47)

または私に負の数を与える...

10000のような大きな数で動作させる方法はありますか?

ありがとう！

import java.util.HashMap; import java.util.Map;

public class Combination {

private Map<Long,Long> factorialMap = new HashMap<Long,Long>();

public Long getFactorial(int number) {
    Long val = factorialMap.get(number);
    if(val != null) {
        return val;
    } else {
        val = getFactorialRecursive(number);
        factorialMap.put((long) number, val);
        return val;
    }
}

public Long getFactorialRecursive(int number) {
    if(number == 1 || number == 0) {
        return 1L;
    } else {
        return number * getFactorialRecursive(number-1);
    }
}

public Long combination(int fromVal, int chooseVal) {
    return getFactorial(fromVal)/(getFactorial(chooseVal)*getFactorial(fromVal-chooseVal));
}


public static void main(String[] args) {
    int   n, k;
    Combination comb = new Combination();
    java.util.Scanner console = new java.util.Scanner(System.in);

    while (true)  // will break with k > n or illegal k or n
    {  System.out.print ("Value for n:  ");
       n = console.nextInt();
       if ( n < 0 ) break;
       System.out.print ("Value for k:  ");
       k = console.nextInt();;
       if ( k > n || k < 0 )
          break;
       System.out.print(n +" choose " + k + " = ");
       System.out.println(comb.combination(n,k));
    }
    console.nextLine();    // Set up for "Press ENTER...


} }
4

2 に答える 2

1

Java はデフォルトで約 10,000 回を超えて再帰することはなく、そもそもそのような大きな階乗を計算する必要はないと考えることをお勧めします。

例: 1000!/999! は 1000 です

ループを使用すると、はるかに早く停止できます。

public static BigInteger combination(int n, int r) {
    if (r * 2 > n) r = n - r;
    BigInteger num = BigInteger.ONE;
    BigInteger nr = BigInteger.valueOf(n - r);
    for (int i = n; i > r; i--) {
        num = num.multiply(BigInteger.valueOf(i));
        while (nr.compareTo(BigInteger.ONE) > 0 && num.mod(nr).equals(BigInteger.ZERO)) {
            num = num.divide(nr);
            nr = nr.subtract(BigInteger.ONE);
        }
    }
    while (nr.compareTo(BigInteger.ONE) > 0) {
        num = num.divide(nr);
        nr = nr.subtract(BigInteger.ONE);
    }
    return num;
}

ところで、効率が悪いのでLong、使用するつもりの場合は使用しません。long

比較のために、long を使用した同じコードを含めました。

public static long combination2(int n, int r) {
    if (r * 2 > n) r = n - r;
    long num = 1;
    int nr = n - r;
    for (int i = n; i > r; i--) {
        num *= i;
        while (nr > 1 && num % nr == 0) {
            num /= nr--;
        }
    }
    while (nr > 1)
        num /= nr--;
    return num;
}
于 2012-10-07T19:34:57.787 に答える
1

BigIntegerオブジェクトを使用する必要があります: http://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html

特に、あなたの問題はその21です！長くても大きすぎるため、オーバーフローします。別のオプションは double を使用することですが、精度が失われるため、整数の精度BigIntegerが必要な場合は行く方法です。

を使用すると、整数を次BigIntegerのように変換する必要があります。BigInteger

BigInteger bi = new BigInteger(intVal+"");

次に、add、multiply、divideおよびsubtract(とりわけ) を使用して、値を操作します (次のように)。

bi = bi.add(bi2);

次に、メソッドlongValue()を使用して値を戻すことができます (long に収まると仮定します)。

return bi.longValue();
于 2012-10-07T19:22:50.613 に答える