Polynom Long Division

10

Implementieren Sie die Polynom-Long-Division, einen Algorithmus, der zwei Polynome teilt und den Quotienten und den Rest erhält:

(12x ^ 3 - 5x ^ 2 + 3x - 1) / (x ^ 2 - 5) = 12x - 5 R 63x - 26

In Ihren Programmen stellen Sie Polynome als Array dar, wobei der konstante Term am Ende steht. Zum Beispiel wird x ^ 5 - 3x ^ 4 + 2x ^ 2 - x + 1 zu [1, -3, 0, 2, -1, 1].

Die lange Teilungsfunktion, die Sie schreiben möchten, gibt zwei Werte zurück: den Quotienten und den Rest. Sie müssen nicht mit numerischen Ungenauigkeiten und Rechenfehlern umgehen. Verwenden Sie keine mathematische Bibliothek, um Ihre Arbeit zu erledigen. Möglicherweise können Sie Ihre Funktion jedoch in die Lage versetzen, mit symbolischen Werten umzugehen. Der kürzeste Code gewinnt.

BEISPIEL: div([12, -5, 3, -1], [1, 0, -5]) == ([12, -5], [63, -26])

code-golf math abstract-algebra polynomials Ming-Tang
quelle
rosettacode.org/wiki/Polynomial_synthetic_division#Python
ghosts_in_the_code

Antworten:

3

J, 94

f=:>@(0&{)
d=:0{[%~0{[:f]
D=:4 :'x((1}.([:f])-((#@]{.[)f)*d);([:>1{]),d)^:(>:((#f y)-(#x)))y'

z.B.

(1 0 _5) D (12 _5 3 _1;'')
63 _26 | 12  _5

Erklärung einiger Schnipsel unter der Voraussetzung, dass a: (12 -5 3 -1) und b: (1 0 -5)

Länge von a:

#a
4

Machen Sie a und b gleich, indem Sie Nullen an b anhängen:

(#a) {. b
1 0 -5 0

Teilen Sie höhere Kräfte (erste Elemente) von a, b:

(0{a) % (0{b)
12

multipliziere b damit und subtrahiere es von a:

a - 12*b
12 0 _60

n-mal wiederholen b = f (a, b):

a f^:n b
Eelvex
quelle
Zwei Dinge. 1) Gewinnen Sie Charaktere, indem Sie Dividende / Divisor in der ungewöhnlichen Reihenfolge nehmen? 2) Ist das nachlaufende ";" in der Dividende notwendig? sieht aus wie etwas, das Sie aus dem eigentlichen Programm heraus tun sollten.
JB
@JB: 1) Nein, tatsächlich könnte es für die "übliche" Reihenfolge kürzer sein; So habe ich angefangen, darüber nachzudenken. 2) Es ist ein Teil des Arrays so ich nehme es sein , einen Teil des Eingangs soll.
Eelvex
Ich kann nicht verstehen, was ein zusätzliches leeres Array mit der Eingabe zu tun hat.
JB
3

Python 2, 260 258 257 255 Bytes

exec'''def d(p,q):
 R=range;D=len(p);F=len(q)-1;d=q[0];q=[q[i]/-d@R(1,F+1)];r=[0@R(D)];a=[[0@R(F)]@R(D)]
@R(D):
  p[i]/=d;r[i]=sum(a[i])+p[i]
  for j in R(F):
   if i<D-F:a[i+j+1][F-j-1]=r[i]*q[j]
 return r[:D-F],[d*i@r[D-F:]]'''.replace('@',' for i in ')

Dies führt aus:

def d(p,q):
 R=range;D=len(p);F=len(q)-1;d=q[0];q=[q[i]/-d for i in R(1,F+1)];r=[0 for i in R(D)];a=[[0 for i in R(F)] for i in R(D)]
 for i in R(D):
  p[i]/=d;r[i]=sum(a[i])+p[i]
  for j in R(F):
   if i<D-F:a[i+j+1][F-j-1]=r[i]*q[j]
 return r[:D-F],[d*i for i in r[D-F:]]

Verwenden Sie wie folgt:

>>>d([12., -5., 3., -1.],[1.,0.,-5.])
([12.0, -5.0], [63.0, -26.0])
Justin
quelle
1
Wow, ich habe zum ersten Mal gesehen, dass ein Exec / Replace tatsächlich zum Speichern von Zeichen verwendet wird.
xnor
@xnor Ich habe das ein anderes Mal gemacht, aber für mehr als einen Ersatz.
Justin
2

Haskell, 126

Für den Anfang:

l s _ 0=s
l(x:s)(y:t)n=x/y:l(zipWith(-)s$map(*(x/y))t++repeat 0)(y:t)(n-1)
d s t=splitAt n$l s t n where n=length s-length t+1

Beispielverwendung:

*Main> d [12, -5, 3, -1] [1, 0, -5]
([12.0,-5.0],[63.0,-26.0])
JB
quelle
1

Javascript mit Lambdas, 108

f=(a,b)=>{for(n=b.length;a.length>=n;a.shift())for(b.push(k=a[q=0]/b[0]);q<n;++q)a[q]-=k*b[q];b.splice(0,n)}

Es ersetzt das erste Argument durch Erinnerung und das zweite durch Ergebnis.

Anwendungsbeispiel in Firefox:

f(x=[12,-5,3,-1], y=[1,0,-5]), console.log(x, y)
// Array [ 63, -26 ] Array [ 12, -5 ]

Entschuldigung für den Fehler. Bereits behoben.

Qwertiy
quelle