C++ 打印二项式展开序列

二项式展开是一种数学公式，用于展开形式为(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]

解释

二项式展开式(1+2)^3如下：

(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 + 314 + 1*1*8$

因此，[1, 6, 12, 8]是二项式展开的项。

示例2

输入 −

a = 7, b = 2, n = 11

输出 −

[2401, 2744, 1176, 224, 16]

方法1：递归二项式展开

使用二项式展开公式，

\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 procedure

procedure 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 = arr
end procedure

示例：C++实现

在下面的程序中，binomialCoeff()函数递归地计算第r个二项式系数的值，而binomialTerms()函数计算展开式中二项式项的值。

#include <bits/stdc++.h>
using namespace std;
// Function for calculating binomial coefficients
int 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 terms
vector<int> binomialTerms(int a, int b, int n){
   vector<int> 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<int> 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

时间复杂度 − 当binomialCoeff()函数中有2^n个递归树节点时，其时间复杂度为O(2^n)，而binomialTerms()函数由于嵌套循环调用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}

通过组合迭代和除法，我们可以计算出展开式的每一项的值。

我们将创建两个函数，第一个函数计算二项式系数，第二个函数将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 = res
end procedure

procedure 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 = arr
end procedure

示例：C++实现

在下面的程序中，binomialCoeff()函数计算第r个二项式系数，而binomialTerms()函数计算给定a、b和n的二项式展开的所有项。

#include <bits/stdc++.h>
using namespace std;
// Function for calculating binomial coefficients
int 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 terms
vector<int> binomialTerms(int a, int b, int n){
   vector<int> 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<int> 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)，由于存储binomial terms的vector。

结论

总之，要找到二项式展开的二项式项，可以实现上述两种方法之一，其时间复杂度范围从O(2^n)到O(n^2)，其中迭代方法比递归方法更优化。