用Java实现选择表示法的好方法是什么？ [英] What is a good way to implement choose notation in Java?

问题描述

...最好使用Java。这是我的东西：

... preferably in Java. Here is what I have:

//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;
}

我想知道是否有更好的方法？

I'm wondering if there's a better way of doing this?

推荐答案

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

您可以在O（k）中执行以下操作：

You could do something like this in 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是安全的）您可以这样做：

EDIT If x and y are large, you will overflow more slowly (i.e., be safe for larger values of x & y) if you divide your answer as you go along:

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

这篇关于用Java实现选择表示法的好方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！