# -*- coding: utf-8 -*-

"""
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

    # on s'assure que le polynôme de plus haut degré est q
    if deg_p > deg_q:
        (p, q, deg_p, deg_q) = (q, p, deg_q, deg_p)

    # on initialise le polynôme somme
    sum = [0] * (deg_q + 1)

    # et on calcule les coefficients de la somme
    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

    # initialisation du produit
    prod = [0] * (deg_p + deg_q + 1)

    # calcul des coefficients du produit
    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

# Tests
P = [-1, 1]                # P(X) = X - 1
Q = [ 1, 1,  1, 1,  1, 1]  # Q(X) = X^5 + X^4 + X^3 + X^2 + X + 1
R = [-1, 1, -1, 1, -1, 1]  # R(X) = X^5 - X^4 + X^3 - X^2 + X - 1

# Affichage des listes de coefficients
print "P =", P
print "Q =", Q
print "R =", R

# Affichage des résultats d'opérations
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)