#Exo 1
#1) On crée un compteur qui compte les 0, et on remplit une liste vide de 0. Pas besoin de compteur de 1 : ce sont les autres éléments
def tri_liste_binaire(L): 
    n=len(L)
    compteur_0=0
    L_triee=[]
    for i in range(n): 
        if L[i]==0:
            compteur_0+=1
            L_triee.append(0)
    for i in range(n-compteur_0): 
        L_triee.append(1)
    return(L_triee)

# La complexite est en O(n) car on des boucles for simples

#2) Voir cours

#Exo 2
#1)On peut utiliser len(L)-1

#2)
def etendre(L,n):
    if n<=len(L): 
        return(L)
    else: 
        for i in range(n-len(L)):
            L.append(0)
        return(L)

#3)
def somme(L1,L2): 
    n1=len(L1)
    n2=len(L2)
    L1=etendre(L1,n2)
    L2=etendre(L2,n1)
    Lsomme=[]
    for i in range(max(n1,n2)): 
        Lsomme.append(L1[i]+L2[i])
    return Lsomme

#4)
def evaluation_recursive(L,x):
    if len(L)==1: #on aurait pu commencer avec la liste vide, tout dépend des conventions. 
        return L[0]
    else:
        return L[0]+x*evaluation_recursive(L[1:],x)

#5)
def produit(L1,L2):
    n1=len(L1)
    n2=len(L2)
    L1=etendre(L1,n1+n2)
    L2=etendre(L2,n1+n2)
    Lprod=[]
    for i in range(n1+n2-1): #Assez subtil ce -1 : essayez de le voir sur des exemples
        ci=0
        for k in range(i+1):
            ci=ci+L1[k]*L2[i-k]
        Lprod.append(ci)
    return Lprod