Trouver les coefficients d'une fonction génératrice rationnelle

12

Si nous écrivons une séquence de nombres comme coefficients d'une série de puissances, alors cette série de puissances est appelée la fonction génératrice (ordinaire) (ou Gf) de cette séquence. Autrement dit, si pour une fonction F(x)et une série d'entiers, a(n)nous avons:

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

Alors F(x)est la fonction génératrice de a. Par exemple, la série géométrique nous dit que:

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

Ainsi, la fonction génératrice de 1, 1, 1, ...est 1/(1-x). Si nous différencions les deux côtés de l'équation ci-dessus et multiplions par, xnous obtenons l'égalité suivante:

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

Ainsi, la fonction génératrice de 1, 2, 3, ...est x/(1-x)^2. La génération de fonctions est un outil très puissant et vous pouvez faire beaucoup de choses utiles avec elles. Une brève introduction peut être trouvée ici , mais pour une explication vraiment approfondie, il y a l'étonnant livre générant une fonctionnalité.


Dans ce défi, vous prendrez une fonction rationnelle (le quotient de deux polynômes avec des coefficients entiers) comme entrée comme deux tableaux de coefficients entiers, d'abord le numérateur puis le dénominateur. Par exemple, la fonction f(x) = x / (1 - x - x^2)sera codée comme [0, 1], [1, -1, -1]dans l'entrée.

Compte tenu de cette entrée, votre programme doit imprimer à l'infini les coefficients de la série de puissance égale à la fonction de génération, un par ligne, en commençant par le coefficient de x, puis x^2, etc.


Exemples:

[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
la source
Merde, mon langage est conçu pour les séquences, mais je ne peux pas vraiment faire d'entrée de tableau multidimensionnel :(
Stephen
2
Je ne suis vraiment pas assez soucieux des mathématiques pour cette spécification, avez-vous une chance que vous puissiez poster plus d'explications d'un profane pour nous, gens du commun?
Skidsdev
2
Copie
1
@trichoplax Cela force toujours le numérateur à 1, ce qui n'est pas le même. Par exemple, il ne peut pas exprimer mon dernier exemple, les carrés.
orlp
1
Une autre façon de formuler cela est d'évaluer une récurrence linéaire générale. De cette façon, il généralise cette question et pourrait servir de dupe pour les futures questions de récurrence.
Peter Taylor

Réponses:

7

Haskell , 63 octets

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

Essayez-le en ligne!

Définit un opérateur %renvoyant une liste de coefficients paresseux infinie. La liste est indexée zéro, donc le coefficient constant est inclus.

Anders Kaseorg
la source
3

Mathematica, 64 83 90 octets

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

Merci à @ngenisis et @Jenny_mathy!

Prenez la saisie comme deux listes.

Besoin Alt+.de terminer l'exécution pour voir le résultat. Le frontend peut se bloquer en raison d'une sortie rapide.

Version 83 octets (@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
la source
83 octets: i = 1; v = Tr [# * x ^ Range @ Length @ #] &; Alors que [1 <2, Echo @ Limit [D [v @ # / v @ # 2 / i !, {x, i}], x -> 0]; i ++] &
J42161217
@Jenny_mathy Désolé d'avoir dérangé. Je me rends compte qu'il y a des caractères Unicode indésirables indésirables dans votre premier commentaire. Une fois nettoyé, le code est OK.
Keyu Gan
3
64octets: Do[Echo@Limit[D[#/#2/i!&@@Fold[x#+#2&]/@#,{x,i}],x->0],{i,∞}]&. Cela suppose que l'entrée est une liste de deux listes et que les coefficients sont dans l'ordre décroissant. Le seul intégré que je connaisse pour faire ce vqui est estInternal`FromCoefficientList
ngenisis
Est-ce que cela fonctionne à plusieurs reprises? Je pense que quelques parenthèses supplémentaires pourraient être nécessaires pour mettre ià l'intérieur du lambda. (D'un autre côté, je ne suis pas vraiment sûr de savoir si la capacité à courir à plusieurs reprises est pertinente lorsque le but est d'imprimer une liste infinie ... y a-t-il eu un méta-consensus à ce sujet?)
Julian Wolf
@ngenisis: Quelle version utilisez-vous? Sur v10.0, votre solution me donne Iterator {i,∞} does not have appropriate bounds.
Julian Wolf
1

CJam (22 octets)

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

Démo en ligne . Notez que comme beaucoup des réponses existantes, cela inclut le 0e coefficient dans la sortie.

Dissection

{           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
la source
0

Mathematica, 86 79 octets

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

Prend la saisie sous forme de deux listes distinctes (coefficients du numérateur, coefficients du dénominateur). Si l'entrée peut être prise directement comme une fraction de polynômes plutôt que comme des listes de coefficients, cela peut être considérablement raccourci.

Il semble que cela Dopuisse fonctionner avec des limites infinies dans la v11. Je ne peux pas tester cela localement, mais si c'est le cas, cette solution peut être raccourcie à 75 octets :

f=x^Range@Length@#.#&;Do[Print@SeriesCoefficient[f@#/f@#2,{x,0,n}],{n,∞}]&
Julian Wolf
la source
le dernier
scénario de
@Jenny_mathy: shoot, merci pour la tête. On dirait que les cas de test s’attendent à partir du premier à la place du zéro… je suis sûr que cela devrait me permettre d’économiser quelques octets.
Julian Wolf
@Jenny_mathy: Je pense que les cas de test pourraient être loufoques. À partir nde 1 au lieu de 0, cela donne les mêmes résultats que votre solution; les deux échouent, cependant, sur l'avant-dernier cas de test, que cette solution réussit lors du démarrage nà partir de 0.
Julian Wolf
0

Pyth , 23 octets

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

Essayez-le en ligne!

Comment ça fonctionne

                       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
la source