有理生成関数の係数を求める

べき級数の係数として一連の数値を書くと、その級数はそのシーケンスの(普通の)生成関数(またはG.f.)と呼ばれます。つまり、ある関数
F(x)と一連の整数 a(n)に対して、

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

次に F(x)a の生成関数です。たとえば、幾何学的なシリーズでは、次のことがわかります。

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

したがって、 1、1、1、... の生成関数は 1
/(1-x)
です。上の方程式の両辺を区別し、 x で掛けると、次の等式が得られます。

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

したがって、 1,2,3、... の生成関数は x /(1-x)^ 2
です。生成関数は非常に強力なツールであり、多くの有用なことをそれらの関数で行うことができます。簡単な紹介は、ここにはありますが、本当に徹底的な説明のために、素晴らしい本を生み出す機能があります。


この課題では、

有理関数(整数係数を持つ2つの多項式の商)を整数係数の2つの配列として入力します。最初は分子、次に分母です。例えば、関数
f(x)= x /(1-x-x ^ 2)[0、1]、[1、-1、-1]
を入力します。

この入力が与えられると、プログラムは、 x の係数から始めて x ^ 2
の係数から始めて、生成関数に等しい冪級数の係数を無限に印刷しなければなりません。等


例:

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

z=0:z
(a:b)%[email protected](c:d)=a/c:zipWith(-)(b++z)(map(a/c*)d++z)%y
_%_=z

Try it
online!

無限の遅延リストを返す演算子を定義します。リストはゼロインデックスであるため、定数係数が含まれます。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です