Construir uma matriz complementar

15

Você tem vários polinômios que são solitários, então faça deles alguns companheiros (que não ameaçam esfaquear)!

Para um polinômio de grau n, há uma matriz de cubon by n complementar para ele. Você precisa criar uma função que aceite uma lista de coeficientes para um polinômio na ordem crescente ( ) ou decrescente ( ) (mas não ambas) e gerar a matriz complementar. a + bx +cx^2 + …ax^n + bx^(n-1) + cx^(n-2)+…

para um polinômio c0 + c1x + c2x^2 + ... + cn-1x^(n-1) + x^n, sua matriz associada é

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

note que o coeficiente para x^né 1. Para qualquer outro valor, divida todo o restante dos coeficientes por x^n's. Além disso, os 1s são deslocados da diagonal.

Se o idioma que você está usando já contém uma função ou módulo que faz isso, você não pode usá-lo - você deve escrever o seu.

Por exemplo, se você tiver 4x^2 – 7x + 12, os coeficientes em ordem crescente (12, -7, 4)e decrescente (4, -7, 12). A função ou programa deve gerar[(0, -3.0), (1, 1.75)] para qualquer ordem. Especifique qual pedido seu código aceita. O polinômio mínimo deve ser quadrático. Os coeficientes são restritos a números reais.

Abaixo estão alguns exemplos - sua saída não precisa corresponder à formatação bonita, mas deve gerar as linhas (na ()) da matriz em ordem.

Ordem 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.        )]

Ordem decrescente:

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 vence com 20 bytes!

code-golf math matrix polynomials linear-algebra Status
fonte
2
Coeficientes são reais (não complexos), certo?
Luis Mendo
1
Os programas são válidos ou funcionam apenas? (Tenha em mente que a restrição da competição para funções não permite langauges interessantes sem funções.)
lirtosiast
1
Qual é o polinômio de grau mínimo que temos que considerar?
Alex A.

Respostas:

3

CJam, 23 20 bytes

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

Esta é uma função que exibe a entrada (ordem crescente) da pilha e empurra a saída em troca.

Experimente online no intérprete CJam .

Como 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
fonte
3

CJam, 32 31 28 bytes

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

Experimente online

Isso leva a entrada em ordem crescente, usando o formato de lista CJam. Entrada de amostra:

[-4.0 -7.0 13.0]

Explicação:

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
fonte
3

APL, 40 30 bytes

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

Aceita entrada em ordem crescente.

Explicação:

{
                        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
}

Experimente online

Alex A.
fonte
3

Julia, 43 bytes

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

Isso usa ordem decrescente para a entrada. Ele constrói a matriz girada 180 graus, a fim de permitir um uso mais eficiente do "olho", depois gira a matriz na orientação correta.

Glen O
fonte
2

Julia, 64 44 bytes

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

Aceita um vetor dos coeficientes em ordem crescente.

Ungolfed:

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

Experimente online

Economizou 20 bytes graças a Glen O!

Alex A.
fonte
2

R, 71 59 bytes

Recebe entrada em ordem crescente.

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

Ungolfed:

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.
fonte
1

Matlab, 66 bytes

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

Ele usa ordem crescente para a entrada, com formato [3., 7., -5., 4., 1.]ou [3. 7. -5. 4. 1.].

Experimente online (na oitava).

Exemplo (no 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

Se um programa é válido (em vez de uma função), com stdin e stdout:

Matlab, 59 bytes

c=input('');n=numel(c);[[0*(3:n);eye(n-2)] -c(1:n-1)'/c(n)]
Luis Mendo
fonte
Eu acho que você pode fazern=numel(c=input(''));
lirtosiast
@ThomasKwa Thanks! No entanto, isso não é uma sintaxe válida no Matlab. n=numel(input(''))seria válido, mas eu preciso usá-lo cnovamente mais tarde
Luis Mendo
Desculpe; funcionou no Octave, onde eu o testei.
Lirtosiast
1

Oitava, 45 44 bytes

Assumindo que cé um vetor de coluna com o coeficiente da maior potência de xno final.

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

Versão antiga:

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

Mais cinco, Julia!

flawr
fonte
1

Python 2, 141 bytes

Minha própria tentativa:

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)

Pega uma lista dos coeficientes em ordem decrescente e primeiro cria a transposição da matriz complementar - conhecida por esfaquear e ser falante. O retorno usa zip para produzir a transposição dessa transposição para obter a 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)]
Status
fonte
1

JavaScript (ES6) 85

Ordem ascendente.

Teste a execução do snippet abaixo em qualquer navegador compatível com 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>
Expandir snippet

edc65
fonte
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)⁻¹

Recebe entrada em ordem crescente. Observe que isso não funcionará para polinômios de grau <2, porque o TI-BASIC não suporta matrizes ou listas vazias. Na pendência de uma decisão do OP, posso corrigir isso ao custo de alguns bytes.

Primeiro, armazenamos a lista ∟Xpara usar o último elemento posteriormente; depois calculamos ΔList(Ans-cumSum(Ans)), que é apenas a lista negada com o último elemento cortado e a convertemos em um vetor de coluna. Como List▶matr(não modifica Ans, podemos usar a próxima linha para obter a dimensão da lista, que usamos três vezes. O TI-BASIC não possui concatenação vertical; portanto, precisamos fazer transposições e concatenar horizontalmente. Na última linha, [A]/∟X(Ansnão funcionaria porque as matrizes podem ser multiplicadas por escalares, mas não divididas.

Um aspecto: para gerar o vetor de linha de zeros, aproveitamos o randM(comando raramente útil . randM(cria uma matriz aleatória, mas suas entradas são sempre números inteiros aleatórios entre -9 e 9 (!), portanto, é realmente útil criar matrizes zero.

lirtosiast
fonte