L3 Maths 2015-2016 Algèbre Effective
TP1 : Pgcds d'entiers
Pour commencer on va modifier deux versions du
calcul du pgcd de deux entiers,
une version récursive
def PgcdRec (a,b): if b==0 : return(a) else : return(PgcdRec(b,a%b))
et une version itérative
def PgcdIter (a,b): while b!=0 : r=a%b;a=b;b=r return(a)
Remarquer le test d'égalité == , d'inégalité !=,
l'affectation = , le reste de la division euclidienne %
N'oubliez pas d'évaluer (Maj-entrée ou Run) avant d'utiliser
PgcdRec(132,105)
PgcdIter(132,105)
PgcdRec(3443,55),PgcdIter(3443,55)
Evidemment la fonction existe dans Sage
gcd(3443,55)
Avoir de l'aide en ligne est important,
on ne peut pas mémoriser les milliers de fonctions de ce genre de
logiciel.
Exécuter les lignes suivantes.
gcd?
help()
help(gcd)
Pour savoir ce qu'un objet accepte comme fonctions
taper l'objet suivi d'un . puis la touche tab
Faire tab dans la ligne ci dessous.
132.
Exercice 1
Modifier les fonctions PgcdRec et PgcdIter
pour qu'elles affichent les restes calculés comme ci-dessous.
Utiliser la fonction print.
PgcdRecVoir(132,105)
27
24
3
0
3
PgcdIterVoir(132,105)
27
24
3
0
3
Exercice 2
Modifier les fonctions PgcdRec et PgcdIter pour qu'elles construisent la
suite d'Euclide
formée des nombres de départ puis de la suite des restes calculés comme
ci-dessous.
Vous aurez besoin de la fonction append qui ajoute un
élément à une liste
ou de la fonction + qui concatène des listes.
La fonction append modifie la liste.
L=[1,2,3,4];L
[1, 2, 3, 4]
L.append(10);L
[1, 2, 3, 4, 10]
L+[6,7,8];L
[1, 2, 3, 4, 10, 6, 7, 8]
[1, 2, 3, 4, 10]
PgcdRecSuite(132,105)
[132, 105, 27, 24, 3, 0]
PgcdIterSuite(132,105)
[132, 105, 27, 24, 3, 0]
%htmlEdit text...gcd ?
Exercice 3 Modifier les fonctions
PgcdRec et PgcdIter pour qu'elles calculent le nombre de divisions
effectuées lors de l'algorithme.
PgcdIterCompte(132,105)
4
PgcdRecCompte(132,105,0)
4
Calculer le nombre de divisions dans les cas
suivants et commenter :
%htmlOn remarque dans la version récursive le compteur comme paramètre supplémentaire<br>qu'on doit initialiser à zéro à l'appel.<br>
PgcdIterCompte(87489456445414145651417,87489456445414145651416)
PgcdIterCompte(87489456445414145651417,67489456445414145651417)
Exercice 4
Modifier la fonction PgcdIter pour qu'elle rende le pgcd et les
coefficients de Bézout.
Vous aurez besoin de l'opérateur // qui donne le quotient de la division
euclidienne.
BezoutIter(132,105)
(3, 4, -5)
BezoutIter(1870,242)
(22, -4, 31)
Comme on l'a vu en td.
Même question avec PgcdRec.
BezoutRec(1870,242,1,0,0,1)
(22, -4, 31)
Comme l'initialisation de u0, v0, u1, v1 est lourde
et peut être source d'erreur
on définit une fonction auxiliaire qui appelle BezoutRec correctement
initialisé.
def BezoutAux (a,b): return(BezoutRec(a,b,1,0,0,1))
BezoutAux(1870,242)
(22, -4, 31)
Evidemment cette fonction aussi existe dans Sage :
xgcd?