Dados dos polinomios f,g
de grado arbitrario sobre los enteros, su programa / función debe evaluar el primer polinomio en el segundo polinomio. f(g(x))
(también conocida como la composición (fog)(x)
de los dos polinomios)
Detalles
Las construcciones están permitidas. Puede asumir cualquier formato razonable como entrada / salida, pero el formato de entrada y salida debe coincidir. Ej. Formatear como una cadena
x^2+3x+5
o como una lista de coeficientes:
[1,3,5] or alternatively [5,3,1]
Además, se puede suponer que los polinomios de entrada están completamente expandidos, y también se espera que las salidas estén completamente expandidas.
Ejemplos
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
(.)
es una respuesta en Haskell. Probablemente se refiera a alguna representación de la lista de coeficientes.Respuestas:
Haskell,
8672 bytesDefine una función
o
tal queo g f
calcula la composición f ∘ g. Los polinomios están representados por una lista no vacía de coeficientes que comienza en el término constante.Manifestación
Cómo funciona
No hay bibliotecas o bibliotecas integradas relacionadas con el polinomio. Observe las recurrencias similares.
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),
para multiplicación polinómica y composición, respectivamente. Ambos toman la forma
f (x) = a + f₁ (x) x ⇒ W (f) (x) = C (a) (x) + U (W (f₁)) (x).
El operador
!
resuelve una recurrencia de esta forma para W dado U y C, utilizandozipWith(+).(++[0,0..])
para la suma polinómica (suponiendo que el segundo argumento sea más largo, para nuestros propósitos, siempre lo será). Luego,(0:)
multiplica un argumento polinómico por x (anteponiendo un coeficiente cero);(<$>g).(*)
multiplica un argumento escalar por el polinomiog
;(0:)!((<$>g).(*))
multiplica un argumento polinómico por el polinomiog
;pure
levanta un argumento escalar a un polinomio constante (lista única);(0:)!((<$>g).(*))!pure
compone un argumento polinomial con el polinomiog
.fuente
Mathematica, 17 bytes
Ejemplo de uso:
fuente
TI-Basic 68k, 12 bytes
El uso es sencillo, por ejemplo, para el primer ejemplo:
Que vuelve
fuente
→
ser 1 byte en TI-BASIC?Python 2,
138156162bytesSe espera que las entradas sean listas enteras con las potencias más pequeñas primero.
Sin golf:
En este cálculo, los coeficientes polinómicos se ven como dígitos (que pueden ser negativos) de un número en una base muy grande. Una vez que los polinomios están en este formato, la multiplicación o suma es una operación entera única. Mientras la base sea lo suficientemente grande, no habrá ningún acarreo que se extienda a los dígitos vecinos.
-18 de mejorar el límite
B
según lo sugerido por @xnor.fuente
B
, sería10**len(`a+b`)
suficiente?Python + SymPy,
5935 bytes¡Gracias a @asmeurer por jugar golf en 24 bytes!
Prueba de funcionamiento
fuente
compose()
función.from module import*;function
era una presentación válida. De todos modos, esta es una política más reciente, que permite importaciones y funciones auxiliares con lambdas sin nombre.Sabio, 24 bytes
A partir de Sage 6.9 (la versión que se ejecuta en http://sagecell.sagemath.org ), las llamadas a funciones sin asignación explícita de argumentos (
f(2) rather than f(x=2)
) hacen que se imprima un mensaje molesto e inútil en STDERR. Debido a que STDERR puede ignorarse por defecto en el código de golf, esto todavía es válido.Esto es muy similar a la respuesta SymPy de Dennis porque Sage está a) construido en Python, yb) usa Maxima , un sistema de álgebra computacional muy similar a SymPy en muchos aspectos. Sin embargo, Sage es mucho más poderoso que Python con SymPy y, por lo tanto, es un lenguaje lo suficientemente diferente como para merecer su propia respuesta.
Verifique todos los casos de prueba en línea
fuente
PARI / GP , 19 bytes
que te permite hacer
Llegar
fuente
MATLAB con caja de herramientas simbólica, 28 bytes
Esta es una función anónima. Para llamarlo, asígnelo a una variable o use
ans
. Las entradas son cadenas con el formato (los espacios son opcionales)Ejemplo de ejecución:
fuente
Python 2,
239232223 bytesUna implementación 'adecuada' que no abusa de las bases. Coeficiente menos significativo primero.
a
es una suma polinómica,m
es una multiplicación polinómica yo
es composición.fuente
m([c],e(m,[[1]]+[g]*k))
No es lo mismo quee(m,[[c]]+[g]*k)
?a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
( or 0)
en esa versión.Javascript (ES6),
150103 bytesAcepta y devuelve polinomios como una matriz a = [a 0 , a 1 , a 2 , ...] que representa a 0 + a 1 * x + a 2 * x 2 ...
Editar: guardé 47 bytes al cambiar de multiplicación polinómica recursiva a iterativa, lo que me permitió fusionar dos
map
llamadas.Explicación: r es el resultado, que comienza en cero, representado por una matriz vacía, y p es g h , que comienza en uno. p se multiplica por cada f h a su vez, y el resultado se acumula en r . p también se multiplica por g al mismo tiempo.
fuente
Pyth,
5134 bytesBanco de pruebas .
fuente
Ruby 2.4 + polinomio , 41 + 12 = 53 bytes
Usa bandera
-rpolynomial
. La entrada es dosPolynomial
objetos.Si alguien me supera en vainilla Ruby (sin biblioteca externa polinomial), quedaré muy impresionado.
fuente