Hệ số nhị thức trong C ++

Hệ số nhị thức được ký hiệu là c (n, k) hoặc ⁿ c _r được định nghĩa là hệ số của x ^k trong khai triển nhị thức của (1 + X) ⁿ .

Hệ số nhị thức cũng cho giá trị của số cách trong đó k mục được chọn trong số n đối tượng, tức là k-tổ hợp của tập hợp n phần tử. Thứ tự lựa chọn các mặt hàng không được xem xét.

Ở đây, chúng ta được cung cấp hai tham số n và k và chúng ta phải trả về giá trị của hệ số nhị thức ⁿ c _k .

Ví dụ

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

Có thể có nhiều giải pháp cho vấn đề này,

Giải pháp chung

Có một phương pháp để tính giá trị của c (n, k) bằng cách gọi đệ quy. Công thức tiêu chuẩn để tìm giá trị của hệ số nhị thức sử dụng lệnh gọi đệ quy là -

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

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

Việc triển khai một cuộc gọi đệ quy sử dụng công thức trên -

Ví dụ

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

Đầu ra

The value of C(8, 5) is 56

Một giải pháp khác có thể đang sử dụng vấn đề con chồng chéo. Vì vậy, chúng tôi sẽ sử dụng thuật toán lập trình động để tránh vấn đề con.

Ví dụ

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

Đầu ra

The value of C(8, 5) is 56