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

Hệ số nhị thứ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ị số cách chọn k vật từ n vật thể, tức là k-kết hợp của tập n phần tử. Thứ tự chọn không quan trọng.

Ở đây, cho hai tham số n và k, ta phải trả về giá trị hệ số nhị thức ⁿc_k.

Ví dụ

Input : n = 8 và k = 3 Output : 56

Có thể có nhiều giải pháp cho bài toán này,

Giải pháp tổng quát

Có phương pháp tính c(n,k) bằng gọi đệ quy. Công thức chuẩn dùng đệ quy:

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

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

Triển khai gọi đệ quy 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<<"Giá trị C("<<n<<", "<<k<<") là "<<binomialCoefficients(n, k);
    return 0;
}

Kết quả

Giá trị C(8, 5) là 56

Giải pháp khác có thể dùng bài toán con chồng chéo. Vì vậy, dùng quy hoạch động để tránh tính lại bài toá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<<"Giá trị C("<<n<<", "<<k<<") là "<<binomialCoefficients(n,k);
    return 0;
}

Kết quả

Giá trị C(8, 5) là 56