Tulis program untuk mencetak siri pengembangan binomial

Peluasan binomial ialah formula matematik yang digunakan untuk mengembangkan ungkapan bentuk (a+b)^n, dengan n ialah integer positif dan a dan b boleh menjadi sebarang nombor nyata atau kompleks. Peluasan memberikan pekali bagi setiap sebutan dalam pengembangan.

Peluasan binomial boleh dinyatakan sebagai

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

di mana $mathrm{^nC_r}$ ialah pekali binomial, diberikan oleh

$mathrm{^nC_r=frac{n!}{r!times(n−r)!}}$, di mana n! Mewakili faktorial bagi n

Peluasan boleh digunakan untuk mengira semua sebutan binomial menggunakan formula di atas dan menggantikannya ke dalam persamaan pengembangan.

Pernyataan Masalah

Diberi tiga integer a, b dan n. Cari sebutan pengembangan binomial bagi (a+b)^n.

Contoh Contoh 1

Masuk -

a = 1, b = 2, n = 3

Output -

[1, 6, 12, 8]

Penjelasan

Penjelasan

Peluasan binomial (1+2)^3 adalah seperti berikut

$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

Oleh itu, [1, 6, 12, 8] ialah sebutan bagi pengembangan binomial.

Contoh contoh 2

Masuk -

a = 7, b = 2, n = 11

Output -

[2401, 2744, 1176, 224, 16]

Kaedah 1: Pengembangan Binomial Rekursif

Gunakan formula pengembangan binomial,

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

Kita boleh mencari nilai setiap sebutan dengan mengira secara rekursif pekali binomial.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam atur cara di bawah, fungsi binomialCoeff() secara rekursif mengira nilai pekali binomial ke-r, manakala fungsi binomialTerms() mengira nilai sebutan binomial dalam pengembangan.

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

Output

The binomial terms are : 16 96 216 216 81

Kerumitan masa - O(2^n), di mana disebabkan oleh pokok rekursi dan 2^n nod dalam binomialTerms(), kerumitan masa bagi fungsi binomialCoeff() ialah O(2^n) disebabkan oleh gelung bersarang panggil binomialCoeff() n+1 kali, kerumitan fungsi ialah O(n^2). Jadi kerumitan keseluruhan ialah O(2^n).

Kerumitan Angkasa - Disebabkan tindanan panggilan rekursif, kerumitan ruang ialah O(n).

Kaedah 2: Pengembangan Binomial Berulang

Gunakan formula pengembangan binomial,

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

Kita boleh mencari nilai setiap istilah pengembangan ini dengan menggabungkan lelaran dan pembahagian.

Kami akan mencipta 2 fungsi di mana fungsi pertama mengira pekali binomial dan fungsi kedua mendarabkan kuasa a dan b untuk mendapatkan sebutan binomial yang dikehendaki.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam atur cara di bawah, fungsi binomialCoeff() mengira pekali binomial ke-r, manakala fungsi binomialTerms() mengira semua sebutan pengembangan binomial yang diberi a, b dan 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;
}

Output

The binomial terms are : 16 96 216 216 81

Kerumitan Masa - O(n^2) dengan fungsi binomialCoeff() mempunyai kerumitan masa O(r) di mana r ialah bilangan r yang lebih kecil dan n-r dan binomialTerms() fungsi dipanggil disebabkan gelung bersarang binomialCoeff() n +1 kali, kerumitannya ialah O(n^2). Jadi kerumitan keseluruhan ialah O(n^2).

Kerumitan Angkasa - O(n) kerana vektor menyimpan istilah binomial.

Kesimpulan

Ringkasnya, untuk mencari istilah binomial pengembangan binomial, kita boleh menggunakan salah satu daripada dua kaedah yang dinyatakan di atas, kerumitan masa berjulat dari O(2^n) hingga O(n^2), di mana kaedah lelaran adalah lebih baik. daripada kaedah rekursif Lebih dioptimumkan.

Atas ialah kandungan terperinci Tulis program untuk mencetak siri pengembangan binomial. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!