Jeśli napiszemy sekwencję liczb jako współczynniki szeregu mocy, wówczas ta seria mocy nazywana jest (zwykłą) funkcją generującą (lub Gf) tej sekwencji. To znaczy, jeśli dla niektórych funkcji F(x)i serii liczb całkowitych a(n)mamy:

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

Następnie F(x)jest funkcja generowania a. Na przykład szereg geometryczny mówi nam, że:

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

Więc funkcja generująca 1, 1, 1, ...to 1/(1-x). Jeśli rozróżnimy obie strony powyższego równania i pomnożymy przez xto otrzymamy następującą równość:

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

Więc funkcja generująca 1, 2, 3, ...to x/(1-x)^2. Generowanie funkcji jest bardzo potężnym narzędziem i można z nimi zrobić wiele przydatnych rzeczy. Krótkie wprowadzenie można znaleźć tutaj , ale dla naprawdę dokładnego wyjaśnienia istnieje niesamowita funkcjonalność generowania książek.

W tym wyzwaniu weźmiesz funkcję racjonalną (iloraz dwóch wielomianów ze współczynnikami całkowitymi) jako dane wejściowe jako dwie tablice współczynników całkowitych, najpierw licznik, a następnie mianownik. Na przykład funkcja f(x) = x / (1 - x - x^2)zostanie zakodowana jak [0, 1], [1, -1, -1]na wejściu.

Biorąc pod uwagę te dane wejściowe, twój program musi nieskończenie drukować współczynniki szeregu mocy, które są równe funkcji generowania, jeden na linię, zaczynając od współczynnika x, a następnie x^2itd.

Przykłady:

[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 bajty

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

Wypróbuj online!

Definiuje operator %zwracający nieskończoną leniwą listę współczynników. Lista jest indeksowana od zera, więc uwzględniono stały współczynnik.

Mathematica, 64 83 90 bajty

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

Dzięki @ngenisis i @Jenny_mathy!

Weź dane jako dwie listy.

Musisz Alt+.zakończyć wykonywanie, aby zobaczyć wynik. Frontend może ulec awarii z powodu szybkiego wyjścia.

Wersja 83 bajtów (@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 bajty)

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

Demo online . Zauważ, że jak wiele istniejących odpowiedzi, obejmuje to 0-ty współczynnik na wyjściu.

Sekcja

{           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 bajtów

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

Pobiera dane wejściowe jako dwie osobne listy (współczynniki licznika, współczynniki mianownika). Jeśli dane wejściowe można przyjąć bezpośrednio jako ułamek wielomianów, a nie jako listy współczynników, można to znacznie skrócić.

Wygląda na to, że Domoże działać z nieograniczonymi granicami w wersji 11. Nie mogę przetestować tego lokalnie, ale jeśli tak jest, to rozwiązanie można skrócić do 75 bajtów :

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

Pyth , 23 bajty

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

Wypróbuj online!

Jak to działa

                       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 bajtów

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

Wypróbuj online!