C++の二項係数

c（n、k）または ⁿ として表される二項係数 c _r x ^k の係数として定義されます （1 + X） ⁿ の二項展開で 。

二項係数は、n個のオブジェクトからk個のアイテムが選択される方法の数の値も示します。つまり、n個の要素セットのk個の組み合わせです。考慮されていないアイテムの選択の順序。

ここでは、2つのパラメーター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