Polynomialception

22

Учитывая два многочлена f,gпроизвольной степени по целым числам, ваша программа / функция должна вычислять первый многочлен во втором многочлене. f(g(x))(он же композиция (fog)(x) двух полиномов)

Детали

Встроенные разрешены. Вы можете принять любое разумное форматирование в качестве ввода / вывода, но формат ввода и вывода должен совпадать. Например, форматирование в виде строки

x^2+3x+5

или как список коэффициентов:

[1,3,5] or alternatively [5,3,1]

Кроме того, можно предположить, что входные полиномы полностью расширены, а выходные данные также должны быть полностью расширены.

Примеры

A(x) = x^2 + 3x + 5, B(y) = y+1
A(B(y)) = (y+1)^2 + 3(y+1) + 5 = y^2 + 5y + 9

A(x) = x^6 + x^2 + 1, B(y) = y^2 - y
A(B(y))= y^12 - 6y^11 + 15y^10 - 20y^9 + 15y^8 - 6y^7 + y^6 + y^4 - 2 y^3 + y^2 + 1

A(x) = 24x^3 - 144x^2 + 288x - 192, B(y) = y + 2
A(B(y)) = 24y^3

A(x) = 3x^4 - 36x^3 + 138x^2 - 180x + 27, B(y) = 2y + 3
A(B(y)) = 48y^4 - 96y^2
flawr
источник
как насчет встроенных?
Maltysen
1
@Maltysen "Подробности: встроенные функции разрешены. (...)" : D
flawr
2
Я думаю, что «любой разумный формат» может быть немного растягиваемым. Если разрешена функция, которая оценивает полином, то композиционная функция (.)является ответом в Haskell. Вы, вероятно, имеете в виду некоторое представление списка коэффициентов.
xnor
1
Название! Я только что получил :-D
Луис Мендо
2
@LuisMendo Быстрый мыслитель = P
flawr

Ответы:

10

Haskell, 86 72 байта

u!c=foldr1((.u).zipWith(+).(++[0,0..])).map c
o g=(0:)!((<$>g).(*))!pure

Определяет функцию o, которая o g fвычисляет композицию f ∘ g. Полиномы представлены непустым списком коэффициентов, начиная с постоянного члена.

демонстрация

*Main> o [1,1] [5,3,1]
[9,5,1]
*Main> o [0,-1,1] [1,0,1,0,0,0,1]
[1,0,1,-2,1,0,1,-6,15,-20,15,-6,1]
*Main> o [2,1] [-192,288,-144,24]
[0,0,0,24]
*Main> o [3,2] [27,-180,138,-36,3]
[0,0,-96,0,48]

Как это работает

Нет встроенных полиномов встроенных или библиотек. Соблюдайте подобные повторения

f (x) = a + f₁ (x) x ⇒ f (x) g (x) = ag (x) + f₁ (x) g (x) x,
f (x) = a + f₁ (x) x ⇒ f (g (x)) = a + f₁ (g (x)) g (x),

для полиномиального умножения и композиции соответственно. Они оба принимают форму

f (x) = a + f₁ (x) x ⇒ W (f) (x) = C (a) (x) + U (W (f₁)) (x).

Оператор !решает повторение этой формы для W, заданного U и C, используя zipWith(+).(++[0,0..])полиномиальное сложение (при условии, что второй аргумент длиннее - для наших целей, он всегда будет). Затем,

(0:)умножает аргумент полинома на x (добавляя нулевой коэффициент);
(<$>g).(*)умножает скалярный аргумент на многочлен g;
(0:)!((<$>g).(*))умножает аргумент полинома на полином g;
pureподнимает скалярный аргумент до постоянного многочлена (одноэлементный список);
(0:)!((<$>g).(*))!pureсоставляет полиномиальный аргумент с полиномом g.

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

Mathematica, 17 байт

Expand[#/.x->#2]&

Пример использования:

In[17]:= Expand[#/.x->#2]& [27 - 180x + 138x^2 - 36x^3 + 3x^4, 3 + 2x]

              2       4
Out[17]= -96 x  + 48 x
feersum
источник
7

TI-Basic 68k, 12 байтов

a|x=b→f(a,b)

Использование простое, например, для первого примера:

f(x^2+3x+5,y+1)

Который возвращается

y^2+5y+9
flawr
источник
Мне кажется, что измена требует, чтобы входные данные были в разных переменных. Имеет ли это значение для этого ответа?
feersum
Не стесняйтесь, я явно разрешил любой разумный удобный формат ввода.
flawr
По поводу редактирования вашего комментария: да, это имеет значение.
flawr
Я не слишком знаком с правилами на этом сайте. Правильно ли быть 1 байтом в TI-BASIC?
asmeurer
@asmeurer Действительно: TI-Basic оценивается кодировкой, используемой в соответствующих калькуляторах. Если вы заинтересованы в деталях, вы можете прочитать это здесь, на мета . Таблицу токенов можно найти здесь на ti-basic-dev .
flawr
6

Python 2, 138 156 162 байта

Предполагается, что входными данными будут целочисленные списки с наименьшими полномочиями.

def c(a,b):
 g=lambda p,q:q>[]and q[0]+p*g(p,q[1:]);B=99**len(`a+b`);s=g(g(B,b),a);o=[]
 while s:o+=(s+B/2)%B-B/2,;s=(s-o[-1])/B
 return o

Ungolfed:

def c(a,b):
 B=sum(map(abs,a+b))**len(a+b)**2
 w=sum(B**i*x for i,x in enumerate(b))
 s=sum(w**i*x for i,x in enumerate(a))
 o=[]
 while s:o+=min(s%B,s%B-B,key=abs),; s=(s-o[-1])/B
 return o

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

-18 от улучшения связанного, Bкак предложено @xnor.

feersum
источник
Хороший метод. Ибо Bбудет 10**len(`a+b`)достаточно?
xnor
@xnor Может быть ... мне трудно сказать.
feersum
+1 Это действительно креативное решение и хорошее использование bigints !!!
flawr
@xnor Теперь мне удалось убедить себя, что длина коэффициента линейна во входной длине :)
feersum
5

Python + SymPy, 59 35 байт

from sympy import*
var('x')
compose

Спасибо @asmeurer за то, что вы играете в гольф на 24 байта!

Тестовый забег

>>> from sympy import*
>>> var('x')
x
>>> f = compose
>>> f(x**2 + 3*x + 5, x + 1)
x**2 + 5*x + 9
Деннис
источник
1
SymPy имеет compose()функцию.
asmeurer
1
Где ответ? Он больше не определяет какие-либо функции и ничего не делает ...
feersum
1
@feersum Такого никогда не было. Вы только что отредактировали этот мета-пост.
Mego
3
@feersum Вы отредактировали принятую мета-публикацию, чтобы изменить политику для своей собственной повестки дня. Это не хорошо.
Мего
3
@feersum Хотя вы, возможно, думали, что ваша формулировка была неоднозначной, она явно была не для остальной части сообщества. Мы приняли консенсус, который from module import*;functionбыл действительным представлением. Несмотря на это , это более новая политика, которая разрешает импорт и вспомогательные функции с безымянными лямбдами.
Mego
3

Sage, 24 байта

lambda A,B:A(B).expand()

Начиная с Sage 6.9 (версия, которая работает на http://sagecell.sagemath.org ), вызовы функций без явного присвоения аргумента ( f(2) rather than f(x=2)) приводят к тому, что на STDERR выводится раздражающее и бесполезное сообщение. Поскольку STDERR можно игнорировать по умолчанию в коде гольф, это все еще действует.

Это очень похоже на ответ Денниса на SymPy, потому что Sage a) построен на Python и b) использует Maxima , систему компьютерной алгебры, очень похожую на SymPy во многих отношениях. Тем не менее, Sage намного мощнее, чем Python с SymPy, и, следовательно, является достаточно другим языком, поэтому заслуживает своего собственного ответа.

Проверьте все тестовые примеры онлайн

Mego
источник
2

PARI / GP , 19 байт

(a,b)->subst(a,x,b)

что позволяет вам делать

%(x^2+1,x^2+x-1)

получить

% 2 = x ^ 4 + 2 * x ^ 3 - x ^ 2 - 2 * x + 2

Чарльз
источник
1

MATLAB с набором символов, 28 байтов

@(f,g)collect(subs(f,'x',g))

Это анонимная функция. Чтобы вызвать его, назначьте его переменной или используйте ans. Входные данные - это строки в формате (пробелы необязательны)

x^2 + 3*x + 5

Пример выполнения:

>> @(f,g)collect(subs(f,'x',g))
ans = 
    @(f,g)collect(subs(f,'x',g))
>> ans('3*x^4 - 36*x^3 + 138*x^2 - 180*x + 27','2*x + 3')
ans =
48*x^4 - 96*x^2
Луис Мендо
источник
1

Python 2, 239 232 223 байта

r=range
e=reduce
a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
m=lambda p,q:[sum((p+k*[0])[i]*(q+k*[0])[k-i]for i in r(k+1))for k in r(len(p+q)-1)]
o=lambda f,g:e(a,[e(m,[[c]]+[g]*k)for k,c in enumerate(f)])

«Правильная» реализация, которая не злоупотребляет основами. Наименее значимый коэффициент в первую очередь.

aявляется полиномиальным сложением, mявляется полиномиальным умножением и oявляется композицией.

orlp
источник
Разве m([c],e(m,[[1]]+[g]*k))не так же, как e(m,[[c]]+[g]*k)?
Нил
@Neil Хороший звонок, может раздавить два в одном с этим!
orlp
a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
Андерс Касеорг
@AndersKaseorg Правильно, я добавил это, спасибо :)
orlp
Возможно, можно упростить сложение полиномов, так как я думаю, что один список всегда будет длиннее другого, поэтому вам не нужно использовать его ( or 0)в этой версии.
Нил
1

JavaScript (ES6), 150 103 байта

(f,g)=>f.map(n=>r=p.map((m,i)=>(g.map((n,j)=>p[j+=i]=m*n+(p[j]||0)),m*n+(r[i]||0)),p=[]),r=[],p=[1])&&r

Принимает и возвращает полиномы в виде массива a = [a 0 , a 1 , a 2 , ...], который представляет 0 + a 1 * x + a 2 * x 2 ...

Изменить: 47 байтов сохранены путем переключения с рекурсивного на итеративное полиномиальное умножение, что позволило мне объединить два map вызова.

Объяснение: r - это результат, который начинается с нуля, представленный пустым массивом, а p - это g h , который начинается с единицы. p умножается на каждый f h по очереди, а результат накапливается в r . p также умножается на g одновременно.

(f,g)=>f.map(n=>            Loop through each term of f (n = f[h])
 r=p.map((m,i)=>(           Loop through each term of p (m = p[i])
  g.map((n,j)=>             Loop though each term of g (n = g[j])
   p[j+=i]=m*n+(p[j]||0)),  Accumulate p*g in p
  m*n+(r[i]||0)),           Meanwhile add p[i]*f[h] to r[i]
  p=[]),                    Reset p to 0 each loop to calculate p*g
 r=[],                      Initialise r to 0
 p=[1]                      Initialise p to 1
)&&r                        Return the result
Нил
источник
1

Pyth, 51 34 байта

AQsM.t*LVG.usM.t.e+*]0k*LbHN0tG]1Z

Тестовый пакет .

Дрянная Монахиня
источник
2
когда питон превосходит питфа
downrep_nation
@downrep_nation больше нет :)
Утренняя монахиня
1

Рубин 2.4 + полином , 41 + 12 = 53 байта

Использует флаг -rpolynomial. Ввод двух Polynomialобъектов.

Если кто-то превзойдет меня в ванильном Ruby (без полиномиальной внешней библиотеки), я буду очень впечатлен.

->a,b{i=-1;a.coefs.map{|c|c*b**i+=1}.sum}
Значение чернил
источник