Exercice algorithme corrigé le plus grand diviseur commun, tutoriel & guide de travaux pratiques en pdf.
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 la formule 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:
- Si a > b, alors PGDC(a, b) = PGDC(a-b, b)
- PGDC(a, a) = a
Exemple de calcul de PGDC(42, 24):
- 42 > 24, alors PGDC(42, 24) = PGDC(42–24, 24) = PGDC(18, 24) = PGDC(24,18)
- 24 > 18, alors PGDC(24, 18) = PGDC(24–18, 18) = PGDC(6, 18) = PGDC(18, 6)
- 18 > 6, alors PGDC(18, 6) = PGDC(18–6, 6) = PGDC(12, 6)
- 12 > 6, alors PGDC(12, 6) = PGDC(12–6, 6) = PGDC(6, 6)
- 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.
La correction exercice algorithme (voir page 2 en bas)
