Écrire un programme pour imprimer la série d'expansion binomiale

Le développement binomial est une formule mathématique utilisée pour développer des expressions de la forme (a+b)^n, où n est un entier positif et a et b peuvent être n'importe quel nombre réel ou complexe. Le développement donne les coefficients de chaque terme du développement.

Une expansion binomiale peut être exprimée comme

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

où $mathrm{^nC_r}$ est le coefficient binomial, donné par

$mathrm{^nC_r=frac{n!}{r!times(n−r)!}}$, où n! Représente la factorielle de n

L'expansion peut être utilisée pour calculer tous les termes binomiaux en utilisant la formule ci-dessus et les substituer dans l'équation d'expansion.

Énoncé du problème

Étant donné trois entiers a, b et n. Trouvez les termes du développement binomial de (a+b)^n.

Exemple Exemple 1

Entrez -

a = 1, b = 2, n = 3

Sortie -

[1, 6, 12, 8]

Explication

Explication

Le développement binomial (1+2)^3 est la suivante

$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

Par conséquent, [1, 6, 12, 8] sont les termes du développement binomial.

Exemple exemple 2

Entrez -

a = 7, b = 2, n = 11

Sortie -

[2401, 2744, 1176, 224, 16]

Méthode 1 : Expansion binomiale récursive

Utilisez la formule d'expansion binomiale,

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

Nous pouvons trouver la valeur de chaque terme en calculant récursivement les coefficients binomiaux.

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

Exemple : implémentation C++

Dans le programme ci-dessous, la fonction binomialCoeff() calcule récursivement la valeur du r-ième coefficient binomial, tandis que la fonction binomialTerms() calcule la valeur du terme binomial dans l'expansion.

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

Sortie

The binomial terms are : 16 96 216 216 81

Complexité temporelle - O(2^n), où en raison de l'arbre récursif et des 2^n nœuds dans binomialTerms(), la complexité temporelle de la fonction binomialCoeff() est O(2^n) en raison des appels de boucle imbriquées binomialCoeff () n+1 fois, la complexité de la fonction est O(n^2). La complexité globale est donc O(2^n).

Complexité spatiale - En raison de la pile d'appels récursifs, la complexité spatiale est O(n).

Méthode 2 : Expansion binomiale itérative

Utilisez la formule d'expansion binomiale,

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

On peut trouver la valeur de chaque terme de cette expansion en combinant itération et division.

Nous allons créer 2 fonctions où la première fonction calcule le coefficient binomial et la deuxième fonction multiplie les puissances de a et b pour obtenir le terme binomial souhaité.

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

Exemple : implémentation C++

Dans le programme ci-dessous, la fonction binomialCoeff() calcule le r-ème coefficient binomial, tandis que la fonction binomialTerms() calcule tous les termes du développement binomial étant donné a, b et 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;
}

Sortie

The binomial terms are : 16 96 216 216 81

Complexité temporelle - O(n^2), où la fonction binomialCoeff() a une complexité temporelle de O(r), où r est le plus petit nombre de r et n-r et la fonction binomialTerms() en raison des appels de boucle imbriquée binomialCoeff() n+1 fois, la complexité est O(n^2). La complexité globale est donc O(n^2).

Complexité spatiale - O(n) puisque le vecteur stocke les termes binomiaux.

Conclusion

En résumé, pour trouver le terme binomial du développement binomial, on peut utiliser l'une des deux méthodes mentionnées ci-dessus, la complexité temporelle va de O(2^n) à O(n^2), où la méthode itérative est meilleure que la méthode récursive Plus optimisée.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!