Dadas dos listas no enteras de enteros, su envío debe calcular y devolver la convolución discreta de los dos. Curiosamente, si considera los elementos de la lista como coeficientes de polinomios, la convolución de las dos listas representa los coeficientes del producto de los dos polinomios.
Definición
Dadas las listas A=[a(0),a(1),a(2),...,a(n)]
y B=[b(0),b(1),b(2),...,b(m)]
(configuración a(k)=0 for k<0 and k>n
y b(k)=0 for k<0 and k>m
), entonces la convolución de los dos se define como A*B=[c(0),c(1),...,c(m+n)]
dondec(k) = sum [ a(x)*b(y) for all integers x y such that x+y=k]
Reglas
- Se permite cualquier formato de entrada y salida conveniente para su idioma.
- Las incorporaciones para convolución, creación de matrices de convolución, correlación y multiplicación polinómica no están permitidas.
Ejemplos
[1,1]*[1] = [1,1]
[1,1]*[1,1] = [1,2,1]
[1,1]*[1,2,1] = [1,3,3,1]
[1,1]*[1,3,3,1] = [1,4,6,4,1]
[1,1]*[1,4,6,4,1] = [1,5,10,10,5,1]
[1,-1]*[1,1,1,1,1] = [1,0,0,0,0,-1]
[80085,1337]*[-24319,406] = [-1947587115,7,542822]
[1,1]*[] = []
, y no es posible que lo sea[]*[] = ?
. La convolución no está bien definida en las listas vacías. Creo que debe garantizar que las listas de entrada no estén vacías.Respuestas:
J,
108 bytesUso:
Descripción: El programa toma dos listas, hace una tabla de multiplicar, luego agrega los números en las diagonales positivas.
fuente
MATL , 19 bytes
Pruébalo en línea!
Explicación
Esto construye una matriz de bloques en diagonal con las dos entradas, invirtiendo la primera. Por ejemplo, con entradas
[1 4 3 5]
,[1 3 2]
la matriz esCada entrada de la convolución se obtiene desplazando la primera fila una posición hacia la derecha, calculando el producto de cada columna y sumando todos los resultados.
En principio, el desplazamiento debe hacerse rellenando con ceros desde la izquierda. De manera equivalente, se puede usar desplazamiento circular , porque la matriz contiene ceros en las entradas apropiadas.
Por ejemplo, el primer resultado se obtiene de la matriz desplazada
y es asi
1*1 == 1
. El segundo se obtiene dey es así
4*1+1*3 == 7
, etc. Esto debe hacersem+n-1
veces, dondem
yn
son las longitudes de entrada. El código usa un bucle conm+n
iteraciones (que ahorra algunos bytes) y descarta el último resultado.fuente
Haskell,
5549 bytesDefine un operador
#
.fuente
[0,0..]
puede ser(0<$b)
para dar exactamente la longitud necesaria, permitiendo el caso base vacío_#b=0<$b
.Matlab / Octave, 41 bytes
Esto define una función anónima. Para llamarlo, asígnelo a una variable o use
ans
.Probar aquí .
Explicación
Esto explota los hechos que
El código calcula las raíces de los dos polinomios (función
roots
) y los concatena en una matriz de columnas. De ahí obtiene los coeficientes del polinomio del producto con una1
función ( principalpoly
). Finalmente, el resultado se multiplica por los coeficientes principales de los dos polinomios.fuente
Octava , 48 bytes
Probar aquí .
Explicación
La convolución discreta corresponde a la multiplicación de las transformadas de Fourier (tiempo discreto). Entonces, una forma de multiplicar los polinomios sería transformarlos, multiplicar las secuencias transformadas y transformar de nuevo.
Si se usa la transformada discreta de Fourier (DFT) en lugar de la transformada de Fourier, el resultado es la convolución circular de las secuencias originales de coeficientes polinomiales. El código sigue esta ruta. Para hacer que la convolución circular sea igual a la convolución estándar, las secuencias se rellenan con ceros y el resultado se recorta.
fuente
05AB1E ,
1817 bytesCódigo
Explicación
La teoría detrás de:
Para encontrar la convolución, tomemos el ejemplo
[1, 2, 3]
,[3, 4, 5]
. Colocamos los valores de la primera matriz boca abajo y verticalmente, así:Ahora, colocamos la segunda matriz como una escalera y la multiplicamos por:
Resultando en:
Luego, los sumamos, resultando en:
Entonces, la convolución es
[3, 10, 22, 22, 15]
.El código en sí:
Vamos a hacer esto paso a paso usando
[1, 2, 3]
,[3, 4, 5]
como el caso de prueba.Primero presionamos
0
y luego valoramosE
la primera matriz de entrada. Mapeamos cada elemento usandov
.Entonces, para cada elemento, empujamos la segunda matriz con
²
y luego la longitud de la primera matriz usando¹g
y disminuimos esto en 1 (con<
). Convertimos esto en una lista de ceros con (longitud 1ª matriz - 1) ceros, usandoÅ0
y agregamos esto a nuestra lista. Nuestra pila ahora se ve así para el primer elemento en la lista de entrada:Multiplicamos esta matriz con el elemento actual, hecho con
y*
. Después de eso, presionamosN
, lo que indica el índice del elemento actual (indexado a cero) y rotamos la matriz que muchas veces hacia la derecha usandoFÁ}
. Finalmente, agregamos esto a nuestro valor inicial (0
). Entonces, lo que básicamente se hace es lo siguiente:Que luego se imprime implícitamente. Utiliza la codificación CP-1252 . Pruébalo en línea! .
fuente
Jalea , 9 bytes
Pruébalo en línea! o verificar todos los casos de prueba .
Cómo funciona
fuente
Casco , 5 bytes
Pruébalo en línea!
Nota: ¡ Al suministrar la lista de polinomio cero / vacío, debe especificar su tipo (es decir
[]:LN
)!Explicación
fuente
Matlab, 33 bytes
Pruébalo en línea!
Crea una matriz de todos los productos basados en elementos de las entradas, luego suma a lo largo de las diagonales. Al
,1
final, obliga a matlab a sumar a lo largo de la dirección correcta cuando uno de los vectores de entrada tiene longitud 1.En Octave
spdiags
no funciona para vectores, lo que genera un error cuando una de las entradas tiene una longitud 1. Se requiere Matlab 2016b o posterior para la expansión explícita del producto basado en elementos.fuente
Ruby, 83 bytes
Casi directamente saqué una respuesta que hice antes sobre la expansión de raíces en un polinomio .
fuente
Python, 90 bytes
fuente
JavaScript (ES6), 64 bytes
Devuelve la matriz vacía si alguna de las entradas está vacía. Basado en mi respuesta a Polynomialception .
fuente
Julia,
6255 bytesPruébalo en línea!
fuente
Clojure, 104 bytes
La fusión con
sorted-map
garantías de que los valores se devuelven en el orden correcto. Desearía que hubiera más casos de prueba.fuente