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

Question

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

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

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

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

测试用例：

• 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 addpoly(p1,p2):
i=0
su=0
j=0
c=[]
if len(p1)==0:
    #if p1 empty
    return p2
if len(p2)==0:
    #if p2 is empty
    return p1
while i<len(p1) and j<len(p2):
    if int(p1[i][1])==int(p2[j][1]):
        su=p1[i][0]+p2[j][0]
        if su !=0:
            c.append((su,p1[i][1]))
        i=i+1
        j=j+1
    elif p1[i][1]>p2[j][1]:
        c.append((p1[i]))
        i=i+1
    elif p1[i][1]<p2[j][1]:
        c.append((p2[j]))
        j=j+1
if p1[i:]!=[]:
    for k in p1[i:]:
        c.append(k)
if p2[j:]!=[]:
    for k in p2[j:]:
        c.append(k)
return c  

乘函数

def multipoly(p1,p2):
p=[]
s=0
for i in p1:
    c=[]
    for j in p2:
        s=i[0]*j[0]
        e=i[1]+j[1]
        c.append((s,e))
    p=addpoly(c,p)
return p 

Answer 2

作为comments中的suggested，将多项式表示为指数的multisets要简单得多。

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

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

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)

（事实上，如果您始终坚持使用计数器表示，您只需return p + q）。

若要乘法多项式，请将一个多项式中的每个项与另一个多项式中的每个项配对相乘。而且，要乘项，你可以加上指数和乘系数。

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 3

我已经想出了一个解决方案，但我不确定它是否得到了优化！

    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)

第二个是：

    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