PGCD [Résolu/Fermé]

- - Dernière réponse :  Anna - 16 nov. 2016 à 20:07
Bonjour,

J'ai trouvée une correction pour l'exercice suivant :

Ecrire une fonction PGCD_Euc qui retourne le PGCD de 2 entiers a et b en utilisant l’algorithme d’Euclide :
L’algorithme d’Euclide consiste à répéter plusieurs fois le traitement :
PGCD(a,b) = PGCD(b,a Mod b)
jusqu’à obtenir PGCD(x,0). Le PGCD est alors x.
Exemple : PGCD(36,16) = PGCD(16,4) = PGCD(4,0) = 4.

Correction :

Fonction PGCD_Euc(a, b : Entier) : Entier
Variables
r : Entier
Début
TantQue (b # 0) Faire
r ← a Mod b
a←b
b←r
FinTQ
PGCD_Euc ← a
Fin

Je pense qu'on doit aussi signaler dans la fonction que a doit être supérieur à b, autrement dit, on doit ajouter un test, au début, sur les valeurs de a et b. qui peut me dire est ce que c'est obligatoire ou non .
Merci en avance.
Afficher la suite 

1 réponse

Messages postés
16028
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
18 septembre 2019
2413
0
Merci
Bonjour,

"signaler dans la fonction que a doit être supérieur à b"
Tu l'as dis toi même
PGCD(a, b) = PGCD(b, a Mod b)

Or si
a < b
on va avoir
a Mod b = a
donc
PGCD(a,b) = PGCD(b, a)
...

Du coup peu importe que a soit plus grand que b, le résultat sera correct quand même (ça va juste rajouter une étape de calcul dans la boucle).
T'as raison, merci bien.