Finden Sie integrale Wurzeln eines Polynoms

19

Herausforderung

Die Herausforderung besteht darin, ein Programm zu schreiben, das die Koeffizienten einer beliebigen n-Grad-Polynomgleichung als Eingabe verwendet und die Integralwerte von x zurückgibt, für die die Gleichung gilt. Die Koeffizienten werden als Eingabe in der Reihenfolge abnehmender oder zunehmender Leistung bereitgestellt. Sie können annehmen, dass alle Koeffizienten ganze Zahlen sind .

Eingabe und Ausgabe

Die Eingabe sind die Koeffizienten der Gleichung in abnehmender oder zunehmender Reihenfolge der Leistung. Der Grad der Gleichung, dh die maximale Potenz von x, ist immer 1 kleiner als die Gesamtanzahl der Elemente in der Eingabe.

Beispielsweise:

[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)

Ihre Ausgabe sollte nur die eindeutigen Integralwerte von x sein, die die angegebene Gleichung erfüllen. Alle Eingabekoeffizienten sind Ganzzahlen, und das Eingabepolynom ist kein Nullpolynom . Wenn es für die angegebene Gleichung keine Lösung gibt, ist die Ausgabe undefiniert.

Wenn eine Gleichung wiederholte Wurzeln hat, zeigen Sie diese bestimmte Wurzel nur einmal an. Sie können die Werte in beliebiger Reihenfolge ausgeben. Nehmen Sie außerdem an, dass die Eingabe mindestens 2 Zahlen enthält.

Beispiele

[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] -> -

Beachten Sie, dass die Gleichung im zweiten Beispiel auch die Wurzel 0,2 hat, aber nicht angezeigt wird, da 0,2 keine ganze Zahl ist.

Wertung

Das ist , also gewinnt der kürzeste Code (in Bytes)!

Manish Kundu
quelle
7
Hinweis: Beachten Sie vor dem Abstimmen, dass es sich bei dieser Frage nicht um ein Duplikat handelt . Ich kann mir mindestens einen Ansatz für dieses Problem vorstellen, der für die andere Herausforderung nicht trivial modifizierbar ist (obwohl ich nicht sage, was; das bleibt Ihnen).
Erik der Outgolfer
Können wir annehmen, dass wir nur Wurzeln innerhalb der ganzzahligen Grenzen unserer Sprache zurückgeben müssen? Oder sollte der Algorithmus auch dann funktionieren, wenn der Bereich für ganzzahlige Sprachen erhöht wurde, das Verhalten jedoch gleich blieb?
Freitag,
1
Können wir auch einen nativen Polynomtyp verwenden, wenn Ihre Sprache diese unterstützt?
Fehler
1
Werden Programme für immer ausgeführt, wenn keine Lösungen akzeptiert werden?
Jack M
1
Das soll die Dinge einfach halten.
Manish Kundu

Antworten:

6

MATL , 13 - 12 Bytes

|stE:-GyZQ~)

Probieren Sie es online!

Dies nutzt die Tatsache, dass für ganzzahlige Koeffizienten der Absolutwert einer Wurzel streng kleiner ist als die Summe der Absolutwerte der Koeffizienten.

Erläuterung

Betrachten Sie die Eingabe [1 5 6]als Beispiel.

|    % 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]
Luis Mendo
quelle
3
Alternativ zum Satz von Rouche würde auch der Satz der rationalen Wurzeln ausreichen, um die von Ihnen verwendete Schranke zu rechtfertigen. Nach dem Theorem der rationalen Wurzeln sind alle ganzzahligen Wurzeln im absoluten Wert durch das Maximum der absoluten Werte der Koeffizienten begrenzt, was enger ist als die Summe. Oder noch enger, um den absoluten Wert des "letzten" Koeffizienten ungleich Null, dh des Koeffizienten der kleinsten Potenz von x, der einen Koeffizienten ungleich Null hat. (
Hilft
1
@mathmandan dieser Ansatz ist drei Bytes länger: Probieren Sie es hier aus , obwohl ich sicher ein oder zwei Tricks verpasst habe
Giuseppe
@ Giuseppe Vielen Dank an beide. Vielleicht X>t_w&:GyZQ~), aber immer noch 13 Bytes
Luis Mendo
1
... aber ich fand eine kürzere Alternative für den Bereich
Luis Mendo
5

Schale , 10 9 Bytes

-1 Byte dank Zgarb

uSȯf¬`Bṁṡ

Probieren Sie es online!

Erläuterung

       ṁṡ   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
H.PWiz
quelle
Sie tun können , ṁṡstatt , oṡ►awenn Sie später dedupliziert.
Zgarb
@ Zgarb Sehr schön! Danke
H.PWiz
5

Haskell , 54 Bytes

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

Probieren Sie es online!

Brute Force und synthetische Teilung.

Ungolfed mit UniHaskell und-XUnicodeSyntax

import UniHaskell

roots     Num a  [a]  [a]
roots xs = [r | r  -bound  bound, foldl1 ((+)  (r ×)) xs  0]
             where bound = sum $ abs § xs

Alternative Lösung, 44 Byte

Dank an Nimi.

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

Ich wünsche Ihnen viel Glück beim Online - Probieren , da hiermit jede Nummer in einem bestimmten IntBereich überprüft wird .

total menschlich
quelle
Sie können iterieren iüber [minBound..]die ganze und fallen tSache. Anruf fmit expliziten IntListen, z f [1::Int,5,6]. Natürlich endet dies nicht in angemessener Zeit.
nimi
@nimi Warum sollte das jemals aufhören? Wäre es nicht eine Endlosschleife?
Totalhuman
Nein, BoundedTypen enden bei maxBound, z print [minBound::Bool ..].
nimi
4

Python 2 + Anzahl, 95 93 91 103 93 91 82 Bytes

-2 Bytes danke an ovs
danke an Luis Mendo für die oberen / unteren Grenzen der Wurzeln
-10 Bytes danke an Mr. Xcoder

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

Probieren Sie es online!

Stange
quelle
91 Bytes
Ovs
@ LuisMendo ja.
Rod
3
Unser gegenwärtiger Konsens scheint zu sein, dass Programme immer beendet werden müssen, sofern die Herausforderung nichts anderes angibt.
Zgarb
@Zgarb da, behoben!
Rod
Mit numpy.polyvalspart einige Bytes
Mr. Xcoder
4

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

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

Probieren Sie es online!

Update: Unter Verwendung von Luis Mendos Fakt wurden weitere 3 Bytes abgegolft

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

Wir werden mit den Grenzen schlampiger und können diese 5 Bytes mehr pro @Not-Vorschlag eines Baums reduzieren:

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

Nachdem dies gepostet wurde, kommentierte OP das Zulassen von "nativen Polynomen". Hier ist also eine 25-Byte-Lösung, die das Polynom als Eingabe akzeptiert. Dies funktioniert, weil Mathematica standardmäßig Polynome über die ganzen Zahlen faktorisiert und alle rationalen Wurzeln in einer m*x+bsolchen Form angezeigt werden, bei der die Musterübereinstimmung fehlschlägt.

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

Wie @alephalpha betont hat, schlägt dies für den Fall fehl, in dem Null eine Wurzel ist, um zu beheben, dass wir das OptionalSymbol verwenden können:

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

Dies analysiert Mathematica 11.0.1, schlägt jedoch fehl und erfordert einen zusätzlichen Satz von Klammern b_:0in Version 11.2. Dies beansprucht bis zu 27 Bytes plus zwei weitere nach Version 11.0.1. Es sieht aus wie ein „fix“ wurde in setzen hier

Probieren Sie es online!

Kelly Lowder
quelle
1
Ich denke, Sie können #.#anstelle von verwenden Tr@Abs@#: Es ist eine schlechtere Grenze, aber weniger Bytes.
Kein Baum
1
OP sagte in einem Kommentar, dass Sie den Polynomtyp Ihrer Sprache verwenden könnten, falls einer existiert. Ich kenne Mathematica nicht gut, aber ich stelle mir vor, es gibt eine ... Würde das Bytes sparen?
Nein, mein richtiger Name wird nicht angezeigt
1
@alephalpha, behoben.
Kelly Lowder
3

Wolfram Language (Mathematica) , 33 26 31 Bytes

Es wurde ein Fehler behoben, der von Kelly Lowder in den Kommentaren vermerkt wurde.

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

Probieren Sie es online!

Vorherige falsche Lösungen:

Mir ist gerade aufgefallen, dass für keine ganzzahlige Lösung die Ausgabe undefiniert anstelle einer leeren Liste ist. Dadurch können einige Bytes entfernt werden.

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

Probieren Sie es online!

Wenn jetzt keine ganzzahlige Lösung existiert, kehrt die Funktion zurück x.

Vorher:

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

Probieren Sie es online!

Celtschk
quelle
Dies schlägt fehl, wie aktuell mit 1,2,1 angegeben, da es die Wurzel wiederholt und das OP angibt, dass sie unterschiedlich sein müssen. Sie müssen Uniondas beheben.
Kelly Lowder
@ KellyLowder: Ah, das habe ich verpasst. Dann fehlte es aber auch in den gegebenen Testfällen.
Celtschk
@ KellyLowder: Ich habe es jetzt behoben. Kannst du es bitte zurücksetzen, falls du deswegen zurückgestimmt hast?
Celtschk
@ Cellschk, yep getan.
Kelly Lowder
29 Bytes bei Verwendung einer undokumentierten Funktion von Solve: Die Liste der Variablen kann weggelassen werden.
Roman
3

R , 61 59 Bytes

Ein besonderes Dankeschön an @mathmandan für den Hinweis auf meine (falsche) Herangehensweise könnte gerettet und gespielt werden!

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

Probieren Sie es online!

Nimmt die Eingabe als Liste von Koeffizienten in aufsteigender Reihenfolge, dh c(-1,0,1)repräsentiert -1+0x+1x^2.

Unter Verwendung des rationalen Wurzelsatzes funktioniert der folgende Ansatz für 47 Bytes beinahe:

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

Probieren Sie es online!

-p:pgeneriert einen symmetrischen Bereich (mit einer Warnung), indem nur das erste Element von p, verwendet wird a_0. Nach dem Rational Root Theorem müssen alle rationalen Wurzeln von Pdie Form haben, p/qin der sich pdividiert a_0und qdividiert a_n(plus oder minus). Daher ist die Verwendung von just a_0für |a_0|>0, wie für alle q, ausreichend |p/q|<=a_0. Wenn a_0==0sich jedoch wie damals eine ganze Zahl teilt 0, schlägt dies fehl.

Mathmandan weist jedoch darauf hin, dass in diesem Fall tatsächlich ein konstanter Faktor herausgerechnet werden x^kkann, und unter der Annahme, dass er kmaximal ist, sehen wir dies

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

Wir wenden dann den Satz der rationalen Wurzel an Q(x)und liefern , wie a_kdurch die Maximalität von garantiert ist k, a_keine aufgeräumte Grenze für die ganzzahligen Wurzeln von Q, und die Wurzeln von Psind die Wurzeln von Qzusammen mit Null, so dass wir die ganze ganze ganze Zahl haben Wurzeln von Pdurch diese Methode anwenden.

Dies ist äquivalent dazu, den ersten Koeffizienten des Polynoms zu finden, der nicht Null ist, t=p[!!p][1]und ihn anstelle des Naiven p[1]als Grenze zu verwenden. Da der Bereich -t:timmer Null enthält, würde die Anwendung Pauf diesen Bereich immer noch Null als Wurzel ergeben, wenn dies tatsächlich der Fall ist.

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
}

Giuseppe
quelle
(Ich denke, Sie könnten maxdie absoluten Werte anstelle von verwenden sum; dies würde die Byteanzahl nicht ändern, sollte aber die Leistung verbessern.) Wie auch immer, schade, dass die kürzere Version nicht funktioniert a_0==0. Gibt es in R eine kurze Möglichkeit, nach dem ersten Koeffizienten (mit aufsteigender Potenz) ungleich Null zu suchen und diesen stattdessen zu verwenden? Dies würde bedeuten, zuerst so viele x wie möglich herauszurechnen (natürlich müsste man dann daran denken, auch auszugeben 0, was vermutlich einige Bytes kosten würde.)
mathmandan
@mathmandan maxwäre effizienter, aber zu Ihrem zweiten Punkt, da ich mich nicht um die Ausgabe kümmern muss, 0da sie durch den Bereich generiert wird -t:t(wo tder erste Koeffizient ungleich Null ist), werden 2 Bytes gespart!
Giuseppe
Oh! Sehr schön! (Und eine schöne Erklärung auch.)
Mathmandan
2

Gelee , 8 Bytes

ASŒRḅ@Ðḟ

Probieren Sie es online! oder als Testsuite!

Wie?

ASŒRŒ @ Ðḟ || Volles Programm (monadischer Link).

AS || Summiere die absoluten Werte.
  ŒR || Und erstellen Sie den symmetrischen Einschlussbereich aus seinem negativen Wert.
       Ðḟ || Und wirf diejenigen weg, die einen wahren Wert ergeben ...
     ḅ @ || Beim Einstecken in das Polynom (Basiskonvertierung).

Basierend auf Luis 'Antwort . Eine Alternative .

Mr. Xcoder
quelle
Fehlt mir etwas, wenn ich die (erlaubte) umgekehrte Reihenfolge einnehme und tue Ær+.Ḟ?
Jonathan Allan
Ich bin ein wenig verwirrt, da die Python-Antwort mit numpy dies auch nicht tut, und denke, ich habe einen Randfall verpasst.
Jonathan Allan
@ JonathanAllan Wie ich erwartet hatte, schlägt deins fehl [1,2,3].
Mr. Xcoder
"Wenn es für die angegebene Gleichung keine Lösung gibt, ist die Ausgabe undefiniert"
Jonathan Allan
@JonathanAllan Aber es ist nicht für [10,-42,8], nicht wahr?
Mr. Xcoder
2

Oktave , 59 49 Bytes

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

Probieren Sie es online!

Dies ist ein Port meiner R-Antwort . Der einzige Unterschied besteht darin, dass ich den Bereich explizit verwenden sign(t)und endgenerieren muss und dass polyvaldas Polynom berechnet werden muss.

Nimmt die Eingabe als Zeilenvektor von Koeffizienten in absteigender Reihenfolge.

Giuseppe
quelle
2

Pari / GP , 31 Bytes

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

Faktorisiert das Polynom und wählt die Faktoren aus, deren Ableitungen 1 sind.

Probieren Sie es online!

Alephalpha
quelle
2

C (gcc) , 127 126 123 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;}

Probieren Sie es online!


Erläuterung

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

Probieren Sie es online!

Jonathan Frech
quelle
l+~j++kann golfen werdenl-++j
Kevin Cruijssen
@ KevinCruijssen Vielen Dank.
Jonathan Frech
@ceilingcat Vielen Dank.
Jonathan Frech
1

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

Inspiriert von @Rods Python 2-Antwort (seine 82-Byte-Version) .

Eine lustige Herausforderung! Ich habe sicherlich viel gelernt, als ich Polynome untersuchte und sah, wie es einige andere hier getan haben.

Erläuterung:

Probieren Sie es online aus.

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`
Kevin Cruijssen
quelle
0

JavaScript (ES6), 97 Byte

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

Nimmt Koeffizienten in absteigender Reihenfolge der Leistung und gibt sie in absteigender Reihenfolge aus.

Neil
quelle
0

Sauber , 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]

Probieren Sie es online!

Οurous
quelle