Exercice algorithme java le plus grand diviseur commun
Rédigé par GC Team, Publié le 13 Août 2010, Mise à jour le Dimanche, 15 Août 2010 16:57Participez au vote ☆☆☆☆☆★★★★★
But:
|
Ecrivez un programme qui calcule le plus grand diviseur commun de deux nombres entiers | |||
Thème:
|
Algorithme, if, boucles |
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 : 9Utilisez la formule d'Euclide pour déterminer le plus grand diviseur. Cette formule se résume comme suit:
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
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
- 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
Fichiers:
|
1 |
import java.util.Scanner; |