############################
#   Thème 6 : Polynômes    #
############################

## Polynômes pour tester

P1 = [1,0,2,3]          # P1 = 3X^3 + 2X² + 1
P2 = [1,2,3,4,0,0,0]    # P2 = 4X^3 + 3X² + 2X + 1
P3 = [0,0,0,0,0]        # P3 = 0
P4 = [1,0,3]
P5 = [0,5,2,1]
P6 = [1,2,3]

## I) Degré
# exercice 64

def deg(P) :
    n = len(P)
    i = n-1
    while i>=0 :
        if P[i] != 0 :
            return i
        i -= 1
    return i

assert deg(P1) == 3
assert deg(P2) == 3
assert deg(P3) == -1
assert deg([]) == -1

## II) Evaluation
# exercice 65

def eval(P,x) :
    s = 0
    for i in range(len(P)) :
        s += P[i]*x**i
    return s

assert eval(P1,3) == 100
assert eval(P2,2) == 49
assert eval(P3,4) == 0

## III) Somme
# exercice 66

def add(P,Q) :
    R = []
    n = len(P)
    m = len(Q)
    for i in range(max(n,m)) :
        if i>=n :
            R.append(Q[i])
        elif i>=m :
            R.append(P[i])
        else :
            R.append(P[i]+Q[i])
    return R

assert add(P4,P5) == [1,5,5,1]

## IV) Multiplication par un scalaire
# exercice 67

def scal_mult(P,alpha) :
    R = []
    for elt in P :
        R.append(alpha*elt)
    return R

assert scal_mult(P6,2) == [2,4,6]

## V) Produit de 2 polynômes
# exercice 69

def multiply(P,Q) :
    n = deg(P)
    m = deg(Q)
    R = []
    for i in range(n+m+1) :
        s = 0
        for k in range(i+1) :
            if k > n or i-k > m :
                r = 0
            else :
                r = P[k]*Q[i-k]
            s += r
        R.append(s)
    return R

assert multiply([1,1],[1,-1]) == [1,0,-1]
assert multiply(P1,P3) == [0,0,0]
assert multiply(P4,P5) == [0,5,2,16,6,3]

## VI) Dérivation
# exercice 70

def deriv(P) :
    n = deg(P)
    R = []
    for i in range(1,n+1) :
        R.append(i*P[i])
    return R

assert(deriv(P1)) == [0,4,9]

# exercice 71

def deriv_n_fois(P,n) :
    R = P
    for _ in range(n) :
        R = deriv(R)
    return R

assert deriv_n_fois(P1,1) == [0,4,9]
assert deriv_n_fois(P1,2) == [4,18]
assert deriv_n_fois(P1,3) == [18]
assert deriv_n_fois(P1,4) == []

## VII) Egalité de 2 polynômes
# exercice 72

def is_equal(P,Q) :
    n = deg(P)
    m = deg(Q)
    if n != m :
        return False
    for i in range(n+1) :
        if P[i] != Q[i] :
            return False
    return True

assert is_equal([1,-1,0,0], [1,-1])
assert not is_equal([1,-1,0,3], [2,-1,0,3])