我想创建一个名为multipoly(x,y)的函数，它将两个列表作为输入，将列表相乘并返回答案。
多项式表示如下：例如x ^ 4 + 2X ^ 3表示为[(1,4),(2,3)]。
这是我得到的东西，但它为一些测试用例返回了错误的答案：
def multipoly(p1,p2):
x=max(p1,p2)
y=min(p1,p2)
p1=x
p2=y
for i in range(len(x)):
for item in p2:
p1[i] = ((p1[i][0] * item[0]), (p1[i][1] + item[1]))
p2.remove(item)
return p1
print(multipoly([(1,1),(-1,0)],[(1,2),(1,1),(1,0)]))
你可能最好将它作为一个类来实现，以封装多项式上的所有操作：
也许这样的事情作为开始的基础？
在这里，我选择通过一系列系数表示多项式，其中指数是x的相应指数
警告，结果看起来没问题，但我没有写测试，因此在某些角落情况下可能会很脆弱。
class Polynomial:
def __init__(self, coefficients:list):
"""represents polynomials as a list of parameters where
the indices are the exponents"""
self.coefficients = coefficients
def __len__(self):
return len(self.coefficients)
def __getitem__(self, idx):
return self.coefficients[idx]
def __iter__(self):
for coeff in self.coefficients:
yield coeff
def __str__(self):
res = [str(self.coefficients[0]) + ' + '] if self.coefficients[0] != 0 else []
for exponent, coeff in enumerate(self.coefficients[1:]):
e = exponent + 1
if coeff != 0:
if e == 1:
if coeff == 1:
res.append('x + ')
else:
res.append(f'({coeff})*x + ')
elif coeff == 1:
res.append(f'x**{e} + ')
else:
res.append(f'({coeff})*x**{e} + ')
return ''.join(res)[:-3]
def __add__(self, other):
result = [0] * max(len(self), len(other))
for idx in range(len(result)):
try:
a = self[idx]
except IndexError:
a = 0
try:
b = other[idx]
except IndexError:
b = 0
result[idx] = a + b
return Polynomial(result)
def __mul__(self, other):
result = [0] * (len(self) + len(other))
for exponent_a, coeff_a in enumerate(self):
for exponent_b, coeff_b in enumerate(other):
result[exponent_a + exponent_b] += coeff_a * coeff_b
return Polynomial(result)
def d_dx(self):
return Polynomial([expo * coeff for expo, coeff in enumerate(self)][1:])
a = Polynomial([1, 2, 3, 0, 0, 6])
b = Polynomial([1, 2, 3, 1, 1, 0])
print(a, '\n', b, '\n', a + b, '\n', a * b, '\n', a.d_dx(), '\n', b.d_dx(), '\n', (a*b).d_dx())
print()
c = Polynomial([1, 1])
d = Polynomial([1, -1])
print(c, '\n', d, '\n', c + d, '\n', c * d)
1 + (2)*x + (3)*x**2 + (6)*x**5
1 + (2)*x + (3)*x**2 + x**3 + x**4
2 + (4)*x + (6)*x**2 + x**3 + x**4 + (6)*x**5
1 + (4)*x + (10)*x**2 + (13)*x**3 + (12)*x**4 + (11)*x**5 + (15)*x**6 + (18)*x**7 + (6)*x**8 + (6)*x**9
2 + (6)*x + (30)*x**4
2 + (6)*x + (3)*x**2 + (4)*x**3
4 + (20)*x + (39)*x**2 + (48)*x**3 + (55)*x**4 + (90)*x**5 + (126)*x**6 + (48)*x**7 + (54)*x**8
1 + x
1 + (-1)*x
2
1 + (-1)*x**2
您可以使用字典存储乘法的结果，以便已经计算的指数可以直接添加到先前的计算值
以下代码有效
def multipoly(p1,p2):
mul = dict()
for m in p1:
for n in p2:
if m[1] + n[1] in mul:
mul[m[1] + n[1]] += m[0] * n[0]
else:
mul[m[1] + n[1]] = m[0] * n[0]
m_res = []
for p, q in mul.items():
m_res.append((q, p))
return m_res
print(multipoly([(1,1),(-1,0)],[(1,2),(1,1),(1,0)]))
它比你的解决方案少。因为在你的解决方案中你要删除p2中的一个元素，它需要O(sizeof(p2))时间。
还有另一种方式。使用itertools groupby来组合类似的术语：
from itertools import groupby
def multipoly(poly1,poly2):
#multiply two polynolials
temp = [(p1[0]*p2[0], p1[1]+p2[1]) for p1 in poly1 for p2 in poly2]
#sort to use for groupby
temp = sorted(temp, key= lambda x: x[1])
#groupby second term
g = groupby(temp, lambda x: x[1])
#combine terms
result = []
for k,v in g:
result.append((sum([i[0] for i in v]), k))
result.sort(key=lambda x: -x[1])
return result
如果你只是想要一个函数乘以两个多项式，表示为元组[(coef, expn) ...]的列表，你可以从term乘以两个多项式p1, p2开始
p3 = [(c1*c2, e1+e2) for c1, e1 in p1 for c2, e2 in p2]
但是你有一个问题，因为一般来说，你将有多个具有相同指数的术语，为了规范化p3中的结果，我们可以使用一个字典
d = {}
for c, e in p3:
d[e] = d.get(e, 0) + c
请注意，如果指数已存在于d.get(e, 0)或返回d[e]，则d将返回0。
最后，您希望将结果作为元组列表返回
p3 = [(c, e) for e, c in d.items()]
但不保证此列表按指数递减的顺序排序
p3 = sorted(p3, key=lambda t: -t[1])
可以将所有这些放在一个可调用的中
def pmult(p1, p2):
d = {}
for coef, expn in [(c1*c2, e1+e2) for c1, e1 in p1 for c2, e2 in p2]:
d[expn] = d.get(expn,0)+coef
return sorted([(c, e) for e, c in d.items()], key=lambda t: -t[1])
一个测试：
In [25]: a = [(1,2),(3,0)]
In [26]: b = [(1,4),(2,3),(3,2),(4,1),(5,0)]
In [27]: def pmult(p1, p2):
...: d = {}
...: for coef, expn in [(c1*c2, e1+e2) for c1, e1 in p1 for c2, e2 in p2]:
...: d[expn] = d.get(expn,0)+coef
...: return sorted([(c, e) for e, c in d.items()], key=lambda t: -t[1])
In [28]: pmult(a, b)
Out[28]: [(1, 6), (2, 5), (6, 4), (10, 3), (14, 2), (12, 1), (15, 0)]