Algorithmique impérative/PGCD
Un livre de Wikibooks.
[modifier] Problèmatique
Écrire un algorithme donnant le Plus Grand Commun Diviseur (PGCD) de deux nombres donnés par l'utilisateur. On supposera que l'utilisateur ne donne que des entiers strictement supérieurs à zéro.
Il faudra écrire une fonction, prenant en entrée deux entiers strictement positifs et renvoyant leur PGCD. L'algorithme principal y fera appel.
Question subsidiaire : on considérera que l'utilisateur peut entrer n'importe quels entiers. Tenez-en compte pour que l'algorithme ne commette pas d'erreur et qu'il informe l'utilisateur.
[modifier] Aide
Il faut avoir étudié ce problème d'algèbre pour avoir la solution. Elle consiste à appliquer l'algorithme d'Euclide.
[modifier] Solution
-
Algorithme pgcd
-
-
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 -
FTQ
-
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 -
(* Fin Question subsidiaire *) -
Écrire(euclide(u,v)) -
fin
-
Fin
Pas vraiment de difficulté pour l'algorithme principal. La difficulté étant la fonction implémentant l'algorithme d'Euclide. Le jeu d'assignation à répéter jusqu'à obtenir un reste nul est difficile à visualiser.
Question subsidiaire : il y a trois événements à contrôler :
- Le cas où u=v=0 et où le pgcd n'existe pas et il faut arrêter le programme (ligne 22)
- Le cas où u ou v (ou les deux) est négatif est il faut prendre son opposé (lignes 24 et 25)
Pour la solution sans la question subsidiaire : ôter les lignes 21 à 26 et la 28 de la solution proposée.
