数据结构
网络
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+ 浏览次数
广告