資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究二項係數在 C++ 中的表示
二項係數表示為 c(n,k) 或 ncr，定義為二項式展開 (1+X)n 中 xk 的係數。
二項係數還給出從 n 個物件中選取 k 個專案的方案數，即 n 元組的 k-組合。不考慮專案選擇順序。
在此，我們給定兩個引數 n 和 k，並且我們必須返回二項係數 nck 的值。
示例
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
更新日期：2019 年 11 月 22 日
6K+ 瀏覽次數
廣告