Java의 이항 계수

Question

2 개의 매개 변수가 있는데 int 결과를 반환하는 방법을 원합니다.이 코드를 받았지만, binom 등에 관한 모든 것을 이해하지 못하고 잘 모릅니다. 그것을 "변환"하는 방법 에는 double BC[126][126];이 그 위에 어딘가에 정의되어 있습니다. 하지만 나는이 n과 m에 대한 결과 만 원할 필요는 없습니다. 당신은 적어도 세 가지 구현이 그런데 ..

private void binom(int n, int m) { 
    int i, j; 

    if (n>=0) 
     if (m>n||m<0) System.err.println("Illegal m!!\n"); 

     else { 
      for(i=0;i<=n;i++) BC[i][0] = 1; 
      for(i=1;i<=m;i++) BC[0][i] = 0; 
      for(j=1;j<=m;j++) for(i=1;i<=n;i++) 
       BC[i][j] = BC[i-1][j-1] + BC[i-1][j]; 
     } 

    else System.err.println("Negative n!!\n"); 
} 

Answer 1

당신은 당신이 사이클의 세 가지로 계산 요소 인 BC[n][m]를 반환 할 수

을 (아마 그렇게 퍼팅 numpty 같은 소리) :

• 단순 재귀
• 이것을 수식을 사용(동적 프로그래밍)
• 사실 작업이 성가신 때문에 좋지 않습니다

시정의 : 당신이 매번 메소드가 호출됩니다 모든 계수를 계산하기 위해 피할 수 있지만 귀하의 경우가 아닌 경우 귀하의 접근 방식은 동적 프로그래밍 것 ..

Answer 2

비교 가능한 복잡도를 갖는 예 O (N 2⁾을 Computing Binomial Coefficients 문서를 참조하는 대신 O (N 2⁾의 O (N) 공간을 사용.