3

...できれば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;
}

これを行うより良い方法があるかどうか疑問に思っていますか？

4

6 に答える 6

8 
choose(n,k) = n! /（nk）！か！

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;
于 2009-11-05T06:35:33.000 に答える
6

扱っている数値が非常に大きくなり、すぐにdouble値の精度を超えて、予想外に間違った結果が得られます。このため、 を使用するなどjava.math.BigInteger、この問題の影響を受けない任意精度のソリューションを検討することをお勧めします。

于 2009-11-05T06:35:30.287 に答える
1

為に

N!/((R!)(NR)!)

これを使用します（疑似コード）

if (R>N) return 0;

long r = max(R, N-r)+1;
if (R==N) return 1;

for (long m = r+1, long d = 2; m <= N; m++, d++ ) {
    r *= m;
    r /= d;
}
return r;
于 2010-05-28T13:42:34.947 に答える
1

これは C# でコーディングしましたが、可能な限り Java に適用できるようにしました。

これらのソースのいくつかに加えて、私からのいくつかの小さなものから派生しました.

コード：

public static long BinomialCoefficient(long n, long k)
{
    if (n / 2 < k)
        return BinomialCoefficient(n, n - k);

    if (k > n)
        return 0;

    if (k == 0)
        return 1;

    long result = n;
    for (long d = 2; d <= k; d++)
    {
        long gcd = (long)BigInteger.GreatestCommonDivisor(d, n);
        result *= (n / gcd);
        result /= (d / gcd);
        n++;
    }

    return result;
}
于 2009-11-05T07:38:13.527 に答える
0

このバージョンはBigInteger、浮動小数点演算を必要とせずn、62 未満のすべてのオーバーフロー エラーなしで動作します。28 を超える 62 は、オーバーフローが発生する最初のペアです。

public static long nChooseK(int n, int k) {
    k = Math.min(k, n - k);

    if (n < 0 || k < 0)
        throw new IllegalArgumentException();

    if (k == 0)
        return 1;

    long value = n--;

    for (int i = 2; i <= k; i++) {
        value = Math.multiplyExact(value, n--);
        value /= i;
    }

    return value;
}

次のテストは、これが正しいことを証明しています。

@Test
void nChooseKLongVsBigInt() {
    for (int n = 0; n < 62; n++) {
        for (int k = 0; k <= n; k++) {
            assertEquals(nChooseKBigInt(n, k), BigInteger.valueOf(nChooseK(n, k)));
        }
    }
}

private BigInteger nChooseKBigInt(int n, int k) {
    return factorial(n).divide(factorial(k).multiply(factorial(n - k)));
}

private BigInteger factorial(int number) {
    BigInteger result = BigInteger.ONE;

    for (int factor = 2; factor <= number; factor++) {
        result = result.multiply(BigInteger.valueOf(factor));
    }

    return result;
}
于 2018-02-04T12:08:11.003 に答える