Schreiben Sie ein Programm zum Drucken der Binomialentwicklungsreihe

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

dar

Mit der Erweiterung können alle Binomialterme mithilfe der obigen Formel berechnet und in die Erweiterungsgleichung eingesetzt werden.

Problemstellung

Gegeben sind drei ganze Zahlen a, b und n. Finden Sie die Terme der Binomialentwicklung von (a+b)^n.

Beispiel Beispiel 1

Geben Sie ein -

a = 1, b = 2, n = 3

Ausgabe -

[1, 6, 12, 8]

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

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.

Beispiel Beispiel 2

Geben Sie ein -

a = 7, b = 2, n = 11

Ausgabe -

[2401, 2744, 1176, 224, 16]

Methode 1: Rekursive Binomialerweiterung

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.

Pseudocode

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

Beispiel: C++-Implementierung

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;
}

Ausgabe

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).

Methode 2: Iterative Binomialerweiterung

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.

Pseudocode

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

Beispiel: C++-Implementierung

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;
}

Ausgabe

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.

Fazit

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!