Найти коэффициенты рациональной производящей функции

12

Если мы запишем последовательность чисел в качестве коэффициентов степенного ряда, то этот степенной ряд называется (обычной) производящей функцией (или Gf) этой последовательности. То есть если для некоторой функции 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. Генерация функций - очень мощный инструмент, и вы можете делать с ним много полезных вещей. Краткое введение можно найти здесь , но для действительно подробного объяснения есть удивительная книга, создающая функциональность.


В этом задании вы возьмете рациональную функцию (частное от двух полиномов с целыми коэффициентами) в качестве входных данных в виде двух массивов целых коэффициентов, сначала числителя, а затем знаменателя. Например, функция 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, ...
orlp
источник
Дерьмо, мой язык построен для последовательностей, но я не могу на самом деле вводить многомерный массив :(
Стивен
2
На самом деле я просто недостаточно математически настроен для этой спецификации, есть ли шанс, что вы могли бы опубликовать больше объяснений непрофессионала для нас, простых людей?
Скидсдев
2
Возможный дубликат вычисления коэффициентов степенных рядов
трихоплакс
1
@trichoplax Это всегда приводит к тому, что числитель равен 1, что не одно и то же. Например, он не может выразить мой последний пример, квадраты.
orlp
1
Альтернативный способ сформулировать это состоит в том, что он оценивает общую линейную повторяемость. Таким образом, он обобщает этот вопрос и может служить ложной целью для будущих вопросов повторения.
Питер Тейлор

Ответы:

7

Haskell , 63 байта

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

Попробуйте онлайн!

Определяет оператор, %возвращающий бесконечный ленивый список коэффициентов. Список с нулевым индексом, поэтому постоянный коэффициент включен.

Андерс Касеорг
источник
3

Математика, 64 83 90 байтов

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

Благодаря @ngenisis и @Jenny_mathy!

Принять ввод в виде двух списков.

Необходимо Alt+.прекратить выполнение, чтобы увидеть результат. Интерфейс может зависнуть из-за быстрого вывода.

Версия 83 байта (@Jenny_mathy):

i=1;v=Tr[#*x^Range@Length@#]&;While[1<2,Echo@Limit[D[v@#/v@#2/i!,{x,i}],x->0];i++]&
Кейу Ган
источник
83 байта: i = 1; v = Tr [# * x ^ Range @ Length @ #] &; В то время как [1 <2, Echo @ Limit [D [v @ # / v @ # 2 / i !, {x, i}], x -> 0]; я ++] &
J42161217
@Jenny_mathy Извините за беспокойство. Я понял, что в вашем первом комментарии есть несколько невидимых символов Unicode. После очистки код в порядке.
Кейу Ган
3
64байт: Do[Echo@Limit[D[#/#2/i!&@@Fold[x#+#2&]/@#,{x,i}],x->0],{i,∞}]&. Предполагается, что входные данные представляют собой список из двух списков, а коэффициенты расположены в порядке убывания степени. Единственное встроенное устройство, которое я знаю, чтобы делать то, что vделает,Internal`FromCoefficientList
ngenisis
Работает ли это многократно? Я думаю, что пара дополнительных скобок может быть необходимо поместить iв лямбду. (С другой стороны, я не совсем уверен, уместна ли способность многократно бегать, когда цель состоит в том, чтобы напечатать бесконечный список ... был ли мета-консенсус по этому
Джулиан Вольф
@ngenisis: Какую версию вы используете? На v10.0 ваше решение мне дает Iterator {i,∞} does not have appropriate bounds.
Джулиан Вольф
1

CJam (22 байта)

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

Демо онлайн . Обратите внимание, что как и многие из существующих ответов, это включает в себя 0-й коэффициент в выходных данных.

рассечение

{           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
}
Питер Тейлор
источник
0

Mathematica, 86 79 байтов

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

Вводит в виде двух отдельных списков (коэффициенты числителя, коэффициенты знаменателя). Если входные данные могут быть взяты непосредственно как часть многочленов, а не как списки коэффициентов, это может быть значительно сокращено.

Кажется, что Doможет работать с бесконечными границами в v11. Я не могу проверить это локально, но, если это так, то это решение может быть сокращено до 75 байт :

f=x^Range@Length@#.#&;Do[Print@SeriesCoefficient[f@#/f@#2,{x,0,n}],{n,∞}]&
Юлианский волк
источник
последний контрольный пример не начинается с 0.
J42161217
@ Jenny_mathy: стрелять, спасибо за голову. Похоже, что тестовые случаи ожидают, начиная с первого вместо нуля… почти наверняка это должно позволить мне сэкономить несколько байтов.
Джулиан Вольф
@Jenny_mathy: я думаю, что тестовые случаи могут быть неудачными. Начиная nс 1 вместо 0, это дает те же результаты, что и ваше решение; однако оба теста терпят неудачу в последнем тестовом примере, который проходит это решение, начиная nс 0.
Julian Wolf
0

Pyth , 23 байта

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

Попробуйте онлайн!

Как это устроено

                       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
Андерс Касеорг
источник