在Java中实现选择符号的好方法是什么？

Question

...最好是用Java.这是我有的:

//x choose y
public static double choose(int x, int y) {
    if (y < 0 || y > x) return 0;
    if (y == 0 || y == x) return 1;

    double answer = 1;
    for (int i = x-y+1; i <= x; i++) {
        answer = answer * i;
    }
    for (int j = y; j > 1; j--) {
        answer = answer / j;
    }
    return answer;
}

我想知道是否有更好的方法来做到这一点？

Answer 1

choose(n,k) = n! / (n-k)! k!

你可以在O(k)中做这样的事情:

public static double choose(int x, int y) {
    if (y < 0 || y > x) return 0;
    if (y > x/2) {
        // choose(n,k) == choose(n,n-k), 
        // so this could save a little effort
        y = x - y;
    }

    double denominator = 1.0, numerator = 1.0;
    for (int i = 1; i <= y; i++) {
        denominator *= i;
        numerator *= (x + 1 - i);
    }
    return numerator / denominator;
}

编辑如果x和y大,你会溢出比较慢,如果你,你走划分你的答案(即,对于较大的X和Y的值是安全的):

    double answer = 1.0;
    for (int i = 1; i <= y; i++) {
        answer *= (x + 1 - i);
        answer /= i;           // humor 280z80
    }
    return answer;

Answer 2

说实话,你对我的看法非常清楚.不可否认,我将返回语句放在括号中,因为这是我遵循的惯例,但除此之外,它看起来和它一样好.

我想我可能会颠倒第二个循环的顺序,这样两个循环都是递增的.

正如格雷格所说,如果你需要获得大数的准确答案,你应该考虑其他数据类型.鉴于结果应始终为整数,您可能想要选择BigInteger(尽管所有除法,结果将始终为整数):

public static BigInteger choose(int x, int y) {
    if (y < 0 || y > x) 
       return BigInteger.ZERO;
    if (y == 0 || y == x) 
       return BigInteger.ONE;

    BigInteger answer = BigInteger.ONE;
    for (int i = x - y + 1; i <= x; i++) {
        answer = answer.multiply(BigInteger.valueOf(i));
    }
    for (int j = 1; j <= y; j++) {
        answer = answer.divide(BigInteger.valueOf(j));
    }
    return answer;
}

Answer 3

您正在处理的数字将变得非常大并且将快速超过double值的精度,从而给您出乎意料的错误结果.因此,您可能需要考虑使用的任意精度解决方案java.math.BigInteger,这不会遇到此问题.