##
## PARTIE I
##

#Q1
# [1]*7 = [1,1,1,1,1,1,1] = 1+X+X^2+X^3+X^4+X^5+X^6

#Q2
def evaluation(L,x):
    n = len(L)
    P = L[0]  
    for k in range(1,n):
        P = P + L[k] * x**k
    return P

#Q3 complexité O(n^2)

#Q4
def reduit(L):
    L_reduite = []
    pos = len(L) - 1 # dernière position
    while L[pos] == 0:
        pos = pos - 1 # tant qu'on trouve un 0 à droite, on recule
    for i in range(pos+1): # on recopie la liste jusqu'à la dernière valeur non nulle
        L_reduite.append( L[i] )
    return L_reduite
    
def reduit2(L):
    if L==[]:
        return []
    if L==[0]:
        return []
    else :
        if L[len(L)-1]==0:
            return reduit2(L[:len(L)-1])
    
        
#Q5
def deg(L):
    return len(reduit(L)) - 1

#Q6
def ajout_zero(L, n):
    for i in range(n):
        L.append(0)
    return L

#Q7
def somme(L1, L2):
    m = max( len(L1), len(L2))
    L1 = ajout_zero(L1, m-len(L1))  # on complète en 0 si nécessaire pour avoir deux listes de même taille
    L2 = ajout_zero(L2, m-len(L2))
    S = [] # polynôme somme
    for i in range(m):
        S.append( L1[i] + L2[i])
    return S
    
#Q8
def produit(L1, L2):
    m = len(L1) + len(L2) - 1
    L1 = ajout_zero(L1, m-len(L1))
    L2 = ajout_zero(L2, m-len(L2))
    P = [] # polynôme produit
    for i in range(m):
        c = 0 # coefficient i du polynôme produit
        for k in range(i+1):
            c = c + L1[k] * L2[i-k]
        P.append(c)
    

##
## PARTIE II
##
    
def horner(C,x):
    n = len(C)
    Q = C[0]
    for k in range(1,n):
        Q = Q * x +C[k]
    return Q
    
P = [4,-8,-7,-1,4,5,6,10]
print(horner(P,0))

import time

def temps(n):   # compare le temps d'exécution entre les deux méthodes Evaluation classique / Horner
    h = []
    e = []
    for i in range(1,n+1):
        start_time = time.time()
        horner([1]*i,2)
        h.append(time.time()-start_time)
        start_time = time.time()
        evaluation([1]*i,2)
        e.append(time.time()-start_time)
    return e,h


##
## Partie III
##

def puissance(x: float, n:int) -> float:
    ''' calcul de x^n '''
    p = 1
    for i in range(n):
        p = p * x
    return p

def puissance_rec(x: float, n: int) -> float:
    if n==0:
        return 1
    else:
        return x*puissance_rec(x, n-1)

def expo_rapide(x: float, n:int) -> int:
    if n == 1:
        return x
    elif n % 2 == 0:
        return expo_rapide(x*x, n//2)
    else:
        return x*expo_rapide(x*x, (n-1)//2)