###########################################
###########################################
## TP 06 : Polynômes
###########################################
###########################################

## Importations

# rien à importer

## Exercice 1 : degré d'un polynôme

def deg(P) :
    n = len(P)-1
    while P[n] == 0 and n >= 0 :
        n -= 1
    return n

P1 = [-5,2,0,3,0]
P2 = [0,0,0]

assert deg(P1) == 3
assert deg(P2) == -1

## Exercice 2 : évaluation d'un polynôme

def eval(P,x) :
    n = len(P)
    S = 0
    for k in range(n) :
        S += P[k] * x**k
    return S

assert eval(P1,0) == -5
assert eval(P1,1) == 0
assert eval(P1,2) == 23
assert eval(P2,3) == 0

## Exercice 3 : somme de polynômes

def add(P,Q) :
    R = []
    d1,d2 = len(P), len(Q)
    for k in range(min(d1,d2)) :
        R.append( P[k]+Q[k] )
    if d1 > d2 :
        for k in range(d2,d1) :
            R.append(P[k])
    else :
        for k in range(d1,d2) :
            R.append(Q[k])
    return R

P3 = [1,0,3]
P4 = [0,5,2,1]
P5 = [1,2,3,4,5]

assert add(P3,P4) == [1,5,5,1]
assert add(P3,P5) == [2,2,6,4,5]
assert add(P4,P5) == [1,7,5,5,5]

## Exercice 4 : multiplication scalaire

def scal_mult(P,alpha) :
    R = []
    for elt in P :
        R.append(alpha*elt)
    return R

P6 = [1,2,3]
a = 2

assert scal_mult(P6,a) == [2,4,6]

## Exercice 5 : formule du produit de polynômes

# Soient P = SUM{k=0,n} ak.X**k et Q = SUM{k=0,p} bk.X**k
#
# Alors R = P x Q est défini par :
#
#     R = SUM{k=0,n+p} ck.X**k,  où ck = SUM_{i=0,k} ai*b_{k-i}

## Exercice 6 : produit de polynômes

def multiply(P,Q) :
    R = []
    p = len(P)
    q = len(Q)
    for k in range(p+q-1) :
        ck = 0
        for i in range(k+1) :
            if i < p : ai = P[i]
            else : ai = 0
            if k-i < q : bj = Q[k-i]
            else : bj = 0
            ck += ai*bj
        R.append(ck)
    return R

assert multiply(P6,P6) == [1,4,10,12,9]
assert deg(multiply(P6,P2)) == -1

## Exercice 7 : polynôme dérivé

def derive(P) :
    D = []
    for i in range(1,len(P)) :
        D.append(P[i]*i)
    return D

P7 = [3,0,5,2]

assert derive(P7) == [0,10,6]

## Exercice supplémentaire : composée de polynômes

def puissance(Q,n) :
    '''renvoie une liste representant Q**n'''
    if n == 0 :
        return [1]
    return multiply(Q,puissance(Q,n-1))

assert puissance(P6,2) == [1,4,10,12,9]

def compose(P,Q) :
    '''renvoie une liste representant P rond Q'''
    n = len(P)
    C = []
    for k in range(n) :
        Qk = puissance(Q,k)
        akQk = scal_mult(Qk,P[k])
        C = add(C,akQk)
    return C

assert compose(P6,P3) == [6,0,24,0,27]
assert compose(P4,P3) == [8,0,36,0,45,0,27]