寫一個程式來列印二項式展開系列

二項展開式是一個數學公式，用來展開 (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 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

時間複雜度 - 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 = 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)。

結論

總之，要找出二項式展開的二項式項，我們可以使用上述兩種方法之一，時間複雜度範圍從O(2^n)到O(n^2)，其中迭代方法比遞歸方法更優化。

以上是寫一個程式來列印二項式展開系列的詳細內容。更多資訊請關注PHP中文網其他相關文章！