leçon 2: polynômes à une indéterminée

Le fichier de ce qui suit est ici. 
Marc m'a déjà corrigé ma copie là :)

# Polynômes à une indéterminée: \( \mathbb{R} [X] \) 

# 1. Représentation des polynômes
# on représente le polynôme \(a_nX^n+...a_1X+a_0\) par la liste de ses
# coefficients jusqu'à un certain degré, étant entendu qu'après ce degré
# les coefficients sont nuls
# on les ordonne par degré croissant:
# \([a_0,a_1,...,a_n]\)
# par exemple, soit p1 le polynôme \(2X^2-3X+1\)

# en python une liste est une suite d'éléments entre crochets,
# séparés par des virgules
p1=[1,-3,0,2]   # le polynôme 2X^3-3X+1
p2=[1,-3,0,2,0] # le même polynôme
p3=[1,3,5]      # le polynôme 5X^2+3X+1

# p1 et p2 représentent le même polynôme, mais pour python ce sont des listes différentes.

# quelques fonctions utiles sur les listes:
# range(n) produit la liste des entiers de 0 à n-1: [0,1,2,...,n-1]
# len(s) donne la longueur d'une liste s
# + concatène deux listes

# on accède à l'élément de rang k de la liste p par la syntaxe p[k]
# le premier rang étant le rang 0
p1[0]
p1[1]
p1[2]

# ca tombe bien pour les polynômes: p[k] donne le coefficient de X^k dans p

# mais on peut désirer connaître le coefficient de p pour un degré donné sans connaître le degré de p, il faut donc écrire une fonction qui calcule cela

def coef(p,k):
  if k<len(p): return p[k]
  else: return 0

# calculons le degré d'un polynôme: c'est le plus grand degré tel que le coefficient correspondant est non nul, et il est borné par la longueur de la liste qui représente p

def deg(p):
  d=0
  # l'instruction suivante est une boucle for:
  # elle exécute les instructions qui la suivent et qui sont décalées
  # par rapport à elle,
  # ceci pour chaque valeur de k dans la liste qui est donnée
  # ici c'est range(len(p))
  for k in range(len(p)):
    if p[k]<>0: d=k # cette instruction est décalée par rapport à
                    # l'instruction for:
                    # elle est exécutée pour chaque valeur de k
  return d # cette instruction n'est pas décalée par rapport à
           # l'instruction for: elle est exécutée quand la boucle for
           # est terminée

deg(p1)
deg(p2)
deg(p3)

# 2. Addition des polynômes

# pour calculer p+q, on additionne les coefficients de même degré
# cela correspond à additionner les termes de même rang des listes représentant
# les polynômes 

def plus_poly(p,q):
  # la variable res va contenir la liste représentant le polynôme somme
  # de p et q, on va lui ajouter des éléments au fur et à mesure que l'on 
  # va calculer les sommes des coefficients de p et q, degré par degré
  # au début elle est vide:
  res=[]
  # parcourons les deux listes p et q, degré par degré
  # du degré 0 au degré maximum, qui est max(deg(p),deg(q))
  # ne pas oublier le range(n) se termine avec n-1 et pas n
  for k in range(max(deg(p),deg(q))+1):
    res=res+[coef(p,k)+coef(q,k)]
  return res

plus_poly(p1,p3)

# plus concis:
# une expression [f(k) for k in A] va calculer la liste des valeurs de f(k)
# pour chaque k de la liste A

def plus_poly(p,q):
  return [coef(p,k)+coef(q,k) for k in range(max(deg(p),deg(q))+1)]

plus_poly(p1,p3)

# 3. Affichage des polynômes

# voir un polynôme sous sa forme en liste n'est pas très parlant, 
# on va programmer qui affiche un polynôme comme on en a l'habitude en maths

# nous aurons besoin de fonctions d'une des bibliothèques python
import sys

# on définit une fonction qui imprime à l'écran une suite de caractères
# (on dit <<chaîne>> en informatique, sans le retour à la ligne que met 
# la fonction standard print

def imprime_chaine(s):
  sys.stdout.write(s)

# et d'une fonction qui fait demême avec un nombre
# pour cela on convertit le nombre en chaîne avec la fonction str

def imprime_nombre(x):
  imprime_chaine(str(x))

# allons-y

def imprime_poly(p):
  deja=False # pour savoir si on déjà imprimé quelque-chose du polynôme
  for k in range(deg(p)+1): 
    c=coef(p,k)
    if c<>0: # toutes les instructions jusqu'à l'instruction deja=True
             # sont décalées: elles sont donc exécutées si c<>0
             # celles d'après ne le sont plus donc sont exécutée 
             # indépendamment de la valeur de c
      if c>0: 
        if deja: imprime_chaine('+')
      else: imprime_chaine('-')
      c=abs(c)
      if c<>1 or k==0: imprime_nombre(c)
      if k>=1: imprime_chaine('X')
      if k>1: 
        imprime_chaine('^') 
        imprime_nombre(k)   
      deja=True
  # fin de la boucle for, car il n'y a plus de décalage 
  # par rapport à l'instruction for 
  if deja==False: imprime_nombre('0')
  imprime_chaine('\n')

imprime_poly(p1)
imprime_poly(p3)
imprime_poly([])
imprime_poly([0,-1])

# 4. Multiplication

# 4.1. Multiplication par une constante a

def mult_constante(a,p):
  return [a*coef(p,k) for k in range(deg(p)+1)]

# 4.2. Multiplication par un monôme X^d

def mult_monome(p,d):
  return ([0 for k in range(d)]+p)

# 4.2. Mutiplication des polynômes

def mult_poly(p,q):
  res=[]
  for k in range(deg(p)+1):
    res=plus_poly(res,
                  mult_constante(coef(p,k),
                                 mult_monome(q,k)))
  return res

p4=[1,1]
imprime_poly(p4)
imprime_poly(mult_poly(p4,p4))

# 4.4. Puissances d'un polynôme

def puis_poly(p,n):
  if n==0: return [1]
  else: return mult_poly(p,puis_poly(p,n-1))

for n in range(13):
  imprime_poly(puis_poly(p4,n))

imprime_poly(puis_poly(p4,500))