Was ist ein guter Weg Notation in Java zu implementieren wählen?

Question

... vorzugsweise in Java. Hier ist, was ich habe:

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

Ich frage mich, ob es ein besserer Weg, dies zu tun?

Answer 1

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

Sie können in O (k) so etwas tun:

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

Bearbeiten Wenn x und y groß sind, werden Sie langsamer Überlauf (das heißt, für größere Werte von x & y sicher sein), wenn Sie Ihre Antwort teilen, wie Sie gehen zusammen:

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

Answer 2

Die Zahlen Sie beschäftigen wird sehr groß werden und wird schnell die Genauigkeit der double Werte überschreiten, Sie unerwartet falsche Ergebnisse. Aus diesem Grund möchten Sie können eine beliebige genaue Lösung wie mit java.math.BigInteger, die unter diesem Problem leiden nicht berücksichtigen.

Answer 3

Was du hast sieht ziemlich klar für mich, um ehrlich zu sein. Zwar würde ich die return-Anweisungen in Klammern setzen, wie, dass die Konvention ich folgen, aber abgesehen davon, dass es aussieht, so gut, wie es nur geht.

Ich glaube, ich würde wahrscheinlich die Reihenfolge der zweiten umzukehren, so dass beiden Schleife aufsteigen.

Wie Greg sagt, wenn Sie präzise Antworten für eine große Anzahl erhalten müssen, sollten Sie alternative Datentypen berücksichtigen. Da das Ergebnis sollte immer eine ganze Zahl sein, könnten Sie holen wollen BigInteger (trotz aller Divisionen wird immer das Ergebnis eine ganze Zahl sein):

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 4

I codiert diese in C #, aber ich versuchte, es als zutreffend wie möglich zu Java zu machen.

von einigen dieser Quellen stammen, plus ein paar kleine Dinge von mir.

• http://blog.plover.com/math/choose.html
• http://blog.plover.com/math/choose-2.html

Code:

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

Answer 5

für

  

N! / ((R!) (N-R)!)

Mit diesem (Pseudocode)

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;

Answer 6

Diese Version benötigt keine BigInteger oder Gleitkomma-Arithmetik und arbeitet ohne Überlauffehler für all n weniger als 62 62 über 28 das erste Paar ist in einem Überlauf führen.

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

Der folgende Test zeigt, dass dies wahr ist:

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