Desafio

O desafio é escrever um programa que considere os coeficientes de qualquer equação polinomial de n grau e retorne os valores integrais de x para os quais a equação é verdadeira. Os coeficientes serão fornecidos como entrada na ordem de potência decrescente ou crescente. Você pode assumir que todos os coeficientes sejam inteiros .

Entrada e saída

A entrada será os coeficientes da equação em ordem decrescente ou crescente de potência. O grau da equação, ou seja, a potência máxima de x, é sempre 1 menor que o número total de elementos na entrada.

Por exemplo:

[1,2,3,4,5] -> represents x^4 + 2x^3 + 3x^2 + 4x + 5 = 0 (degree = 4, as there are 5 elements)
[4,0,0,3] -> represents 4x^3 + 3 = 0 (degree = 3, as there are 3+1 = 4 elements)

Sua saída deve ser apenas os valores integrais distintos de x que satisfazem a equação dada. Todos os coeficientes de entrada são números inteiros e o polinômio de entrada não será um polinômio zero . Se não houver solução para a equação fornecida, a saída será indefinida.

Se uma equação tiver raízes repetidas, exiba essa raiz específica apenas uma vez. Você pode emitir os valores em qualquer ordem. Além disso, suponha que a entrada conterá pelo menos 2 números.

Exemplos

[1,5,6] -> (-3,-2)
[10,-42,8] -> (4)
[1,-2,0] -> (0,2)
[1, 1, -39, -121, -10, 168] -> (-4, -3, -2, 1, 7)
[1, 0, -13, 0, 36] -> (-3, -2, 2, 3)
[1,-5] -> (5)
[1,2,3] -> -

Observe que a equação no segundo exemplo também tem a raiz 0.2, mas não é exibida como 0.2 não é um número inteiro.

Pontuação

Isso é código-golfe , então o código mais curto (em bytes) vence!

MATL , 13 12 bytes

|stE:-GyZQ~)

Experimente online!

Isso usa o fato de que, para coeficientes inteiros, o valor absoluto de qualquer raiz é estritamente menor que a soma dos valores absolutos dos coeficientes.

Explicação

Considere a entrada [1 5 6]como um exemplo.

|    % Implicit input. Absolute value
     % STACK: [1 5 6]
s    % Sum
     % STACK: 12
t    % Duplicate
     % STACK: 12, 12
E    % Multiply by 2
     % STACK: 12, 24
:    % Range
     % STACK: 12, [1 2 ... 23 24]
-    % Subtract, elemet-wise
     % STACK: [11 10 ... -11 -12]
G    % Push input again
     % STACK: [11 10 ... -11 -12], [1 5 6]
y    % Duplicate from below
     % STACK: [11 10 ... -11 -12], [1 5 6], [11 10 ... -11 -12]
ZQ   % Polyval: values of polynomial at specified inputs
     % STACK: [11 10 ... -11 -12], [182 156 ... 72 90]
~    % Logical negation: turns nonzero into zero
     % STACK: [11 10 ... -11 -12], [0 0 ... 0] (contains 1 for roots)
)    % Index: uses second input as a mask for the first. Implicit display
     % STACK: [-3 -2]

Casca , 10 9 bytes

-1 byte graças a Zgarb

uSȯf¬`Bṁṡ

Experimente online!

Explicação

       ṁṡ   Concatenate together the symmetric ranges of each coefficient
            (It is guaranteed that the integer roots lie in the range [-n..n],
                        where n is the coefficient with the largest magnitude)
 Sȯf        Find all the values in that range which
    ¬       are zero
     `B     when plugged through the polynomial
            (Base conversion acts as polynomial evaluation)
u           De-duplicate the roots

Haskell , 54 bytes

f l|t<-sum$abs<$>l=[i|i<-[-t..t],foldl1((+).(i*))l==0]

Experimente online!

Força bruta e divisão sintética.

Ungolfed with UniHaskell and-XUnicodeSyntax

import UniHaskell

roots    ∷ Num a ⇒ [a] → [a]
roots xs = [r | r ← -bound … bound, foldl1 ((+) ∘ (r ×)) xs ≡ 0]
             where bound = sum $ abs § xs

Solução alternativa, 44 bytes

Crédito para nimi.

f l=[i|i<-[minBound..],foldl1((+).(i*))l==0]

Boa sorte em tentar online , pois isso verifica todos os números no Intintervalo de uma.

Python 2 + numpy, 95 93 91 103 93 91 82 bytes

^{-2 bytes graças a ovs
obrigado Luis Mendo pelos limites superior / inferior das raízes
-10 bytes graças a Mr. Xcoder}

from numpy import*
def f(r):s=sum(fabs(r));q=arange(-s,s);print q[polyval(r,q)==0]

Experimente online!

Wolfram Language (Mathematica) , 50 47 42 25 27 bytes

{}⋃Select[x/.Solve[#~FromDigits~x==0],IntegerQ]&

Experimente online!

Atualização: usando o fato de Luis Mendo, jogamos mais 3 bytes

Pick[r=Range[s=-Tr@Abs@#,-s],#~FromDigits~r,0]&

Ficando mais desonesto com os limites, podemos reduzir mais 5 bytes por @Não é uma sugestão da árvore:

Pick[r=Range[s=-#.#,-s],#~FromDigits~r,0]&

Depois de postar isso, o OP comentou a permissão de "polinômios nativos", então aqui está uma solução de 25 bytes que aceita o polinômio como entrada. Isso funciona porque, por padrão, o Mathematica fatora polinômios sobre os números inteiros, e quaisquer raízes racionais aparecem em uma forma como m*x+bessa que falha na correspondência de padrões.

Cases[Factor@#,b_+x:>-b]&

Como @alephalpha apontou, isso falhará no caso em que zero é uma raiz, para corrigir que podemos usar o Optionalsímbolo:

Cases[Factor@#,b_:0+x:>-b]&

Isso analisa o Mathematica 11.0.1, mas falha e requer um conjunto extra de parênteses b_:0na versão 11.2. Isso leva até 27 bytes, além de mais dois após a versão 11.0.1. Parece que uma "correção" foi colocada aqui

Experimente Online!

Wolfram Language (Mathematica) , 33 26 31 bytes

Corrigido um erro observado por Kelly Lowder nos comentários.

x/.{}⋃Solve[#==0,x,Integers]&

Experimente online!

Soluções incorretas anteriores:

Acabei de notar que, para nenhuma solução inteira, a saída é indefinida em vez de lista vazia; que permite remover alguns bytes.

x/.Solve[#==0,x,Integers]&

Experimente online!

Agora, se nenhuma solução inteira existir, a função retornará x.

Anteriormente:

x/.Solve[#==0,x,Integers]/.x->{}&

Experimente online!

R , 61 bytes

Um agradecimento especial a @mathmandan por apontar minha abordagem (incorreta) pode ser salvo e jogado golfe!

function(p)(x=-(t=p[!!p][1]):t)[!outer(x,seq(p)-1,"^")%*%p]

Experimente online!

Toma entrada como uma lista de coeficientes em ordem crescente , isto é, c(-1,0,1)representa -1+0x+1x^2.

Usando o teorema da raiz racional, a seguinte abordagem quase funciona, por 47 bytes:

function(p)(x=-p:p)[!outer(x,seq(p)-1,"^")%*%p]

Experimente online!

-p:pgera um intervalo simétrico (com um aviso), utilizando apenas o primeiro elemento de p, a_0. Pelo teorema da raiz racional , todas as raízes racionais de Pdevem ter a forma em p/qque se pdivide a_0e se qdivide a_n(mais ou menos). Portanto, usar just a_0é suficiente para|a_0|>0 , como para qualquer q, |p/q|<=a_0. No entanto, quando a_0==0, como então, qualquer número inteiro divide0 e, portanto, isso falha.

No entanto, mathmandan ressalta que, realmente, neste caso, isso significa que há um fator constante x^kdisso que pode ser fatorado e, assumindo que ké o máximo, vemos que

P(x) = x^k(a_k + a_{k+1}x + ... a_n x^{n-k}) = x^k * Q(x)

Em seguida, aplicamos o Teorema da Raiz Racional a Q(x)e, como a_ké garantido, diferente de zero pela máxima dek , a_kfornece um limite arrumado para as raízes inteiras de Q, e as raízes de Psão as raízes de Qzero e, portanto, teremos todo o número inteiro. raízes da Paplicação deste método.

Isso é equivalente a encontrar o primeiro coeficiente diferente de zero do polinômio, t=p[!!p][1] e usá-lo em vez do ingênuo p[1]como limites. Além disso, como o intervalo -t:tsempre contém zero, a aplicação Pa esse intervalo ainda nos daria zero como raiz, se é que é.

ungolfed:

function(polynom) {
 bound <- polynom[polynom != 0][1]             #first nonzero value of polynom
 range <- -bound:bound                         #generates [-bound, ..., bound]
 powers <- outer(range,seq_along(p) - 1, "^")  #matrix where each row is [n^0,n^1,n^2,...,n^deg(p)]
 polyVals <- powers %*% polynom                #value of the polynomial @ each point in range
 return(range[polyVals == 0])                  #filter for zeros and return
}

Gelatina , 8 bytes

ASŒRḅ@Ðḟ

Experimente online! ou como uma suíte de teste!

Quão?

ASŒRḅ @ Ðḟ || Programa completo (link monádico).

AS || Soma os valores absolutos.
  ŒR || E crie a faixa simétrica inclusiva a partir do seu valor negativo.
       Ðḟ || E descartar aqueles que produzem um valor de verdade ...
     ḅ @ || Ao conectá-los ao polinômio (usa conversão de base).

Baseado na resposta de Luis . Uma alternativa .

Oitava , 59 49 bytes

@(p)(x=-(t=p(~~p)(end)):sign(t):t)(!polyval(p,x))

Experimente online!

Esta é uma porta da minha resposta R . A única diferença é que eu tenho que usar sign(t)e endgerar explicitamente o intervalo e que ele precisa polyvalcalcular o polinômio.

Recebe entrada como um vetor de linha de coeficientes em ordem decrescente.

Pari / GP , 31 bytes

p->[x-a|a<-factor(p)[,1],a'==1]

Fatora o polinômio e escolhe os fatores cujos derivativos são 1.

Experimente online!

C (gcc) , 127 126 123 bytes

• Guardado um byte graças a Kevin Cruijssen ; golfe l+~j++para l-++j.
• Agradecimentos ao ceilingcat por salvar três bytes.

x,X,j,m,p;f(A,l)int*A;{for(m=j=0;j<l;m+=abs(A[j++]));for(x=~m;X=x++<m;p||printf("%d,",x))for(p=j=0;j<l;X*=x)p+=A[l-++j]*X;}

Experimente online!

Explicação

C (gcc) , 517 bytes

x,X,j,m,p;                      // global integer variables
f(A,l)int*A;{                   // define function, takes in integer array pointer and length
 for(m=j=0;j<l;m+=abs(A[j++])); // loop through array, sum up absolute values
  for(x=~m;X=x++<m;             // loop through all values x in [-m, m], prime X
   p||printf("%d,",x))          // at loop's end, print x value if polynomial value is zero
    for(p=j=0;j<l;X*=x)         // loop through coefficients
     p+=A[l-++j]*X;}            // build polynomial

Experimente online!

Java 8, 141 140 bytes

a->{int l=a.length,s=0,i,r,f,p;for(int n:a)s+=n<0?-n:n;for(r=~s;r++<s;System.out.print(p==0?r+",":""))for(p=i=0,f=1;i<l;f*=r)p+=a[l-++i]*f;}

Inspirado por resposta Python 2 de @Rod (sua versão de 82 bytes) .

Desafio divertido! Eu certamente aprendi muito disso ao investigar sobre polinômios e ver como alguns outros aqui o fizeram.

Explicação:

Experimente online.

a->{                   // Method with integer-array parameter and no return-type
  int l=a.length,      //  The length of the input-array
      s=0,             //  Sum-integer, starting at 0
      i,               //  Index integer
      r,               //  Range-integer
      f,               //  Factor-integer
      p;               //  Polynomial-integer
  for(int n:a)         //  Loop over the input-array
    s+=n<0?-n:n;       //   And sum their absolute values
  for(r=~s;r++<s;      //  Loop `r` from `-s` up to `s` (inclusive) (where `s` is the sum)
      System.out.print(p==0?r+",":""))
                       //    After every iteration: print the current `r` if `p` is 0
    for(p=i=0,         //   Reset `p` to 0
        f=1;           //   and `f` to 1
        i<l;           //   Loop over the input-array again, this time with index (`i`)
        f*=r)          //     After every iteration: multiply `f` with the current `r`
      p+=              //    Sum the Polynomial-integer `p` with:
         a[l-++i]      //     The value of the input at index `l-i-1`,
                 *f;}  //     multiplied with the current factor `f`

Oitava com Pacote Simbólico, 63 bytes

@(p)(s=double(solve(poly2sym(p)==0)))(s==(t=real(s))&~mod(t,1))

Experimente online!

05AB1E , 8 bytes

ÄOD(Ÿʒβ>

Experimente online!

JavaScript (ES6), 97 bytes

a=>[...Array((n=Math.max(...a.map(Math.abs)))-~n)].map(_=>n--).filter(i=>!a.reduce((x,y)=>x*i+y))

Toma coeficientes em ordem decrescente de potência e resultados de saída em ordem decrescente.

Limpo , 110 91 bytes

import StdEnv
?p#s=sum p
=[i\\i<-[~s..s]|i<>0&&sum[e*i^t\\t<-reverse(indexList p)&e<-p]==0]

Experimente online!

Python 2 , 89 bytes

def f(a):s=sum(map(abs,a));return[n for n in range(-s,s)if reduce(lambda v,c:v*n+c,a)==0]

Experimente online!