"""
Un polynôme est représenté en python par la liste de ses coefficients, du
coefficient constant à celui de plus haut degré ; par exemple :
X - 1 est représenté par [-1, 1]
X^2 - 1 est représenté par [-1, 0, 1]
-X^3 + 3X^2 - 3X + 1 est représenté par [1, -3, 3, -1]
On a donc len(P) = deg(P) + 1
"""
def add_poly(p, q):
deg_p = len(p) - 1
deg_q = len(q) - 1
if deg_p > deg_q:
(p, q, deg_p, deg_q) = (q, p, deg_q, deg_p)
sum = [0] * (deg_q + 1)
for i in range(0, deg_p+1):
sum[i] = p[i] + q[i]
for i in range(deg_p+1, deg_q+1):
sum[i] = q[i]
return sum
def mult_poly(p, q):
deg_p = len(p) - 1
deg_q = len(q) - 1
prod = [0] * (deg_p + deg_q + 1)
for k in range(0, deg_p + deg_q + 1):
for i in range(max(0, k - deg_q), min(k, deg_p)):
prod[k] += p[i]*q[k-i]
return prod
P = [-1, 1] Q = [ 1, 1, 1, 1, 1, 1] R = [-1, 1, -1, 1, -1, 1]
print "P =", P
print "Q =", Q
print "R =", R
print "P + Q =", add_poly(P, Q)
print "Q + R =", add_poly(Q, R)
print "P * Q =", mult_poly(P, Q)
print "Q * R =", mult_poly(Q, R)
print "P * R =", mult_poly(P, R)