Die Binomialentwicklung ist eine mathematische Formel zur Erweiterung von Ausdrücken der Form (a+b)^n, wobei n eine positive ganze Zahl ist und a und b beliebige reelle oder komplexe Zahlen sein können. Die Entwicklung gibt die Koeffizienten jedes Termes in der Entwicklung an.
Eine Binomialentwicklung kann ausgedrückt werden als
$$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}$$
wobei $mathrm{^nC_r}$ der Binomialkoeffizient ist, gegeben durch
$mathrm{^nC_r=frac{n!}{r!times(n−r)!}}$, wobei n! Stellt die Fakultät von n
darMit der Erweiterung können alle Binomialterme mithilfe der obigen Formel berechnet und in die Erweiterungsgleichung eingesetzt werden.
Gegeben sind drei ganze Zahlen a, b und n. Finden Sie die Terme der Binomialentwicklung von (a+b)^n.
Geben Sie ein -
a = 1, b = 2, n = 3
Ausgabe -
[1, 6, 12, 8]
Die Binomialentwicklung (1+2)^3 lautet wie folgt
$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
Daher sind [1, 6, 12, 8] die Terme der Binomialentwicklung.
Geben Sie ein -
a = 7, b = 2, n = 11
Ausgabe -
[2401, 2744, 1176, 224, 16]
Verwenden Sie die binomiale Erweiterungsformel,
$$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}$$
Wir können den Wert jedes Termes ermitteln, indem wir die Binomialkoeffizienten rekursiv berechnen.
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
Im folgenden Programm berechnet die Funktion binomialCoeff() rekursiv den Wert des r-ten Binomialkoeffizienten, während die Funktion binomialTerms() den Wert des Binomialterms in der Erweiterung berechnet.
#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
Zeitliche Komplexität – O(2^n), wobei aufgrund des rekursiven Baums und 2^n Knoten in binomialTerms() die zeitliche Komplexität der binomialCoeff()-Funktion aufgrund der verschachtelten Schleife O(2^n) beträgt Rufen Sie binomialCoeff() n+1 Mal auf, die Komplexität der Funktion beträgt O(n^2). Die Gesamtkomplexität beträgt also O(2^n).
Raumkomplexität – Aufgrund des rekursiven Aufrufstapels beträgt die Raumkomplexität O(n).
Verwenden Sie die binomiale Erweiterungsformel,
$$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}$$
Wir können den Wert jedes Termes dieser Erweiterung ermitteln, indem wir Iteration und Division kombinieren.
Wir werden zwei Funktionen erstellen, wobei die erste Funktion den Binomialkoeffizienten berechnet und die zweite Funktion die Potenzen von a und b multipliziert, um den gewünschten Binomialterm zu erhalten.
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
Im folgenden Programm berechnet die Funktion binomialCoeff() den r-ten Binomialkoeffizienten, während die Funktion binomialTerms() alle Terme der Binomialentwicklung bei gegebenen a, b und n berechnet.
#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
Zeitkomplexität – O(n^2), wobei die Funktion binomialCoeff() eine Zeitkomplexität von O(r) hat, wobei r die kleinere Zahl von r und n-r ist und die Funktion binomialTerms() aufgrund verschachtelter Schleifen aufgerufen wird. binomialCoeff() n +1 mal, die Komplexität beträgt O(n^2). Die Gesamtkomplexität beträgt also O(n^2).
Raumkomplexität – O(n), da der Vektor binomiale Terme speichert.
Zusammenfassend lässt sich sagen, dass wir zum Ermitteln der Binomialterme der Binomialentwicklung eine der beiden oben genannten Methoden verwenden können. Die zeitliche Komplexität reicht von O(2^n) bis O(n^2), wobei die iterative Methode besser ist als die rekursive Methode Optimierter.
Das obige ist der detaillierte Inhalt vonSchreiben Sie ein Programm zum Drucken der Binomialentwicklungsreihe. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
