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:
  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.
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);
}
}
Article publié le 13 Août 2010 Mise à jour le Dimanche, 15 Août 2010 16:57 par Salim KHALIL