# TD 18 correction (partie informatique) : Polynômes
# BCPST1 2025-2026
# Lycée Hoche, Versailles
# L.-C. LEFÈVRE

#%% exercice 13

def degré(P):
    # le degré de P…
    n = len(P) - 1
    # … sauf s'il y a des zéros *à la fin* : dans ce cas diminuer le degré de 1
    while n >= 0 and P[n] == 0:
        n = n - 1
    return n
# à la fin le degré du polynôme nul est *naturellement* -1

# Dans la suite, une convention intéressante est de noter par n non pas la longueur des liste, mais leur longueur moins un (le degré « présumé » du polynôme).

def produit_constante(P, t):
    n = len(P) - 1
    R = [0 for _ in range(n+1)]
    for i in range(n+1):
        R[i] = t * P[i]
    return R

def somme(P, Q):
    n = len(P) - 1
    m = len(Q) - 1
    if n >= m:
        # le résultat est de degré n
        R = [0 for _ in range(n+1)]
        # somme là où P, Q ont des coefficients communs
        for i in range(m+1):
            R[i] = P[i] + Q[i]
        # *puis* rajouter les coefficients de P tout seul
        for i in range(m+1, n+1):
            R[i] = P[i]
        return R
    else:
        # sinon, tout refaire mais c'est Q de plus grand degré
        # grosse astuce (réservé aux professionnels)
        return somme(Q, P)

def produit(P, Q):
    n = len(P) - 1
    m = len(Q) - 1
    # le résultat, polynôme nul de la bonne taille
    r = n + m
    R = [0 for _ in range(r+1)]
    # double boucle
    for i in range(n+1):
        for j in range(m+1):
            R[i+j] = R[i+j] + P[i] * Q[j]
    return R

def puissance_iteratif(P, m):
    R = [1]
    for _ in range(m):
        R = produit(R, P)
    return R

def puissance_recursif(P, m):
    if m == 0:
        return [1]
    else:
        Q = puissance(P, m-1)
        return produit(P, Q)

puissance = puissance_iteratif

def évalue(P, u):
    n = len(P) - 1
    s = 0
    for i in range(n+1):
        s = s + P[i] * u**i
    return s

# idem que évalue : c'est la somme des P[i] * Q**i mais tout en opération sur les polynômes
def compose(P, Q):
    n = len(P) - 1
    R = []
    for i in range(n+1):
        R = somme(R, produit_constante(puissance(Q, i), P[i]))
    return R

def dérive(P):
    n = len(P) - 1
    # le résultat est de degré n-1
    r = n - 1
    R = [0 for _ in range(r+1)]
    for i in range(r+1):
        R[i] = (i+1) * P[i+1]
    return R

# dérivées supérieures : exactement comme pour passer de produit à puissance !
def rdérive_iteratif(P, r):
    R = P
    for _ in range(r):
        R = dérive(R)
    return R

def rdérive_recursif(P, r):
    if r == 0:
        return P
    else:
        R = rdérive_recursif(P, r-1)
        return dérive(R)

rdérive = rdérive_iteratif

#%% exercice 13.1

def factoriel(n):
    if n == 0:
        return 1
    else:
        return n * factoriel(n-1)

def Legendre(n):
    return produit_constante(rdérive(puissance([-1, 0, 1], n), n), 1 / 2**n * factoriel(n))

# test
for i in range(10):
    print(Legendre(i))

#%% exercice 13.2

def Tchebychev(n):
    # u représente T_(i) et v représente T_(i+1) dans la boucle
    u = [1]
    v = [0, 1]
    for i in range(n):
        w = somme(produit([0, 2], v), produit_constante(u, -1))
        u = v
        v = w
    return u

for i in range(10):
    print(Tchebychev(i))

#%% petit bonus : formater l'affichage
# largement améliorable selon les besoins

def affiche(P):
    n = len(P)-1
    for i in range(n+1):
        print(f"{int(P[i]):+}X^{i} ", end="")
    print("")

for i in range(10):
    affiche(Legendre(i))

for i in range(10):
    affiche(Tchebychev(i))

#%% exercice 14

# le degré est donc le maximum de tous les coefficients rencontrés
# la variable d stocke le maximum "jusque là" dans le boucle
def degré(P):
    d = -1
    for i in P.keys():
        if P[i] != 0 and i > d:
            d = i
    return d

def produit_constante(P, t):
    R = {}
    for i in P.keys():
        R[i] = t * P[i]
    return R

def somme(P, Q):
    # copie d'abord P d'un seul coup
    R = P.copy()
    # puis lui ajoute R
    for i in Q.keys():
        if i in R.keys():
            R[i] = R[i] + Q[i]
        else:
            R[i] = Q[i]
    return R

# fait des produits de monômes "en vrac"
def produit(P, Q):
    R = {}
    for i in P.keys():
        for j in Q.keys():
            k = i + j
            c = P[i] * Q[j]
            if k in R.keys():
                R[k] = R[k] + c
            else:
                R[k] = c
    return R

# aussi facile qu'avec des listes, même si les monômes ne sont pas dans l'ordre !
def évalue(P, u):
    s = 0
    for i in P.keys():
        s = s + P[i] * u**i
    return s

def dérive(P):
    R = {}
    for i in P.keys():
        # attention, cette fois on ne peut pas écrire R[i] = (i+1) * P[i+1] car là c'est vraiment i qui est une clé de P
        # on crée donc la clé i-1 dans R : i * P[i] devient le coefficient de x^(i-1)
        # mais attention si i = 0
        if i > 0:
            R[i-1] = i * P[i]
    return R