สัมประสิทธิ์ไบนอมีอัลใน C++

สัมประสิทธิ์ไบนอมีอัล (Binomial coefficient) แทนด้วย c(n,k) หรือ ⁿc_r นิยามว่าเป็นสัมประสิทธิ์ของ x^k ในการขยายไบนอมีอัลของ (1+X)ⁿ

สัมประสิทธิ์ไบนอมีอัลยังให้ค่าของจำนวนวิธีที่เลือก k รายการจาก n วัตถุ คือ k-combinations ของ n-element set ลำดับการเลือกไม่ได้ถูกพิจารณา

ที่นี่ เราได้รับสองพารามิเตอร์ n และ k และต้องคืนค่าของสัมประสิทธิ์ไบนอมีอัล ⁿc_k

ตัวอย่าง

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

สามารถมีหลายวิธีแก้ปัญหานี้

วิธีทั่วไป

มีวิธีคำนวณค่า c(n,k) โดยใช้การเรียกซ้ำ (recursive) สูตรมาตรฐานสำหรับหาค่าสัมประสิทธิ์ไบนอมีอัลที่ใช้การเรียกซ้ำคือ −

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

วิธีอื่น อาจใช้ overlapping subproblem ดังนั้นเราจะใช้อัลกอริทึมไดนามิกโปรแกรมมิ่งเพื่อหลีกเลี่ยงซับปัญหา

ตัวอย่าง

#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