Exercice Algorithme : Le PGCD
![](/images/thumb/46/default.png)
Enoncé de l'Exercice:
Donner l’algorithme qui calcule le PGDC (plus grand diviseur commun).
Exemple : calcul du PGDC des deux nombres 1000 et 24
On continue jusqu'à avoir un reste nul. Le dernier nombre, par lequel on a divisé, est le PGDC. Ainsi, le PGDC est égal à 8.
Pour plus de Simplicité :
À chaque ligne suivante:
- A prend la valeur de B,
- B celle de R.
Et, on recommence la division avec ces nouvelles valeurs de B et R.
On s'arrête lorsque R est nul.
Le PGCD est égal au B final.
Première Solution:
Fonction Euclide( u : entier v : entier) : entier
Variables
r : entier (* le reste d'une division entière *)
Début
Tant que v 0 faire
r = u mod v
u = v
v = r
Fin Tant que
retourner u
Fin
Variables
u,v : entier (* les deux entiers donnés par l'utilisateur *)
Début
Écrire("Donner les deux nombres : ")
Lire(u,v)
(* Début question subsidiaire *)
si u=0 et v=0 alors Écrire("Le PGCD n'existe pas")
sinon début
si u < 0 alors u := -u
si v < 0 alors v := -v
Écrire(euclide(u,v))
fin
Fin
Deuxième Solution:
Var a, b, PGCD ; Entier Ecrire "Introduisez le 1er nombre: " lire a Ecrire "Introduisez le 2ème nombre: " lire b tant que NOT (a*b=0) faire selon que 1: a mod 2+b mod 2=0 faire PGCD Ecrire "PGCD = ", PGCD*b sinon écrire "PGCD = ", PGCD*a fin si