Dados dois polinômios f,g
de grau arbitrário sobre os números inteiros, seu programa / função deve avaliar o primeiro polinômio no segundo polinômio. f(g(x))
(aka a composição (fog)(x)
dos dois polinômios)
Detalhes
Builtins são permitidos. Você pode assumir qualquer formatação razoável como entrada / saída, mas o formato de entrada e saída deve corresponder. Por exemplo, formatação como uma string
x^2+3x+5
ou como lista de coeficientes:
[1,3,5] or alternatively [5,3,1]
Além disso, os polinômios de entrada podem ser assumidos como totalmente expandidos e as saídas também devem ser totalmente expandidas.
Exemplos
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
(.)
é uma resposta em Haskell. Você provavelmente quer dizer alguma representação da lista de coeficientes.Respostas:
Haskell,
8672 bytesDefine uma função
o
tal queo g f
calcula a composição f ∘ g. Polinômios são representados por uma lista não vazia de coeficientes começando no termo constante.Demo
Como funciona
Nenhum built-in ou bibliotecas relacionadas a polinômios. Observe as recorrências semelhantes
(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),
para multiplicação polinomial e composição, respectivamente. Ambos assumem a forma
f (x) = a + f₁ (x) x ⇒ W (f) (x) = C (a) (x) + U (W (f₁)) (x).
O operador
!
resolve uma recorrência desse formulário para W, dado U e C, usandozipWith(+).(++[0,0..])
para adição polinomial (assumindo que o segundo argumento seja mais longo - para nossos propósitos, sempre será). Então,(0:)
multiplica um argumento polinomial por x (acrescentando um coeficiente zero);(<$>g).(*)
multiplica um argumento escalar pelo polinômiog
;(0:)!((<$>g).(*))
multiplica um argumento polinomial pelo polinômiog
;pure
eleva um argumento escalar para um polinômio constante (lista de singleton);(0:)!((<$>g).(*))!pure
compõe um argumento polinomial com o polinômiog
.fonte
Mathematica, 17 bytes
Exemplo de uso:
fonte
TI-Basic 68k, 12 bytes
O uso é direto, por exemplo, para o primeiro exemplo:
Que retorna
fonte
→
ter 1 byte no TI-BASIC?Python 2, 138
156 162bytesAs entradas devem ser listas inteiras com os menores poderes primeiro.
Ungolfed:
Neste cálculo, os coeficientes polinomiais são vistos como dígitos (que podem ser negativos) de um número em uma base muito grande. Depois que os polinômios estão nesse formato, a multiplicação ou adição é uma operação inteira única. Desde que a base seja suficientemente grande, não haverá carregamentos que se espalhem para os dígitos vizinhos.
-18 de melhorar o limite,
B
conforme sugerido por @xnor.fonte
B
, seria o10**len(`a+b`)
suficiente?Python + SymPy,
5935 bytesObrigado a @asmeurer por jogar fora 24 bytes!
Execução de teste
fonte
compose()
função.from module import*;function
era um envio válido. Independentemente disso, essa é uma política mais recente, que permite funções de importação e auxiliar com lambdas sem nome.Sábio, 24 bytes
A partir do Sage 6.9 (a versão que é executada em http://sagecell.sagemath.org ), as chamadas de função sem atribuição explícita de argumentos (
f(2) rather than f(x=2)
) fazem com que uma mensagem irritante e inútil seja impressa no STDERR. Como STDERR pode ser ignorado por padrão no código golf, isso ainda é válido.Isso é muito semelhante à resposta SymPy de Dennis porque o Sage é a) construído em Python eb) usa o Maxima , um sistema de álgebra computacional muito semelhante ao SymPy de várias maneiras. No entanto, o Sage é muito mais poderoso que o Python com o SymPy e, portanto, é uma linguagem suficientemente diferente para merecer sua própria resposta.
Verifique todos os casos de teste online
fonte
PARI / GP , 19 bytes
o que permite fazer
para obter
fonte
MATLAB com caixa de ferramentas simbólica, 28 bytes
Esta é uma função anônima. Para chamá-lo, atribua a uma variável ou use
ans
. As entradas são cadeias de caracteres com o formato (os espaços são opcionais)Exemplo de execução:
fonte
Python 2,
239232223 bytesUma implementação 'adequada' que não abuse das bases. Coeficiente menos significativo primeiro.
a
é adição polinomial,m
é multiplicação polinomial eo
é composição.fonte
m([c],e(m,[[1]]+[g]*k))
é o mesmo quee(m,[[c]]+[g]*k)
?a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
( or 0)
dessa versão.JavaScript (ES6),
150103 bytesAceita e retorna polinômios como uma matriz a = [a 0 , a 1 , a 2 , ...] que representa um 0 + a 1 * x + a 2 * x 2 ...
Editar: salvou 47 bytes alternando da multiplicação polinomial recursiva para iterativa, o que me permitiu mesclar duas
map
chamadas.Explicação: r é o resultado, que começa em zero, representado por uma matriz vazia ep é g h , que começa em uma. p é multiplicado por cada f h por sua vez, e o resultado acumulado em r . p também é multiplicado por g ao mesmo tempo.
fonte
Pyth,
5134 bytesSuíte de teste .
fonte
Ruby 2.4 + polinomial , 41 + 12 = 53 bytes
Usa sinalizador
-rpolynomial
. Entrada é doisPolynomial
objetos.Se alguém me derrotar em baunilha Ruby (nenhuma biblioteca externa polinomial), ficarei muito impressionado.
fonte