Banque de problèmes LARP

Problème 4.18

 

Titre :

Programme du Plus Grand Commun Diviseur (P.G.C.D.)

Date :

3 avril 2006

Référence :

Le livre du C premier langage

C. Delannoy

1994, Éditions Eyrolles

P. 125 (Algorithme d’Euclide)

Solutions :

Philippe Turcotte

 

Description du problème

 

Concevoir un algorithme capable de trouver le Plus Grand Commun Diviseur (P.G.C.D.) de deux entiers à l’aide de l’algorithme d’Euclide. L’algorithme d’Euclide consiste à répéter les étapes suivantes :

 

·         calculer r, reste de la division de a par b,

·         remplacer a par b et b par r.

 

Lorsque la valeur de r sera nulle (égale à 0), alors le P.G.C.D. cherché sera la valeur finale de a.

 

L’algorithme doit lire deux entiers positifs et afficher leur P.G.C.D.

 

Solutions du problème

 

Cet algorithme utilise une structure d’itération TANTQUE.

Elle sera exécutée indéfiniment jusqu’à ce que r soit égal à 0.

 

*Aucune vérification ne sera appliquée pour vérifier que a et b sont des entiers positifs.

 

Solution organigramme LARP :

Delannoy_P125_Euclide_Org.larp

Solution pseudo-code LARP :

Delannoy_P125_Euclide_Pseudo.larp

Solution Java :

Delannoy_P125_Euclide.java

 

Note : L'accès aux fichiers de projet LARP ci-dessus est réservé aux détenteurs d'une clé de débridage pour LARP afin d'en assurer l'exclusivité aux enseignants. Tous ont cependant accès à la solution Java proposée.