資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究列印二項式展開式程式
二項式展開是一個數學公式，用於展開形如 (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 的二項式展開式如下
$\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]
方法 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
時間複雜度 - O(2^n)，其中 binomialCoeff() 函式的時間複雜度為 O(2^n)，因為遞迴樹中有 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}$$
我們可以透過結合迭代和除法來找到該展開式中每一項的值。
我們將建立 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)，其中迭代方法比遞迴方法更最佳化。
407 次瀏覽
