如何计算两个多项式的和？

Question

例如3x^4-17x^2-3x+5。多项式的每个项可以表示为一对整数（系数、指数）。然后，多项式本身是这样的对的列表，如
[(3，4)，(-17，2)，(-3，1)，(5，0)]所示。

零多项式0表示为空列表[]，因为它没有具有非零系数的项。

我想写两个函数，用元组（系数、指数）的相同表示形式对两个输入多项式进行相加和相乘：

null

>

addpoly([(4,3）,（3,0)],[(-4,3）,（2,1)])
应该给出[2,1）,（3,0)]

addpoly([(2，1)],[(-2，1)])
应该给出[]

multpoly([(1，1),(-1，0)],[(1，2),(1，1),(1，0)])
应该给出[(1，3),(-1，0)]

这里有一些东西，我开始了，但完全被打动了！

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

Answer 1

正如评论中所建议的那样，把多项式表示成指数的多组要简单得多。

在Python中，最接近多集的是计数器数据结构。使用将指数映射到系数的计数器（甚至只是一个普通字典）将自动合并具有相同指数的条目，就像您在编写简化多项式时所期望的那样。

您可以使用计数器执行操作，然后在使用如下函数完成后转换回对列表表示形式：

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

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

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

    return counter_to_poly(r)

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)