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.
Diberi tiga integer a, b dan n. Cari sebutan pengembangan binomial bagi (a+b)^n.
Masuk -
a = 1, b = 2, n = 3
Output -
[1, 6, 12, 8]
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.
Masuk -
a = 7, b = 2, n = 11
Output -
[2401, 2744, 1176, 224, 16]
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.
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
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; }
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).
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.
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
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; }
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.
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!