Construir una matriz compañera

15

Tienes varios polinomios que están solos, ¡así que conviértelos en compañeros (que no amenacen con apuñalar)!

Para un polinomio de grado n, hay una matriz de cubon by n compañera para él. Debe realizar una función que acepte una lista de coeficientes para un polinomio en orden ascendente ( ) o descendente ( ) (pero no en ambos) y generar la matriz complementaria. a + bx +cx^2 + …ax^n + bx^(n-1) + cx^(n-2)+…

para un polinomio c0 + c1x + c2x^2 + ... + cn-1x^(n-1) + x^n, su matriz compañera es

     (0, 0, 0, ..., -c0  ),
     (1, 0, 0, ..., -c1  ),
     (0, 1, 0, ..., -c2  ),
     (...................),
     (0, 0, ..., 1, -cn-1)

tenga en cuenta que el coeficiente para x^nes 1. Para cualquier otro valor, divida el resto de los coeficientes por x^n's. Además, los 1 están desplazados de la diagonal.

Si el idioma que está utilizando ya contiene una función o módulo que hace esto, no puede usarlo, debe escribir el suyo.

Por ejemplo, si tuviera 4x^2 – 7x + 12, los coeficientes en orden ascendente son (12, -7, 4)y en orden descendente (4, -7, 12). La función o el programa deben salir [(0, -3.0), (1, 1.75)]para cualquier orden. Especifique qué orden acepta su código. El polinomio mínimo debe ser cuadrático. Los coeficientes están restringidos a números reales.

A continuación se muestran ejemplos: su salida no tiene que coincidir con el formato bonito, pero debe generar las filas (en el ()) de la matriz en orden.

Orden ascendente:

input:
    [3., 7., -5., 4., 1.]
output:
    [(0, 0, 0, -3.),
     (1, 0, 0, -7.),
     (0, 1, 0,  5.),
     (0, 0, 1, -4.)]

input:
    [-4., -7., 13.]
output:
    [(0, 0.30769231),
     (1, 0.53846154)]

input:
    [23., 1., 92., 8., -45., 88., 88.]
output:
    [(0, 0, 0, 0, 0, -0.26136364),
     (1, 0, 0, 0, 0, -0.01136364),
     (0, 1, 0, 0, 0, -1.04545455),
     (0, 0, 1, 0, 0, -0.09090909),
     (0, 0, 0, 1, 0,  0.51136364),
     (0, 0, 0, 0, 1, -1.        )]

Orden descendiente:

input:
    [1., 4., -5., 7., 3.]
output:
    [(0, 0, 0, -3.),
     (1, 0, 0, -7.),
     (0, 1, 0,  5.),
     (0, 0, 1, -4.)]

input:
    [13., -7., -4.]
output:
    [(0, 0.30769231),
     (1, 0.53846154)]

input:
    [88., 88., -45., 8., 92.,1., 23.]
output:
    [(0, 0, 0, 0, 0, -0.26136364),
     (1, 0, 0, 0, 0, -0.01136364),
     (0, 1, 0, 0, 0, -1.04545455),
     (0, 0, 1, 0, 0, -0.09090909),
     (0, 0, 0, 1, 0,  0.51136364),
     (0, 0, 0, 0, 1, -1.        )]

¡Dennis gana con 20 bytes!

Estado
fuente
2
Los coeficientes son reales (no complejos), ¿verdad?
Luis Mendo
1
¿Son válidos los programas o solo funcionan? (Tenga en cuenta que la restricción de la competencia a las funciones no permite langauges interesantes sin funciones.)
lirtosiast
1
¿Cuál es el polinomio de grado mínimo que tenemos que tener en cuenta?
Alex A.

Respuestas:

3

CJam, 23 20 bytes

{)W*f/_,,_ff=1f>\.+}

Esta es una función que saca la entrada (orden ascendente) de la pila y empuja la salida a cambio.

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

)   e# Pop the last element from the input array.
W*  e# Multiply it by -1.
f/  e# Divide the remaining array elements by this product.
_,  e# Push a copy of the array and compute its length (L).
,_  e# Push [0 ... L-1] twice.
ff= e# For each I in [0 ... L-1]:
    e#   For each J in [0 ... L-1]:
    e#     Push (I==J).
    e# This pushes the L x L identity matrix.
1f> e# Discard the first element of each row, i.e., the first column.
\   e# Swap the result with the modified input.
.+  e# Vectorized append; append the input as a new column.
Dennis
fuente
3

CJam, 32 31 28 bytes

0q~)f/f-_,(_,\0a*1+fm<~]W%z

Pruébalo en línea

Esto toma la entrada en orden ascendente, utilizando el formato de lista CJam. Entrada de muestra:

[-4.0 -7.0 13.0]

Explicación:

0     Push a 0 for later sign inversion.
q~    Get and interpret input.
)     Pop off last value.
f/    Divide all other values by it.
f-    Invert sign of values.
_,    Get count of values, which corresponds to n.
(     Decrement by 1.
_,    Create list of offsets [0 1 ... n-1] for later.
\     Swap n-1 back to top.
0a*   Create list of n-1 zeros.
1+    Append a 1. This is the second-but-last column [0 0 ... 0 1].
fm<   Apply rotation with all offsets [0 1 ... n-1] to column.
~     Unwrap the list of 0/1 columns.
]     Wrap all columns
W%    Invert their order from last-to-first to first-to last.
z     Transpose to get final matrix.
`     Convert to string for output.
Reto Koradi
fuente
3

APL, 40 30 bytes

{(-n↑⍵÷⊃⊖⍵),⍨⍉1↓⍉∘.=⍨⍳n←1-⍨≢⍵}

Acepta entradas en orden ascendente.

Explicación:

{
                        n←1-⍨≢⍵    ⍝ Define n = length(input)-1
                   ∘.=⍨⍳           ⍝ Create an n×n identity matrix
               ⍉1↓⍉                ⍝ Drop the leftmost column
            ,⍨                     ⍝ Append on the right:
  (-n↑⍵                            ⍝ n negated coefficients,
       ÷⊃⊖⍵)                       ⍝ divided by the n+1st
}

Pruébalo en línea

Alex A.
fuente
3

Julia, 43 bytes

c->rot180([-c[2:(n=end)]/c[] eye(n-1,n-2)])

Esto usa orden descendente para la entrada. Construye la matriz girada 180 grados, para permitir un uso más eficiente del "ojo", luego gira la matriz en la orientación correcta.

Glen O
fuente
2

Julia, 64 44 bytes

c->(k=c[n=end];[eye(n-=1)[:,2:n] -c[1:n]/k])

Acepta un vector de los coeficientes en orden ascendente.

Sin golf:

function f(c::Array)
    # Simultaneously define k = the last element of c and
    # n = the length of c
    k = c[n = end]

    # Decrement n, create an n×n identity matrix, and exclude the
    # first column. Horizontally append the negated coefficients.
    [eye(n-=1)[:,2:n] -c[1:n]/k]
end

Pruébalo en línea

Ahorró 20 bytes gracias a Glen O!

Alex A.
fuente
2

R, 71 59 bytes

Toma entrada en orden ascendente.

function(x)cbind(diag(n<-length(x)-1)[,2:n],-x[1:n]/x[n+1])

Sin golf:

f <- function(x) {
    # Get the length of the input
    n <- length(x)-1

    # Create an identity matrix and exclude the first column
    i <- diag(n)[, 2:n]

    # Horizontally append the negated coefficients divided
    # by the last one
    cbind(i, -x[1:n]/x[n+1])
}
Alex A.
fuente
1

Matlab, 66 bytes

function y=f(c)
n=numel(c);y=[[0*(3:n);eye(n-2)] -c(1:n-1)'/c(n)];

Utiliza el orden ascendente para la entrada, con formato [3., 7., -5., 4., 1.]o [3. 7. -5. 4. 1.].

Pruébelo en línea (en octava).

Ejemplo (en Matlab):

>> f([23., 1., 92., 8., -45., 88., 88.])
ans =
                   0                   0                   0                   0                   0  -0.261363636363636
   1.000000000000000                   0                   0                   0                   0  -0.011363636363636
                   0   1.000000000000000                   0                   0                   0  -1.045454545454545
                   0                   0   1.000000000000000                   0                   0  -0.090909090909091
                   0                   0                   0   1.000000000000000                   0   0.511363636363636
                   0                   0                   0                   0   1.000000000000000  -1.000000000000000

Si un programa es válido (en lugar de una función), con stdin y stdout:

Matlab, 59 bytes

c=input('');n=numel(c);[[0*(3:n);eye(n-2)] -c(1:n-1)'/c(n)]
Luis Mendo
fuente
Creo que puedes hacern=numel(c=input(''));
lirtosiast
@ThomasKwa ¡Gracias! Sin embargo, esa no es una sintaxis válida en Matlab. n=numel(input(''))sería válido, pero necesito volver a usarlo cmás tarde
Luis Mendo
Lo siento; funcionó en Octave donde lo probé.
lirtosiast
1

Octava, 45 44 bytes

Suponiendo que ces un vector de columna con el coeficiente de la potencia más alta xal final.

@(c)[eye(n=rows(c)-1)(:,2:n),-c(1:n)/c(end)]

Versión antigua:

@(c)[eye(n=numel(c)-1)(:,2:n),-c(1:n)/c(end)]

¡Choca los cinco, Julia!

falla
fuente
1

Python 2, 141 bytes

Mi propio intento:

def C(p):
 c,r=p.pop(0),range;d=[-i/c for i in p];n=len(d);m=[[0]*n for i in r(n)]
 for i in r(n-1):m[i][i+1]=1
 m[-1]=d[::-1];return zip(*m)

Toma una lista de los coeficientes en orden descendente y primero construye la transposición de la matriz compañera, conocida por apuñalar y ser hablador. La devolución usa zip para producir la transposición de esta transposición para obtener la matriz real.

>>> C([1., 4., -5., 7., 3.])
[(0, 0, 0, -3.0), (1, 0, 0, -7.0), (0, 1, 0, 5.0), (0, 0, 1, -4.0)]
Estado
fuente
1

JavaScript (ES6) 85

Orden ascendente

Pruebe a ejecutar el fragmento a continuación en cualquier navegador compatible con EcmaScript 6.

f=c=>alert(c.map((v,i)=>c.map((x,j)=>++j-i?j-c.length?0:-v/m:1),m=c.pop()).join(`
`))

// test
// redefine alert to write into the snippet body
alert=x=>O.innerHTML+=x+'\n'

function test() {
  v=I.value.match(/\d+/g)
  I.value=v+''
  alert(v)
  f(v)
}  

test()
<input value='23.,1.,92.,8.,-45.,88.,88.' id=I><button onclick="test()">-></button>
<pre id=O></pre>

edc65
fuente
0

TI-BASIC, 50 bytes

Ans→X
List▶matr(ΔList(Ans-cumSum(Ans)),[A]
dim(Ans
augment(augment(0randM(Ans-2,1),identity(Ans-2))ᵀ,[A]∟X(Ans)⁻¹

Toma entrada en orden ascendente. Tenga en cuenta que esto no funcionará para polinomios de grado <2, porque TI-BASIC no admite matrices o listas vacías. En espera de una decisión de OP, puedo arreglar esto a costa de unos pocos bytes.

Primero, almacenamos la lista ∟Xpara usar el último elemento más tarde; luego, calculamos ΔList(Ans-cumSum(Ans)), que es solo la lista negada con el último elemento cortado, y la convertimos en un vector de columna. Como List▶matr(no se modifica Ans, podemos usar la siguiente línea para tomar la dimensión de la lista, que usamos tres veces. TI-BASIC no tiene concatenación vertical, por lo que debemos tomar transposiciones y concatenar horizontalmente. En la última línea, [A]/∟X(Ansno funcionaría porque las matrices pueden multiplicarse por escalares pero no dividirse.

Un aparte: para generar el vector fila de ceros, aprovechamos el randM(comando raramente útil .randM(crea una matriz aleatoria, pero sus entradas son siempre enteros aleatorios entre -9 y 9 (!), por lo que en realidad solo es útil crear matrices cero.

lirtosiast
fuente