C++의 이항 계수

c(n,k) 또는 ⁿ 으로 표시되는 이항 계수 c_r x ^k 의 계수로 정의됩니다. (1+X) ⁿ 의 이항 전개에서 .

이항 계수는 또한 n개의 개체, 즉 n개의 요소 집합의 k 조합 중에서 k개의 항목이 선택되는 방법의 수 값을 제공합니다. 항목 선택 순서는 고려되지 않습니다.

여기에서 두 개의 매개변수 n과 k가 주어지고 이항 계수 ⁿ 의 값을 반환해야 합니다. c_k .

예시

Input : n = 8 and k = 3
Output : 56

이 문제에 대한 여러 가지 해결책이 있을 수 있습니다.

일반 솔루션

재귀 호출을 사용하여 c(n,k)의 값을 계산하는 방법이 있습니다. 재귀 호출을 사용하는 이항 계수 값을 찾는 표준 공식은 -

c(n,k) =c(n-1, k-1) + c(n-1, k)

c(n, 0) =c(n, n) =1

위의 공식을 사용하는 재귀 호출의 구현 -

예시

#include <iostream>
using namespace std;
int binomialCoefficients(int n, int k) {
   if (k == 0 || k == n)
   return 1;
   return binomialCoefficients(n - 1, k - 1) + binomialCoefficients(n - 1, k);
}
int main() {
   int n=8 , k=5;
   cout<<"The value of C("<<n<<", "<<k<<") is "<<binomialCoefficients(n, k);
   return 0;
}

출력

The value of C(8, 5) is 56

또 다른 솔루션 중복 하위 문제를 사용 중일 수 있습니다. 따라서 하위 문제를 피하기 위해 동적 프로그래밍 알고리즘을 사용합니다.

예시

#include <bits/stdc++.h>>
using namespace std;
int binomialCoefficients(int n, int k) {
   int C[k+1];
   memset(C, 0, sizeof(C));
   C[0] = 1;
   for (int i = 1; i <= n; i++) {
      for (int j = min(i, k); j > 0; j--)
         C[j] = C[j] + C[j-1];
   }
   return C[k];
}
int main() {
   int n=8, k=5;
   cout<<"The value of C("<<n<<", "<<k<<") is "<<binomialCoefficients(n,k);
   return 0;
}

출력

The value of C(8, 5) is 56