nCr을 계산하는 더 좋은 방법은 무엇입니까?

nCr을 계산하는 더 좋은 방법은 무엇입니까?

접근법 1:
C(n,r) = n!/(n-r)!r!

접근법 2:
Wilf의 Combinatory Algorithms라는 책에서 다음과 같은 사실을 발견했습니다.
C(n,r)는 다음과 같이 쓸 수 있습니다.C(n-1,r) + C(n-1,r-1).

예.

C(7,4) = C(6,4) + C(6,3) 
       = C(5,4) + C(5,3) + C(5,3) + C(5,2)
       .   .
       .   .
       .   .
       .   .
       After solving
       = C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)

보시다시피 최종 솔루션에는 곱셈이 필요하지 않습니다.모든 형태 C(n,r)에서 n==r 또는 r==1 중 하나이다.

구현한 샘플 코드는 다음과 같습니다.

int foo(int n,int r)
{
     if(n==r) return 1;
     if(r==1) return n;
     return foo(n-1,r) + foo(n-1,r-1);
}

출력은 이쪽을 참조해 주세요.

어프로치 2에서는 같은 서브 문제를 다시 해결하기 위해 재귀 호출을 하는 서브 문제가 중복됩니다.동적 프로그래밍을 사용하면 이를 피할 수 있습니다.

C(n,r)를 계산하는 더 좋은 방법이 무엇인지 알고 싶습니다.

두 방법 모두 시간을 절약할 수 있지만 첫 번째 방법은 정수 오버플로가 발생하기 쉽습니다.

접근법 1:

이 접근방식을 사용하면 최단 시간(최대 시간)에 결과를 얻을 수 있습니다.n/2반복)과 함께 곱셈을 주의하여 수행함으로써 오버플로 가능성을 줄일 수 있습니다.

long long C(int n, int r) {
    if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}

이 코드는 작은 끝에서 분자의 곱셈을 시작합니다. 그리고 모든 것의 곱으로서k연속된 정수는 로 나누어진다k!, 나눗셈의 문제는 없습니다.하지만 넘칠 가능성은 여전히 남아 있습니다. 또 다른 유용한 속임수는 나누기일 수 있습니다.n - r + i그리고.iGCD를 통해 증식 및 나눗셈을 수행합니다(또한 오버플로가 발생할 수 있음).

접근법 2:

이 방법에서는 실제로 파스칼의 삼각형을 구축하게 됩니다.동적 접근법은 재귀적 접근법보다 훨씬 빠르다(첫 번째 접근법은O(n^2)다른 하나는 기하급수적)입니다.단, 이 경우O(n^2)기억도 많이 남아요.

# define MAX 100 // assuming we need first 100 rows
long long triangle[MAX + 1][MAX + 1];

void makeTriangle() {
    int i, j;

    // initialize the first row
    triangle[0][0] = 1; // C(0, 0) = 1

    for(i = 1; i < MAX; i++) {
        triangle[i][0] = 1; // C(i, 0) = 1
        for(j = 1; j <= i; j++) {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }
}

long long C(int n, int r) {
    return triangle[n][r];
}

그러면 어떤 것이든 조회할 수 있습니다.C(n, r)에O(1)시간을.

특별히 필요한 경우C(n, r)(즉, 전체 삼각형이 필요하지 않음) 그러면 메모리 소비를 할 수 있습니다.O(n)같은 행의 삼각형을 위에서 아래로 덮어씁니다.

# define MAX 100
long long row[MAX + 1];

int C(int n, int r) {
    int i, j;

    // initialize by the first row
    row[0] = 1; // this is the value of C(0, 0)

    for(i = 1; i <= n; i++) {
        for(j = i; j > 0; j--) {
             // from the recurrence C(n, r) = C(n - 1, r - 1) + C(n - 1, r)
             row[j] += row[j - 1];
        }
    }

    return row[r];
}

내부 루프는 끝에서 계산을 단순화하기 시작했다.만약 당신이 인덱스 0에서 시작하면 다른 변수는 값을 덮어쓰저장할 필요가 있다.

나는 당신의 재귀적 접근 효율적으로와 연구해야 한다고 생각한다.DP. 하지만 이것은 문제가 제약 인상을 받을 시작할 것이다.http://www.spoj.pl/problems/MARBLES/ 를 참조해 주세요.

여기 나는 온라인 심사 위원들과 부호화 대회에 사용하는 함수이다.그러니까 사실상 일을 빨리 해.

long combi(int n,int k)
{
    long ans=1;
    k=k>n-k?n-k:k;
    int j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}

어프로치 #1의 효율적인 구현입니다.

재귀적 접근법은 괜찮지만, DP를 접근법과 함께 사용하면 하위 문제를 다시 해결하는 데 드는 오버헤드를 줄일 수 있습니다.이미 두 가지 조건이 있으니...

nCr(n,r) = nCr(n-1,r-1) + nCr(n-1,r);

nCr(n,0)=nCr(n,n)=1;

이제 하위 결과를 2-D 어레이에 저장함으로써 DP 솔루션을 쉽게 구축할 수 있습니다.

int dp[max][max];
//Initialise array elements with zero
int nCr(int n, int r)
{
       if(n==r) return dp[n][r] = 1; //Base Case
       if(r==0) return dp[n][r] = 1; //Base Case
       if(r==1) return dp[n][r] = n;
       if(dp[n][r]) return dp[n][r]; // Using Subproblem Result
       return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}

이항 계수의 소인수 분해를 구하는 것이 이항 계수를 계산하는 가장 효율적인 방법일 것입니다. 특히 곱셈이 비싼 경우에는 더욱 그렇습니다.

내가 아는 가장 빠른 방법은 블라디미르 방법이야nCr을 소인수로 분해함으로써 분열을 피할 수 있다.Vladimir가 말했듯이 Eratosthenes 체를 사용하면 이 작업을 매우 효율적으로 수행할 수 있습니다.또한 페르마의 작은 정리를 사용하여 nCr MOD(여기서 MOD는 소수)를 계산합니다.

동적 프로그래밍을 사용하면 여기에서 nCr을 쉽게 찾을 수 있습니다.

package com.practice.competitive.maths;

import java.util.Scanner;

public class NCR1 {

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int testCase = scanner.nextInt();
            while (testCase-- > 0) {
                int n = scanner.nextInt();
                int r = scanner.nextInt();
                int[][] combination = combination();
                System.out.println(combination[n][r]%1000000007);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static int[][] combination() {
        int combination[][] = new int[1001][1001];
        for (int i = 0; i < 1001; i++)
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i)
                    combination[i][j] = 1;
                else
                    combination[i][j] = combination[i - 1][j - 1] % 1000000007 + combination[i - 1][j] % 1000000007;
            }
        return combination;
    }
}

unsigned long long ans = 1,a=1,b=1;
        int k = r,i=0;
        if (r > (n-r))
            k = n-r;
        for (i = n ; k >=1 ; k--,i--)
        {
            a *= i;
            b *= k;
            if (a%b == 0)
            {
                a = (a/b);
                b=1;
            }
        }
        ans = a/b;

언급URL : https://stackoverflow.com/questions/11809502/which-is-better-way-to-calculate-ncr