[Précédent]
[Index] | [Corrigé] | [Version imprimable]
[Prochain]

3.8
   Plus Grand Diviseur Commun - Enoncé
Niveau 2
  
 
But:
   Ecrivez un programme qui calcule le plus grand diviseur commun de deux nombres entiers    
Thème:
   Algorithme, if, boucles    
Fichiers:
   -    

Ecrivez un programme PGDC.java qui calcule et affiche le plus grand diviseur commun de deux nombres entiers positifs entrés au clavier. Exemples d'exécution du programme:

Entrez un nombre positif :  9
Entrez un nombre positif :  6
Le plus grand diviseur commun de 9 et 6 est 3

Entrez un nombre positif :  9
Entrez un nombre positif :  4
Le plus grand diviseur commun de 9 et 4 est 1
Utilisez l'algorithme d'Euclide pour déterminer le plus grand diviseur. Cette formule se résume comme suit:
Soient deux nombres entiers positifs a et b. Si a est plus grand que b, le plus grand diviseur commun de a et b est le même que pour a-b et b. Vice versa si b est plus grand que a.
Les équivalences mathématiques utiles sont:
  1. Si a > b, alors PGDC(a, b) = PGDC(a-b, b)

  2. PGDC(a, a) = a
Exemple de calcul de PGDC(42, 24):
  1. 42 > 24, alors PGDC(42, 24) = PGDC(42--24, 24) = PGDC(18, 24) = PGDC(24,18)

  2. 24 > 18, alors PGDC(24, 18) = PGDC(24--18, 18) = PGDC(6, 18) = PGDC(18, 6)

  3. 18 > 6, alors PGDC(18, 6) = PGDC(18--6, 6) = PGDC(12, 6)

  4. 12 > 6, alors PGDC(12, 6) = PGDC(12--6, 6) = PGDC(6, 6)

  5. Résultat: PGDC(42, 24) = PGDC(6, 6) = 6
Indication: utilisez une boucle (par exemple while) qui s'occupe de modifier et de tester les valeurs de a et b jusqu'à ce qu'une solution soit trouvée.

 

[Précédent]
[Index] | [Corrigé] | [Version imprimable]
[Prochain]