二项展开式是一个数学公式，用于展开 (a+b)^n 形式的表达式，其中 n 是正整数，a 和 b 可以是任何实数或复数。展开式给出了展开式中各项的系数。
一个二项式展开可以表示为
$$mathrm{(a+b)^n= ^nC_0a^nb^0+ ^nC_1a^{n-1}b^1 + ^nCa^{n-2}b^2+… + ^nC_ra^{n-r}b^r+…+ ^nC_na^0b^n}$$
其中 $mathrm{^nC_r}$ 是二项式系数，由下式给出
$mathrm{^nC_r=frac{n!}{r!times(n−r)!}}$，其中n！表示n的阶乘
展开式可用于使用上述公式计算所有二项式项并将其代入展开式方程。
问题陈述
给定三个整数 a、b 和 n。求 (a+b)^n 的二项展开式的项。
示例示例1
输入 –
a = 1, b = 2, n = 3
输出 –
[1, 6, 12, 8]
Explanation
的中文翻译为：
解释
二项式展开式(1+2)^3如下所示
$mathrm{(1+2)^3 = C(3,0)a^3b^0 + C(3,1)a^2b^1 + C(3,2)a^1b^2 + C(3,3)a^0b^3}$
= 1*1*1 + 3*1*2 + 3*1*4 + 1*1*8
因此，[1, 6, 12, 8] 是二项式展开的项。
示例例子2
输入 –
a = 7, b = 2, n = 11
输出 –
[2401, 2744, 1176, 224, 16]
方法一：递归二项式展开
使用二项式展开公式，
$$mathrm{(a+b)^n= ^nC_0a^nb^0+ ^nC_1a^{n-1}b^1 + ^nCa^{n-2}b^2+… + ^nC_ra^{n-r}b^r+…+ ^nC_na^0b^n}$$
我们可以通过递归计算二项式系数来找到每一项的值。
伪代码
procedure binomialCoeff (n, r) if r == 0 or r == n ans = 1 else ans = binomialCoeff (n - 1, r - 1) + binomialCoeff (n - 1, r)end procedureprocedure binomialTerms (a, b, n) Initialize vector: arr for r = 0 to n coeff = binomialCoeff(n, r) term = coeff + a^n-r + b^r add the term to arr ans = arrend procedure
示例：C++实现
在下面的程序中，binomialCoeff()函数递归地计算第r个二项式系数的值，而binomialTerms()函数计算展开式中二项式项的值。
#include using namespace std;// Function for calculating binomial coefficientsint binomialCoeff(int n, int r){ if (r == 0 || r == n) { return 1; } else { return binomialCoeff(n - 1, r - 1) + binomialCoeff(n - 1, r); }}// Function for calculating the binomial termsvector binomialTerms(int a, int b, int n){ vector ans; for (int r = 0; r <= n; r++) { // Calculate the rth binomial coefficients int coeff = binomialCoeff(n, r); // Calculate the rth binomial expansion term int term = coeff * pow(a, n - r) * pow(b, r); ans.push_back(term); } return ans;}int main(){ int a = 2, b = 3, n = 4; vector res = binomialTerms(a, b, n); cout << "The binomial terms are : "; for (int i = 0; i < res.size(); i++) { cout << res[i] << " "; } return 0;}
输出
The binomial terms are : 16 96 216 216 81
时间复杂度 – O(2^n)，其中由于递归树和 binomialTerms() 中的 2^n 个节点，binomialCoeff() 函数的时间复杂度为 O(2^n)由于嵌套循环调用 binomialCoeff() n+1 次，函数的复杂度为 O(n^2)。因此总体复杂度为 O(2^n)。
空间复杂度 – 由于递归调用栈，空间复杂度为O(n)。
方法 2：迭代二项式展开
使用二项式展开公式，
$$mathrm{(a+b)^n= ^nC_0a^nb^0+ ^nC_1a^{n-1}b^1 + ^nCa^{n-2}b^2+… + ^nC_ra^{n-r}b^r+…+ ^nC_na^0b^n}$$
我们可以通过结合迭代和除法来找到这个展开式的每一项的值。
我们将创建 2 个函数，其中第一个函数计算二项式系数，第二个函数将 a 和 b 的幂相乘以获得所需的二项式项。
伪代码
procedure binomialCoeff (n, r) res = 1 if r > n - r r = n - r end if for i = 0 to r-1 res = res * (n - i) res = res / (i + 1) ans = resend procedureprocedure binomialTerms (a, b, n) Initialize vector: arr for r = 0 to n coeff = binomialCoeff(n, r) term = coeff + a^n-r + b^r add the term to arr ans = arrend procedure
示例：C++实现
在下面的程序中，binomialCoeff() 函数计算第 r 个二项式系数，而 binomialTerms() 函数计算给定 a、b 和 n 的二项式展开的所有项。
#include using namespace std;// Function for calculating binomial coefficientsint binomialCoeff(int n, int r){ int res = 1; if (r > n - r) { r = n - r; } for (int i = 0; i < r; i++) { res *= (n - i); res /= (i + 1); } return res;}// Function for calculating the binomial termsvector binomialTerms(int a, int b, int n){ vector ans; for (int r = 0; r <= n; r++){ // Calculate the rth binomial coefficients int coeff = binomialCoeff(n, r); // Calculate the rth binomial expansion term int term = coeff * pow(a, n - r) * pow(b, r); ans.push_back(term); } return ans;}int main(){ int a = 2, b = 3, n = 4; vector res = binomialTerms(a, b, n); cout << "The binomial terms are : "; for (int i = 0; i < res.size(); i++){ cout << res[i] << " "; } return 0;}
输出
The binomial terms are : 16 96 216 216 81
时间复杂度 – O(n^2)，其中 binomialCoeff() 函数的时间复杂度为 O(r)，其中 r 是 r 和 n-r 中较小的数字以及 binomialTerms() 函数由于嵌套循环调用 binomialCoeff() n+1 次，复杂度为 O(n^2)。因此总体复杂度为 O(n^2)。
空间复杂度 – 由于向量存储二项式项，所以为O(n)。
结论
总之，要找到二项式展开的二项式项，我们可以使用上述两种方法之一，时间复杂度范围从O(2^n)到O(n^2)，其中迭代方法比递归方法更优化。
以上就是编写一个程序来打印二项式展开系列的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445436.html
微信扫一扫 
支付宝扫一扫 
