Znajdź współczynniki racjonalnej funkcji generującej

12

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, ...
orlp
źródło
Cholera, mój język jest zbudowany na takie sekwencje, ale tak naprawdę nie mogę wykonywać wielowymiarowych danych tablicowych :(
Stephen
2
Tak naprawdę nie jestem wystarczająco matematycznie nastawiony do tej specyfikacji, czy jest szansa, że ​​możesz opublikować więcej wyjaśnień laika dla nas, zwykłych ludzi?
Skidsdev
2
Możliwa duplikat obliczenia współczynników
szeregu
1
@trichoplax To zawsze wymusza licznik na 1, co nie jest takie samo. Na przykład nie może wyrazić mojego ostatniego przykładu, kwadratów.
orlp
1
Alternatywnym sposobem sformułowania tego jest ocena ogólnej powtarzalności liniowej. W ten sposób uogólnia to pytanie i może służyć jako cel dupe w przyszłych pytaniach dotyczących powtarzania się.
Peter Taylor,

Odpowiedzi:

7

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.

Anders Kaseorg
źródło
3

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++]&
Keyu Gan
źródło
83 bajty: i = 1; v = Tr [# * x ^ Range @ Length @ #] &; Podczas gdy [1 <2, Echo @ Limit [D [v @ # / v @ # 2 / i !, {x, i}], x -> 0]; i ++] i
J42161217,
@Jenny_mathy Przepraszam, że przeszkadzam. Rozumiem, że w twoim pierwszym komentarzu jest kilka niewidzialnych znaków Unicode. Po wyczyszczeniu kod jest OK.
Keyu Gan,
3
64bajtów: Do[Echo@Limit[D[#/#2/i!&@@Fold[x#+#2&]/@#,{x,i}],x->0],{i,∞}]&. Zakłada się, że dane wejściowe są listą dwóch list, a współczynniki są uporządkowane w kolejności malejącej. Jedyne, co wiem, żeby robić to, co vrobi, toInternal`FromCoefficientList
ngenisis,
Czy uruchamianie tego wielokrotnie działa? Myślę, że kilka dodatkowych nawiasów może być potrzebnych do umieszczenia iw lambda. (Z drugiej strony nie jestem do końca pewien, czy zdolność do wielokrotnego biegania jest istotna, gdy celem jest wydrukowanie nieskończonej listy ... czy w tej sprawie osiągnięto meta konsensus?)
Julian Wolf
@ngenisis: jakiej wersji używasz? W wersji 10.0 twoje rozwiązanie mi to daje Iterator {i,∞} does not have appropriate bounds.
Julian Wolf
1

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
}
Peter Taylor
źródło
0

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,∞}]&
Julian Wolf
źródło
ostatni przypadek testowy nie zaczyna się od 0.
J42161217,
@Jenny_mathy: strzelaj, dzięki za heads up. Wygląda na to, że przypadki testowe oczekują, że zaczną się od zera zamiast zera… jestem pewien, że to pozwoli mi zaoszczędzić kilka bajtów.
Julian Wolf
@Jenny_mathy: Myślę, że przypadki testowe mogą być dziwne. Począwszy nod 1 zamiast 0, daje to takie same wyniki jak rozwiązanie; oba kończą się niepowodzeniem w drugim do ostatniego przypadku testowym, który to rozwiązanie przechodzi, gdy zaczyna się nod 0.
Julian Wolf
0

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
Anders Kaseorg
źródło
0

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!

alephalpha
źródło