Calcul du PGCD
Le PGCD de deux entiers est leur plus grand diviseur commun.
Le principe adopté est l'algorithme d'Euclide que l'on peut formellement décrire ainsi :
La division entière se définit par A= (B * Q) + R avec A, B, Q, R entiers naturels. Nous définissons par le signe % l'opérateur binaire tel que A % B calcule la valeur de R. C'est le reste de la division entière. L'opérateur % défini le modulo mathématique.
si R= 0 alors le PGCD de A et B vaut B
si R≠ 0 alors le PGCD de A et B est le même que le PGCD de B et R
Données
A et B deux valeurs entières fournies par l'utilisateur
Variables
A et B entiers
R entier pour le reste
le_pgcd entier pour le résultat
Instructions
afficher (calcul du PGCD de deux entiers)
afficher (entrer le premier entier)
lire (A)
afficher (entrer le deuxième entier)
lire (B)
truc : R = A % B
si R≠ 0
alors
A = B
B = R
aller à truc:
sinon le_pgcd = B
afficher ( le PGCD de A et B est, le_pgcd)
Remarquez que « truc: » est une étiquette. Nous avons un branchement sans condition.
Il existe une solution avec une boucle (voir structures itératives) qui est préférable. Il peut exister plusieurs algorithmes pour traiter un même problème.
Comme vous pouvez le constater, ces deux algorithmes sont plus précis. Ils ne sont cependant pas sans ambiguïtés.
Nous avons présenté un cadre pour concevoir des algorithmes simples. Nous avons introduit des concepts importants.
Cependant nous pouvons nous permettre de prendre certaines libertés dans la rédaction d'un algorithme quand celui-ci est très simple et qu'il y a peu d'ambiguïtés possibles.
Par exemple dans des cas très simples on peut omettre de définir explicitement les variables, ou encore ne pas utiliser de délimiteurs de début et fin de bloc. Par contre si l'algorithme est complexe nous vous invitons à utiliser ce qui vous a été présenté.
