Wie berechnet man die Summe zweier Polynome?

Question

Zum Beispiel 3x^4 - 17x^2 - 3x + 5. Jeder Term des Polynoms kann als ein Integer-Paar (Koeffizient, Exponent) dargestellt werden. Das Polynom selbst ist dann eine Liste solcher Paare wie
[(3,4), (-17,2), (-3,1), (5,0)] für das Polynom wie gezeigt.

Nullpolynom, 0, wird als leere Liste [] dargestellt, da es keine Terme mit Koeffizienten ungleich Null hat.

Ich möchte zwei Funktionen schreiben zwei Eingangs Polynome mit der gleichen Darstellung Tupel (Koeffizient, Exponent) zu addieren und zu multiplizieren:

1. addpoly(p1, p2)
2. multpoly(p1, p2)

Testfälle:

• addpoly([(4,3),(3,0)], [(-4,3),(2,1)])
  sollte []

• multpoly([(1,1),(-1,0)], [(1,2),(1,1),(1,0)])
  geben sollte geben sollte [(1, 3),(-1, 0)]

Hier [(2, 1),(3, 0)]

addpoly([(2,1)],[(-2,1)])
geben, ist etwas, das ich mit angefangen hat, aber völlig geschlagen!

def addpoly(p1, p2): 
    (coeff1, exp1) = p1 
    (coeff2, exp2) = p2 
    if exp1 == exp2: 
     coeff3 = coeff1 + coeff2 

Answer 1

Als suggested im comments, es ist viel einfacher Polynome als multisets von Exponenten darzustellen.

In Python ist die Datenstruktur Counter die nächste Sache, die einem Multiset entspricht. Wenn Sie ein Counter (oder auch nur ein einfaches Dictionary) verwenden, das Exponenten Koeffizienten zuordnet, werden automatisch Einträge mit dem gleichen Exponenten koalesziert, genau wie Sie es erwarten würden, wenn Sie ein vereinfachtes Polynom schreiben.

Sie können Operationen durchführen Counter verwenden, und dann in die Liste der Paare Darstellung zurück konvertieren bei Verwendung einer Funktion wie folgt beendet:

def counter_to_poly(c): 
    p = [(coeff, exp) for exp, coeff in c.items() if coeff != 0] 
    # sort by exponents in descending order 
    p.sort(key = lambda pair: pair[1], reverse = True) 
    return p 

Polynome hinzuzufügen, Sie Gruppe zusammen wie-Exponenten und summieren ihre Koeffizienten.

def addpoly(p, q): 
    r = collections.Counter() 

    for coeff, exp in (p + q): 
     r[exp] += coeff 

    return counter_to_poly(r) 

(In der Tat, wenn Sie mit der Gegendarstellung halten sind überall, konnte man nur return p + q).

Um Polynome zu multiplizieren, multiplizieren Sie jeden Begriff aus einem Polynom paarweise mit jedem Ausdruck aus dem anderen. Und außerdem, um Terme zu multiplizieren, addieren Sie Exponenten und multiplizieren Koeffizienten.

def mulpoly(p, q): 
    r = collections.Counter() 

    for (c1, e1), (c2, e2) in itertools.product(p, q): 
     r[e1 + e2] += c1 * c2 

    return counter_to_poly(r) 

Answer 2

Ich habe eine Lösung gefunden, aber ich bin mir nicht sicher, dass es optimiert ist!

def addpoly(p1,p2): 
     for i in range(len(p1)): 
      for item in p2: 
       if p1[i][1] == item[1]: 
        p1[i] = ((p1[i][0] + item[0]),p1[i][1]) 
        p2.remove(item) 
     p3 = p1 + p2 
     for item in (p3): 
      if item[0] == 0: 
       p3.remove(item) 
     return sorted(p3) 

und die zweite: -

def multpoly(p1,p2): 
     for i in range(len(p1)): 
      for item in p2: 
       p1[i] = ((p1[i][0] * item[0]), (p1[i][1] + item[1])) 
       p2.remove(item) 
     return p1