例如3x ^ 4 - 17x ^ 2 - 3x + 5.多项式的每个项可以表示为一对整数(系数,指数)。多项式本身就是这样的对的列表
[(3,4), (-17,2), (-3,1), (5,0)]
为多项式,如图所示。
零多项式0表示为空列表[]
,因为它没有非零系数的项。
我想编写两个函数来添加和乘以两个输入多项式,并使用相同的元组表示(系数,指数):
addpoly(p1, p2)
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
作为suggested中的comments,将多项式表示为指数的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)
(事实上,如果你坚持使用Counter表示,你可以只使用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)
我想出了一个解决方案,但我不确定它是否已经过优化!
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
这个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