ALGORITHMES EN DIRECT
AlgoBox
Présentation de l'algorithme :
Deux résultats sont utilisés :
- Si A est un entier alors PGCD(A , 0)=A
- Si A et B sont deux entiers (avec A > B) et si R est le reste de la division euclidienne de A par B alors PGCD(A,B)=PGCD(B,R)
(c'est pour cela que dans l'algorithme, A prend la valeur de B et B prend la valeur de R : le processus peut ainsi se poursuivre)
On procède par division euclidienne successive jusqu'à obtenir un reste nul.
Exemple :
PGCD de 169 et 54
= PGCD de 54 et 7 car 169 = 54 × 3 + 7
= PGCD de 7 et 5 car 54 = 7 × 7 + 5
= PGCD de 5 et 2 car 7 = 5 × 1 + 2
= PGCD de 2 et 1 car 5 = 2 × 2 + 1
= PGCD de 1 et 0 car 2 = 1 × 2 + 0
= 1
Ici 169 et 54 sont premiers entre eux
Code de l'algorithme :
VARIABLES
A EST_DU_TYPE NOMBRE
B EST_DU_TYPE NOMBRE
R EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE A
LIRE B
AFFICHER "PGCD de "
AFFICHER A
AFFICHER " et "
AFFICHER B
TANT_QUE (B!=0) FAIRE
DEBUT_TANT_QUE
R PREND_LA_VALEUR A%B
A PREND_LA_VALEUR B
B PREND_LA_VALEUR R
AFFICHER "= PGCD de "
AFFICHER A
AFFICHER " et "
AFFICHER B
FIN_TANT_QUE
AFFICHER "= "
AFFICHER A
FIN_ALGORITHME
EN CLIQUANT CI-DESSOUS VOUS POUVEZ LANCER L'ALGORITHME.