Exercice Algorithme : Le PGCD

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:

1. A prend la valeur de B,
2. 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

si v

Écrire(euclide(u,v))

fin

Fin