Java에서 선택한 표기법을 구현하는 좋은 방법은 무엇입니까?

https://stackoverflow.com/questions/1678690

16-09-2019
|

문제

... 바람직하게는 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;
}

더 나은 방법이 있는지 궁금합니다.

해결책

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;

다른 팁

당신이 다루고있는 숫자는 상당히 커지고 정밀도를 빨리 초과 할 것입니다. double 값, 예기치 않게 잘못된 결과를 제공합니다. 이러한 이유로 사용과 같은 임의의 차가 솔루션을 고려할 수 있습니다. java.math.BigInteger, 이 문제로 고통받지 않을 것입니다.

당신이 가진 것은 솔직히 말해서 나에게 꽤 분명해 보입니다. 분명히, 나는 그것이 내가 따르는 컨벤션이기 때문에 귀환 진술을 중괄호에 넣었지만, 그 외에는 그것이 얻는만큼 좋아 보인다.

두 번째 루프의 순서를 뒤집어 두 루프가 올라가고 있다고 생각합니다.

Greg가 말했듯이, 많은 숫자에 대한 정확한 답변을 받아야한다면 대체 데이터 유형을 고려해야합니다. 결과가 항상 정수 여야한다는 점을 감안할 때 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;
}

나는 이것을 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;
}

~을 위한

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;

이 버전에는 필요하지 않습니다 BigInteger 또는 부동 소수점 산술 및 모든 사람의 오버플로 오류없이 작동합니다. n 62 미만의 28 세 이상이 오버플로를 초래 한 첫 번째 쌍입니다.

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

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow