Hitung Koefisien Seri Daya

24

Diberikan polinomial p(x)dengan koefisien integral dan istilah konstan p(0) = 1 or -1, dan bilangan bulat non-negatif N, kembalikan Nkoefisien ke-20 dari seris daya (kadang-kadang disebut "deret Taylor") f(x) = 1/p(x)dikembangkan pada x0 = 0, yaitu koefisien monomial derajat N.

Kondisi yang diberikan memastikan bahwa seri daya ada dan bahwa koefisiennya adalah bilangan bulat.

Detail

Seperti biasa, polinom dapat diterima dalam format apa pun yang nyaman, misalnya daftar koefisien, misalnya p(x) = x^3-2x+5dapat direpresentasikan sebagai [1,0,-2,5].

Powereries dari fungsi yang fdikembangkan di 0diberikan oleh

dan Nkoefisien -th (koefisien x^N) diberikan oleh

di mana menunjukkan nturunan ke-10 darif

Contohnya

  • Hasil polinomial p(x) = 1-xdalam deret geometri f(x) = 1 + x + x^2 + ...sehingga output harus 1untuk semua N.

  • p(x) = (1-x)^2 = x^2 - 2x + 1menghasilkan turunan dari deret geometri f(x) = 1 + 2x + 3x^2 + 4x^3 + ..., sehingga output untuk Nadalah N+1.

  • p(x) = 1 - x - x^2 menghasilkan fungsi penghasil urutan Fibonacci f(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + 13x^6 + ...

  • p(x) = 1 - x^2menghasilkan fungsi menghasilkan 1,0,1,0,...yaituf(x) = 1 + x^2 + x^4 + x^6 + ...

  • p(x) = (1 - x)^3 = 1 -3x + 3x^2 - x^3menghasilkan fungsi menghasilkan angka segitiga f(x) = 1 + 3x + 6x^6 + 10x^3 + 15x^4 + 21x^5 + ...yang berarti Nkoefisien -th adalah koefisien binomial(N+2, N)

  • p(x) = (x - 3)^2 + (x - 2)^3 = 1 + 6x - 5x^2 + x^3 hasil dalam f(x) = 1 - 6x + 41x^2 - 277x^3 + 1873x4 - 12664x^5 + 85626x^6 - 57849x^7 + ...

cacat
sumber
Apakah dapat diterima untuk mengambil polinomial sebagai daftar koefisien deret daya tak terbatas seperti [1,-1,0,0,0,0,...]?
xnor
Ya, saya pikir ini adalah format yang dapat diterima.
flawr
Contoh bagus dipilih!
Greg Martin
Saya senang Anda menghargainya, terima kasih =)
flawr

Jawaban:

9

Mathematica, 24 23 byte

Disimpan 1 byte berkat Greg Martin

D[1/#2,{x,#}]/#!/.x->0&

Fungsi murni dengan dua argumen #dan #2. Diasumsikan polinom #2memenuhi PolynomialQ[#2,x]. Tentu saja ada built-in untuk ini:

SeriesCoefficient[1/#2,{x,0,#}]&
ngenisis
sumber
1
Bagus mengalahkan built-in! Saya kira Anda dapat menyimpan byte dengan menganggap itu #adalah bilangan bulat Ndan #2polinomial.
Greg Martin
6

Matlab, 81 79 75 byte

Berbeda dengan dua jawaban sebelumnya, ini tidak menggunakan perhitungan simbolik. Idenya adalah Anda dapat menghitung koefisien secara iteratif:

function C=f(p,N);s=p(end);for k=1:N;q=conv(p,s);s=[-q(end-k),s];end;C=s(1)

Cobalah online!

Penjelasan

function C=f(p,N);
s=p(end);            % get the first (constant coefficient)
for k=1:N;           
    q=conv(p,s);     % multiply the known coefficients with the polynomial
    s=[-q(end-k),s]; % determine the new coefficient to make the the product get "closer" 
end;
C=s(1)           % output the N-th coefficient
cacat
sumber
4

GeoGebra , 28 byte

Derivative[1/A1,B1]/B1!
f(0)

Input diambil dari sel spreadsheet A1 dan B1 masing-masing dari polinomial dan integer, dan setiap baris dimasukkan secara terpisah ke dalam bilah input. Output adalah melalui penugasan ke variabel a.

Berikut adalah gif yang menunjukkan eksekusi:

Koefisien Taylor

Menggunakan builtin jauh lebih lama, pada 48 byte:

First[Coefficients[TaylorPolynomial[1/A1,0,B1]]]
TheBikingViking
sumber
4

Haskell, 44 byte

p%n=(0^n-sum[p!!i*p%(n-i)|i<-[1..n]])/head p

Perhitungan langsung tanpa built-in aljabar. Mengambil input sebagai daftar koefisien deret daya tak terbatas, seperti p = [1,-2,3,0,0,0,0...](yaitu p = [1,-2,3] ++ repeat 0) untuk 1-2*x+x^2. Sebut saja seperti p%3, yang memberi -4.0.

Idenya adalah jika p adalah polinomial dan q = 1 / p itu terbalik, maka kita dapat mengekspresikan kesetaraan p · q = 1 istilah per kata. Koefisien x n dalam p · q diberikan oleh konvolusi koefisien dalam p dan q :

p 0 · q n + p 1 · q n-1 + ... + p n · q 0

Agar p · q = 1 bertahan, di atas harus sama dengan nol untuk semua n> 0 . Untuk di sini, kita dapat mengekspresikan q n secara rekursif dalam hal q 0 , ..., q n-1 dan koefisien p .

q n = - 1 / p 0 · (p 1 · q n-1 + ... + p n · q 0 )

Ini persis apa yang dihitung dalam ekspresi sum[p!!i*p%(n-i)|i<-[1..n]]/head p, dengan head pkoefisien terkemuka p 0 . Koefisien awal q 0 = 1 / p 0 ditangani secara hitung dalam ekspresi yang sama menggunakan 0^nsebagai indikator untuk n==0.

Tidak
sumber
3

J, 12 byte

1 :'(1%u)t.'

Menggunakan kata keterangan t.yang mengambil polinomial pdalam bentuk kata kerja pada LHS dan bilangan bulat negatif kpada RHS dan menghitung koefisien kth dari seri Taylor pat x = 0. Untuk mendapatkan seri daya, timbal balik pdiambil sebelum menerapkannya.

Cobalah online!

mil
sumber
2

Maple, 58 26 byte

Ini adalah fungsi tanpa nama yang menerima polinomial dalam xdan bilangan bulat N.

EDIT: Saya baru memperhatikan bahwa ada builtin:

(p,N)->coeftayl(1/p,x=0,N)
cacat
sumber
1

MATL , 19 byte

0)i:"1GY+@_)_8Mh]1)

Terjemahan dari jawaban Matlab @ flawr yang luar biasa .

Cobalah online!

Bagaimana itu bekerja

0)      % Implicitly input vector of polynomial coefficients and get last entry
i       % Input N
:"      % For k in [1 2 ... N]
  1G    %   Push vector of polynomial coefficients
  Y+    %   Convolution, full size
  @     %   Push k
  _     %   Negate
  )     %   Index. This produces the end-k coefficient
  _     %   Negate
  8M    %   Push first input of the latest convolution
  h     %   Concatenate horizontally
]       % End
1)      % Get first entry. Implicitly display
Luis Mendo
sumber
1

JavaScript (ES6), 57 byte

(a,n)=>a.reduce((s,p,i)=>!i|i>n?s:s-p*f(a,n-i),!n)/a[0]

Port of @ xnor's jawaban Haskell. Saya awalnya mencoba versi berulang tetapi ternyata menjadi 98 byte, namun akan jauh lebih cepat untuk N besar, karena saya secara efektif memoising panggilan rekursif:

(a,n)=>[...Array(n+1)].fill(0).map((_,i,r)=>r[i]=r.reduce((s,p,j)=>s-p*(a[i-j]||0),!i)/a[0]).pop()

n+1persyaratan diperlukan, yang disimpan dalam array r. Ini awalnya nol yang memungkinkan pengurangan seluruh array rsekaligus, karena nol tidak akan mempengaruhi hasilnya. Koefisien perhitungan terakhir adalah hasil akhir.

Neil
sumber
1

PARI / GP, 31 27 byte

f->n->Pol(Ser(1/f,,n+1))\x^n
alephalpha
sumber