Jika kita menulis urutan angka sebagai koefisien dari seri daya, maka seri daya itu disebut fungsi penghasil (atau Gf) dari urutan tersebut. Artinya, jika untuk beberapa fungsi F(x)dan serangkaian bilangan bulat yang a(n)kita miliki:

a(0) + a(1)x + a(2)x^2 + a(3)x^3 + a(4)x^4 + ... = F(x)

Kemudian F(x)adalah fungsi menghasilkan a. Misalnya, deret geometri memberi tahu kita bahwa:

1 + x + x^2 + x^3 + x^4 + ... = 1/(1-x)

Jadi fungsi pembangkitnya 1, 1, 1, ...adalah 1/(1-x). Jika kita membedakan kedua sisi persamaan di atas dan mengalikannya dengan xkita mendapatkan persamaan berikut:

x + 2x^2 + 3x^3 + 4x^4 + ... = x/(1-x)^2

Jadi fungsi pembangkitnya 1, 2, 3, ...adalah x/(1-x)^2. Menghasilkan fungsi adalah alat yang sangat kuat, dan Anda dapat melakukan banyak hal berguna dengannya. Pengantar singkat dapat ditemukan di sini , tetapi untuk penjelasan yang sangat menyeluruh ada fungsi buku yang menakjubkan.

Dalam tantangan ini, Anda akan mengambil fungsi rasional (hasil bagi dari dua polinomial dengan koefisien integer) sebagai input sebagai dua array koefisien integer, pertama pembilang kemudian penyebut. Misalnya fungsi f(x) = x / (1 - x - x^2)akan dikodekan seperti [0, 1], [1, -1, -1]pada input.

Dengan masukan ini, program Anda harus mencetak koefisien seri daya tanpa batas yang sama dengan fungsi pembangkit, satu per baris, mulai dari koefisien x, kemudian x^2, dll.

Contoh:

[1], [1, -1] -> 1, 1, 1, 1, 1, 1, 1, ...
[1], [2, -2] -> 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, ...
[0, 1], [1, -2, 1] -> 1, 2, 3, 4, 5, 6, 7, 8, ...
[0, 1], [1, -1, -1] -> 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
[1], [1, -2] -> 1, 2, 4, 8, 16, 32, 64, 128, ...
[0, 1, 1], [1, -3, 3, -1] -> 1, 4, 9, 16, 25, 36, ...

Haskell , 63 byte

z=0:z
(a:b)%y@(c:d)=a/c:zipWith(-)(b++z)(map(a/c*)d++z)%y
_%_=z

Cobalah online!

Menentukan operator yang %mengembalikan daftar koefisien malas yang tak terbatas. Daftar ini diindeks nol, sehingga koefisien konstan disertakan.

Mathematica, 64 83 90 byte

Do[Echo@Limit[D[#/#2/i!&@@Fold[x#+#2&]/@#,{x,i}],x->0],{i,∞}‌​]&

Terima kasih kepada @ngenisis dan @Jenny_mathy!

Ambil input sebagai dua daftar.

Perlu Alt+.mengakhiri eksekusi untuk melihat hasilnya. Frontend mungkin macet karena output yang cepat.

Versi 83 byte (@Jenny_mathy):

i=1;v=Tr[#*x^Range@Length@#]&;While[1<2,Echo@Limit[D[v@#/v@#2/i!,{x,i}],x->0];i++]&

CJam (22 byte)

{\{(W$(@\/_pW*f*.+1}g}

Demo online . Perhatikan bahwa karena banyak jawaban yang ada, ini termasuk koefisien 0 dalam output.

Pembedahan

{           e# Define a block which takes numerator N and denominator D as arguments
  \         e# Flip to put D at the bottom, since that won't change
  {         e# Infinite loop:
    (       e#   Pop the first element of (the modified) N
    W$(     e#   Copy D and pop its first element
            e#   Stack: D N[1:] N[0] D[1:] D[0]
    @\/     e#   Bring N[0] to top, flip, divide
            e#   Stack: D N[1:] D[1:] N[0]/D[0]
    _p      e#   Print a copy
    W*f*.+  e#   Multiply by -1, multiply all, pointwise add
            e#   Stack: D N[1:]-(N[0]/D[0])*D[1:]
  1}g
}

Mathematica, 86 79 byte

f=x^Range@Length@#.#&;For[n=1,8>3,Print@SeriesCoefficient[f@#/f@#2,{x,0,n++}]]&

Mengambil input sebagai dua daftar terpisah (koefisien pembilang, koefisien penyebut). Jika input dapat diambil secara langsung sebagai fraksi dari polinomial daripada sebagai daftar koefisien, ini dapat dipersingkat secara signifikan.

Tampaknya Dobisa bekerja dengan batas tak terbatas di v11. Saya tidak dapat menguji ini secara lokal, tetapi, jika ini masalahnya, maka solusi ini dapat dipersingkat menjadi 75 byte :

f=x^Range@Length@#.#&;Do[Print@SeriesCoefficient[f@#/f@#2,{x,0,n}],{n,∞}]&

Pyth , 23 byte

JE#
KchQhJ=t-M.t,Q*LKJ0

Cobalah online!

Bagaimana itu bekerja

                       Q = eval(input())
JE                     J = eval(input())
  #                    infinite loop:
 chQhJ                   Q[0]/J[0]
K                        assign that to K (and print it, because of the preceding newline)
              *LKJ       K times every element of J
            ,Q           [Q, that]
          .t      0      transpose, padding with 0s
        -M               subtract each pair
       t                 remove the first element
      =                  assign that back to Q

Pari / GP , 66 byte

p->q->for(i=0,oo,print(Pol(Polrev(p)/(Polrev(q)+O(x*x^i)))\x^i%x))

Cobalah online!