[SIZE=3]I. Introduction
On souhaite créer une fonction permettant de calculer le plus grand commun diviseur ou PGCD entre deux nombres entiers à l'aide de l'algorithme d'Euclide.
Ensuite, toujours en se basant sur cet algorithme, on va créer une autre fonction qui pourra déterminer le PGCD de deux polynômes.
II. Définitions mathématiques
II-A. PGCD de nombres entiers
D'après Wikipedia, en mathématiques, le PGCD de nombres entiers différents de zéro est, parmi les diviseurs communs à ces entiers, le plus grand d'entre eux.
Par exemple, les diviseurs positifs de 30 sont, dans l'ordre : 1, 2, 3, 5, 6, 10, 15 et 30. Ceux de 18 sont 1, 2, 3, 6, 9 et 18.
Les diviseurs communs de 30 et 18 étant 1, 2, 3 et 6, leur PGCD est 6. Ce qui se note : PGCD(30, 18) = 6.
Les diviseurs communs à plusieurs entiers sont les diviseurs de leur PGCD. Connaître le PGCD de deux nombres entiers non nuls a et b permet de simplifier la fraction a/b.
Il est possible de le déterminer par divers raisonnements, dont l'algorithme d'Euclide.
II-B. PGCD de polynômes
On va simplement transposer pour les polynômes l'algorithme d'Euclide servant à trouver le PGCD de deux nombres entiers.
Toutefois, comme il y a une infinité de PGCD possibles avec les polynômes, pour avoir un PGCD unique, on choisira par convention le polynôme unitaire, polynôme non nul et dont le coefficient dominant vaut 1.
Connaître le PGCD de deux polynômes non nuls A et B permet de simplifier la fraction A/B.
III. Algorithme d'Euclide
III-A. PGCD de deux nombres entiers
Ainsi, selon Wikipedia, l'algorithme d'Euclide sur deux nombres entiers positifs a et b avec a > b ⩾ 0 procède comme suit :
- si b = 0, l'algorithme termine et rend la valeur a ;
- sinon, l'algorithme calcule le reste r de la division euclidienne de a par b, puis recommence avec a := b et b := r.
Formellement l'algorithme d'Euclide construit une suite finie d'entiers (rn) par récurrence double :
- r0 = a, r1 = b ;
- pour n ⩾ 1, rn+1 est le reste de la division euclidienne de rn-1 par rn, en particulier rn+1 < rn.
La suite (rn) est une suite strictement décroissante d'entiers positifs à partir du rang 1 : elle est donc finie et s'arrête au premier n tel que rn = 0.
Le tableau suivant montre le calcul du PGCD de 21 et 15. On réalise la division euclidienne de a = 21 et b = 15 : le quotient est 1 et le reste 6.
L'algorithme continue avec a := b et b := le précédent reste, jusqu'à trouver un reste nul. L'algorithme s'arrête alors et retourne le dernier reste non nul trouvé, ici r3 = 3 qui est bien le PGCD de 21 et 15 :
III-B. PGCD de polynômes
On procédera de la même façon pour le calcul du PGCD des polynômes A et B :
- si B = 0 alors PGCD(A, B) = A ;
- sinon, l'algorithme calcule le reste R de la division euclidienne des polynômes A et B, puis recommence avec A := B et B := R.
Pour avoir plus d'information sur la division d'un polynôme, je vous invite à consulter la page Division d'un polynôme.
IV. Implémentation en Python
On va chercher comme d'habitude à écrire du code le plus lisible possible, sans chercher forcément à l'optimiser.
IV-A. PGCD de nombres entiers
A partir de l'algorithme décrit précédemment on obtient facilement la fonction récursive :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 | def PGCD(a, b): # si b=0 if (b==0): # renvoi de a return a else: # sinon # calcul du reste r de la division de a par b r = a % b # appel de la fonction PGCD pour a=b et b=r return PGCD(b, r) |
On laisse le choix à chacun de traduire ensuite ce code en fonction itérative.
Testons maintenant cette fonction :
| Code Python : | Sélectionner tout |
1 2 3 4 5 | # calcul du PGCD des entiers 21 et 15 gcd = PGCD(21, 15) # affiche le résultat print("PGCD(21, 15) = " + str(gcd)) |
Le code affiche :
PGCD(21, 15) = 3
IV-B. PGCD de polynômes
On utilise à nouveau notre classe Polynome dans laquelle on va ajouter une méthode pour réaliser une division euclidienne entre deux polynômes :
On donne maintenant le code complet de la méthode permettant de réaliser cette division en surchargeant l'opérateur « / » :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | class Polynome: ... def __truediv__(self, other): # méthode permettant de redéfinir l'opérateur « / » pour 2 polynômes # si le degré de self est inférieur au degré de other if self.degre()<other.degre(): # on renvoie (0, self) : q=0, r=self return (Polynome([0]), self) # sortie de la fonction # polynôme self représentant au départ le reste r r = Polynome(self.coefs) # degré du polynôme représentant le quotient q degre = r.degre() - other.degre() # initialisation du polynôme q : [0, 0, 1] -> ... + X^2 q = Polynome([0]*degre + [1]) # tant que le degré mini des termes du polynôme q est supérieur ou égal à 0, et que r n'est pas égal à 0. while (degre>=0) and (r.coefs[-1]!=0): # coefficient du nouveau terme du polynôme q coef = r.coefs[-1] / other.coefs[-1] # affectation du coefficient au terme q.coefs[degre] = coef # on multiplie le polynôme other par le polynôme coef*(x^degre) p = other * (coef, degre) # soustraction des polynômes r et p r = r - p # degré du nouveau terme du polynôme q degre = r.degre() - other.degre() # renvoi le couple (q, r) représentant le quotient et le reste de la division return (q, r) |
On doit donc d'abord comparer les degrés des polynômes p1 = self et p2 = other au début du code.
Si le degré de p1 est inférieur au degré de p2, alors q = 0 et r = p1,
sinon, on procède à la division des deux polynômes pour obtenir q et r.
Testons cette méthode :
| Code : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 | # création du polynôme p1 = (1 + X)(2 + X) = 2 + 3X + X^2
p1 = Polynome([1, 1])*Polynome([2, 1])
# création du polynôme p2 = 1 + 2X + X^2 = (1 + X)^2
p2 = Polynome([1, 2, 1])
# division euclidienne : p1 = p2*q + r
q, r = p1 / p2
# affiche le quotient q et le reste r de la division
print("q = " + str(q))
print("r = " + str(r)) |
q = 1.0
r = 1.0 + X
On peut maintenant créer notre fonction permettant de déterminer le PGCD entre deux polynômes :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | def PGCD_POLY(A, B): # si B=0 if (B==Polynome([0])): # par convention on choisit de renvoyer le polynôme unitaire, polynôme non nul et dont le coefficient dominant vaut 1 : coef = 1.0/A.coefs[-1] # multiplication de A par coef A = A*(coef,0) # renvoi de A return A else: # détermination du quotient Q et du reste R de la division de A par B Q, R = A / B # appel de la fonction PGCD pour A=B et B=R return PGCD_POLY(B, R) |
Testons enfin notre fonction :
| Code : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 | # création du polynôme p1 = (1 + X)(2 + X) = 2 + 3X + X^2
p1 = Polynome([1, 1])*Polynome([2, 1])
# création du polynôme p2 = 1 + 2X + X^2 = (1 + X)^2
p2 = Polynome([1, 2, 1])
# calcul du PGCD des polynômes p1 et p2
gcd = PGCD_POLY(p1, p2)
# affiche le résultat
print("PGCD(p1, p2) = " + str(gcd)) |
PGCD(p1, p2) = 1.0 + X
IV-C. Application : simplification de fraction
Supposons que l'on souhaite connaître la limite :
On voit facilement qu'on aboutit à une forme indéterminée 0/0.
Pour lever cette indétermination on identifie d'abord le PGCD entre le numérateur et le dénominateur (x - 2), pour ensuite simplifier la fraction :
On obtient ainsi la limite égale à 13/7.
Mise en œuvre en Python :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | # création du polynôme p1 = -10 + X + X^3 p1 = Polynome([-10, 1, 0, 1]) print("p1 = " + str(p1)) # création du polynôme p2 = -6 - X + 2X^2 p2 = Polynome([-6, -1, 2]) print("p2 = " + str(p2)) print() print("Limite de p1/p2 quand X -> 2 = 0/0\n") # calcul du PGCD des polynômes p1 et p2 gcd = PGCD_POLY(p1, p2) # affiche le résultat print("PGCD(p1, p2) = " + str(gcd)) # simplification de p1 p1, r1 = p1 / gcd # simplification de p2 p2, r2 = p2 / gcd print() print("p1/p2 = ({0})/({1})".format(p1, p2)) print() print("Limite de p1/p2 quand X -> 2 = {0}/{1}\n".format(p1.eval(2),p2.eval(2)) |
Le code affiche :
p1 = -10 + X + X^3
p2 = -6 - X + 2.X^2
Limite de p1/p2 quand X -> 2 = 0/0
PGCD(p1, p2) = -2.0 + X
p1/p2 = (5.0 + 2.0.X + X^2)/(3.0 + 2.0.X^1)
Limite de p1/p2 quand X -> 2 = 13.0/7.0
On voit qu'on obtient le même résultat, les termes des polynômes sont simplement affichés dans l'ordre inverse.
IV-D. Module complet
On donne pour finir le code complet permettant d'effectuer les différents tests :
[CODE=Python]class Polynome:
def __init__(self, liste_coefs=[0]): # méthode constructeur de la classe
# on définit la liste des coefficients du polynôme [a0, a1, ..., an]
self.coefs = liste_coefs
# suppression si nécessaire des zéros en queue de liste de coefficients. Exemple : [2, 3, 1, 0, 0] -> [2, 3, 1]
self.reduire()
def __str__(self): # permet d'afficher le polynôme sous la forme 1 + 2x + 3x^2
s="" # initialisation de la chaîne de caractères
# on vérifie d’abord si le degré du polynôme est nul
if (len(self.coefs)-1==0):
return str(self.coefs[0])
else: # sinon
if self.coefs[0]!=0:
s=str(self.coefs[0]) + " + "
for i in range(1, len(self.coefs)): # parcours des indices des coefficients du polynôme : [a1, a2, ..., an]
if self.coefs[i]!=0: # si le coefficient de degré i n'est pas nul
if self.coefs[i]!=1: # si le coefficient de degré i est différent de 1
s+="{}.X^{} + ".format(self.coefs[i],i)
else: s+="X^{} + ".format(i)
# élimination des caractères en trop
s = s[:-3].replace("+ -", "- ").replace("X^1 ","X ").replace(" 1.X"," X")
if s[-2:]=="^1": s = s[:-2]
if s[:3]=="1.X": s = s[3:]
return s # on retourne l'expression du polynôme
def degre(self): # retourne le degré du polynôme
return (len(self.coefs)-1)
def __add__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes : (1 + 2x + x^2) + (1 + x) = 2 + 3x + x^2
# p1 = self, p2 = other
if len(other.coefs) >len(self.coefs): # si degré de p2 > degré de p1
liste_coefs = other.coefs[:]; n = len(self.coefs) # on copie les coefs du polynôme de degré le plus élevé et la longueur de la liste de coefs la plus petite.
else: liste_coefs = self.coefs[:]; n = len(other.coefs) # sinon, ...
for i in range(n): # parcours des indices de liste_coefs
liste_coefs[i] = self.coefs[i] + other.coefs[i] # addition des coefficients de degré i
return Polynome(liste_coefs) # renvoie le polynôme résultat de l'addition
def __sub__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes : (1 + 2x + x^2) + (1 + x) = 2 + 3x + x^2
# p1 = self, p2 = other
if len(other.coefs) >len(self.coefs): # si degré de p2 > degré de p1
liste_coefs = other.coefs[:]; n = len(self.coefs) # on copie les coefs du polynôme de degré le plus élevé et la longueur de la liste de coefs la plus petite.
else: liste_coefs = self.coefs[:]; n = len(other.coefs) # sinon, ...
for i in range(n): # parcours des indices de liste_coefs
liste_coefs[i] = self.coefs[i] - other.coefs[i] # addition des coefficients de degré i
return Polynome(liste_coefs) # renvoie le polynôme résultat de l'addition
def reduire(self):
# tant que le dernier élément de la liste est nul
while round(self.coefs[-1],12) == 0 and len(self.coefs)>1:
self.coefs.pop() # supprimer le dernier élément
for i in range(len(self.coefs)):
self.coefs[i] = round(self.coefs[i],12)
def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 polynômes : (1 + x) * (1 + 2x) = 1 + 3x + 2x^2
if isinstance(other,tuple):
coef = other[0]; degre = other[1]
liste_coefs = [0]*degre + self.coefs
for i in range(degre, len(liste_coefs)):
liste_coefs[i] = liste_coefs[i]*coef
else:
# initialisation de la liste des coefficients qu'avec des zéros
liste_coefs=[0]*(len(self.coefs)+len(other.coefs)-1) # exemple : [0, 0, 0]
for i1 in range(len(self.coefs)): # parcours des indices des coefs du polynôme n°1
for i2 in range(len(other.coefs)): # parcours des indices des coefs du polynôme n°2
# multiplication des coefficients d'indices i1 et i2
liste_coefs[i1+i2] = liste_coefs[i1+i2] + self.coefs[i1]*other.coefs[i2]
poly = Polynome(liste_coefs) # création de l'objet Polynome basé sur la liste
return poly # renvoie le polynôme résultat de la multiplication
def __pow__(self, n): # méthode permettant de redéfinir l'opérateur de puissance : self ** n
# on crée l'objet poly à partir d'une liste contenant un seul élément 1, élément neutre pour la multiplication des polynômes
poly = Polynome([1])
for i in range(n): # on multiplie n fois poly par self à l'aide de l'opérateur *
poly = poly*self # équivalent à : poly = poly.__mul__(self)
return poly # renvoie le polynôme résultat de l'opération (self ** n)
def __truediv__(self, other): # méthode permettant de redéfinir l'opérateur « / » pour 2 polynômes
# si le degré de self est inférieur au degré de other
if self.degre()<other.degre():
# on renvoie (0, self) : q=0, r=self
return (Polynome([0]), self) # sortie de la fonction
# polynôme self représentant au départ le reste r
r = Polynome(self.coefs)
# degré du polynôme représentant le quotient q
degre = r.degre() - other.degre()
# initialisation du polynôme q : [0, 0, 1] -> ... + X^2
q = Polynome([0]*degre + [1])
# tant que le degré mini des termes du polynôme q est supérieur ou égal à 0, et que r n'est pas égal à 0.
while (degre>=0) and (r.coefs[-1]!=0):
# coefficient du nouveau terme du polynôme q
coef = r.coefs[-1] / other.coefs[-1]
# affectation du coefficient au terme
q.coefs[degre] = coef
# on multiplie le polynôme other par le polynôme coef*(x^degre)
p = other * (coef, degre)
# soustraction des polynômes r et p
r = r - p
# degré du nouveau terme du polynôme q
degre = r.degre() - other.degre()
# renvoi le couple (q, r) représentant le quotient et le reste[/degre]...
La fin de cet article est réservée aux abonnés. Soutenez le Club Developpez.com en prenant un abonnement pour que nous puissions continuer à vous proposer des publications.