สัมประสิทธิ์ทวินามใน C++

สัมประสิทธิ์ทวินามแสดงเป็น c(n,k) หรือ ⁿ c_r ถูกกำหนดให้เป็นสัมประสิทธิ์ของ x ^k ในการขยายทวินามของ (1+X) ⁿ .

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

ที่นี่เราได้รับพารามิเตอร์สองตัว 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