我被python中的多项式除法难住了。下面是我修改的代码。while循环无法工作。这段代码只输出原来的L为r，如果去掉while循环，只输出第一次除法的余数。我试了很多方法让它工作，但都失败了。任何建议都将非常感激。谢谢！我想输入任何随机的多项式。
def GetDegree(poly):
while poly and poly[-1] == 0:
poly.pop() # normalize
return len(poly)-1
def division(p1,p2):
d1 = GetDegree(p1)
d2 = GetDegree(p2)
if d2 < 0 or d1<0:
raise ZeroDivisionError
if d1 > d2:
S,L = p2,p1#obtain S with lower degree, L with higher degree
else:
S,L = p1,p2
d1 = GetDegree(L)
d2 = GetDegree(S)
while d1>0:
q = [0]*d1
d = [0]*(d1 - d2) + S#shift short towards right by d1-d2
mult = q[d1 - d2] = L[-1] / float(d[-1])#get the result by dividing the first term of the dividend by the highest term of the divisor
d = [coef*mult for coef in d]#multiply the above result by short
L = [fabs( coefL - coefd ) for coefL, coefd in zip(L, d)]#return a new long by subtracting long with d
d1 = GetDegree(L)#return new d1
r = L#return new long and keeping looping for there is no variable left and return as remainder
return r
我想输入任意随机多项式进行计算。但是，当我修改后，结果还是不对。下面是我运行的测试：num:[2,1,1,1] den:[1,1,2]。打印结果是：quote:[0.25,0.5]，rem:[1.75,0.25]。这是我根据PM 2Ring的回答，针对输入的情况修改的代码。
def normalize(poly):
while poly and poly[-1] == 0:
poly.pop()
if poly == []:
poly.append(0)
def poly_divmod(num, den):
#Create normalized copies of the args
num = num[:]
normalize(num)
den = den[:]
normalize(den)
if len(num) >= len(den):
#Shift den towards right so it's the same degree as num
shiftlen = len(num) - len(den)
den = [0] * shiftlen + den
else:
return [0], num
quot = []
divisor = float(den[-1])
for i in range(shiftlen + 1):
#Get the next coefficient of the quotient.
mult = num[-1] / divisor
quot = [mult] + quot
#Subtract mult * den from num, but don't bother if mult == 0
#Note that when i==0, mult!=0; so quot is automatically normalized.
if mult != 0:
d = [mult * u for u in den]
num = [u - v for u, v in zip(num, d)]
num.pop()
den.pop(0)
normalize(num)
return quot, num
def test(num, den):
print ("%s / %s ->" % (num, den))
q, r = poly_divmod(num, den)
print ("quot: %s, rem: %s\n" % (q, r))
return q, r
def main():
degree = int(input('Enter the degree of your polynomial 1:'))
num = []
for i in range (0,degree+1):
coefficient = int(input('Enter the coefficient for x^ %i ? ' %i))
num.append(coefficient)
degree = int(input('Enter the degree of your polynomial 2:'))
den = []
for i in range (0,degree+1):
coefficient = int(input('Enter the coefficient for x^ %i ? ' %i))
den.append(coefficient)
test(num, den)
if __name__ == '__main__':
main()
我稍微修改了你的代码，所以现在它返回的是商和余数。
FWIW，创建一个多项式类是相当容易的，然后你可以使用标准运算符和函数进行多项式运算......。
#! /usr/bin/env python
''' Polynomial long division
From http://stackoverflow.com/questions/26173058/division-of-polynomials-in-python
A polynomial is represented by a list of its coefficients, eg
5*x**3 + 4*x**2 + 1 -> [1, 0, 4, 5]
Modified by PM 2Ring 2014.10.03
'''
def normalize(poly):
while poly and poly[-1] == 0:
poly.pop()
if poly == []:
poly.append(0)
def poly_divmod(num, den):
#Create normalized copies of the args
num = num[:]
normalize(num)
den = den[:]
normalize(den)
if len(num) >= len(den):
#Shift den towards right so it's the same degree as num
shiftlen = len(num) - len(den)
den = [0] * shiftlen + den
else:
return [0], num
quot = []
divisor = float(den[-1])
for i in xrange(shiftlen + 1):
#Get the next coefficient of the quotient.
mult = num[-1] / divisor
quot = [mult] + quot
#Subtract mult * den from num, but don't bother if mult == 0
#Note that when i==0, mult!=0; so quot is automatically normalized.
if mult != 0:
d = [mult * u for u in den]
num = [u - v for u, v in zip(num, d)]
num.pop()
den.pop(0)
normalize(num)
return quot, num
def test(num, den):
print "%s / %s ->" % (num, den)
q, r = poly_divmod(num, den)
print "quot: %s, rem: %s\n" % (q, r)
return q, r
def main():
num = [1, 5, 10, 10, 5, 1]
den = [1, 2, 1]
test(num, den)
num = [5, 16, 10, 22, 7, 11, 1, 3]
den = [1, 2, 1, 3]
quot = [5, 1, 3, 0, 1]
rem = [0, 5]
q, r = test(num, den)
assert quot == q
assert rem == r
if __name__ == '__main__':
main()
from sympy import Symbol
from sympy import div
x = Symbol('x')
def Poly(p,mod):
q,r = div(p,mod,x) #quotient and remainder polynomial division by modulus mod
return r.as_poly(x,domain='GF(2)') #Z_2
m = x**8 + x**4 + x**3 + x + 1
p = x**6 + x**5 + x + 1
print Poly(p*p, m)
如果你愿意使用一个外部库（我看到上面提到的sympy），numpy可以很容易的为你解决这个问题。numpy.polydiv 是你所需要的。https:/numpy.orgdocstablereferencegeneratednumpy.polydiv.html。