Exercice algorithme java le plus grand diviseur commun
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 : 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
- 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | import java.util.Scanner; class PGDC { private static Scanner scanner = new Scanner(.in); public static void main( args[]) { .out.println("Calcul du plus grand diviseur commun de deux nombres entiers positifs."); // Entrée des données .out.print("Entrez un nombre positif : "); int nb1 = scanner.nextInt(); .out.print("Entrez un nombre positif : "); int nb2 = scanner.nextInt(); /* A chaque passage de la boucle while, on modifie le plus grand de a et b en déduisant le nombre plus petit, comme indiqué par la formule d'Euclide. La boucle se terminera quand a et b sont égaux (au pire des cas quand ils valent 1). A ce moment-là, on retourne la valeur de a (on aurait aussi pu retourner b). */ int a = nb1; int b = nb2; while (a != b) { if (a > b) { a = a - b; } else { b = b - a; } } .out.println("Le plus grand diviseur commun de " + nb1 + " et " + nb2 + " est " + a); } } |