Plus grand diviseur commun avec Java

«Le plus grand diviseur commun, abrégé GCD, est également connu comme le facteur commun le plus élevé, abrégé H.C.F."

Signification du plus grand diviseur commun

Un diviseur est un nombre entier (entier) qui ira dans un autre nombre entier sans reste. Le plus grand diviseur commun s'explique mieux avec une illustration. Le tableau suivant montre deux nombres: 60 et 108, tous leurs diviseurs supérieurs à 1.

Il y a des diviseurs dans le tableau qui ne sont pas communs à 60 et 108. Cependant, 2 est un diviseur commun aux deux nombres 60 et 108, mais ce n'est pas le plus grand diviseur commun aux 60 et 108. Le diviseur 3 est décrit de la même manière. Par inspection de la table, le plus grand diviseur commun à 60 et 108 est 12. Aucun diviseur supérieur à 12 n'est commun dans les 60 et 108. Donc 12 est le plus grand diviseur commun pour 60 et 108.

Le but de cet article est d'expliquer comment obtenir le plus grand diviseur commun par soustraction ou par division; avec la programmation réalisée à Java.

GCD par soustraction

Par inspection du tableau ci-dessus, le GCD pour 60 et 108 est 12. Cela signifie que si 12 est ajouté à plusieurs reprises, le résultat deviendra 60, le plus petit des deux nombres. Si l'ajout de 12 se poursuit, le résultat deviendra 108, le plus gros des deux chiffres. C'est-à-dire:

12 + 12 +12 +12 + 12 = 60

12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108

C'est-à-dire:

60 + 12 + 12 + 12 + 12 = 108

Ce qui signifie:

60 + 48 = 108

Si l'ajout de GCD peut entraîner les deux nombres, alors peut-être qu'une forme de soustraction continue vers le bas peut conduire au GCD. Ceci est un fait, comme illustré par les étapes suivantes, en commençant par la différence de 108 et 60:

108 - 60 = 48
60 - 48 = 12
48 - 12 = 36
36 - 12 = 24
24 - 12 = 12
12 - 12 = 0

Entre 60 et 108, 108 est le plus grand nombre. Après cela, la différence de la différence résultante (48 pour la première étape) et du subtrahend (60 pour la première étape) est obtenue à plusieurs reprises jusqu'à ce que la réponse soit nulle. Dans les étapes, le plus petit nombre est soustrait, le plus grand nombre. À la dernière étape, le Minuend et le Subtrahend sont les mêmes. Cette même valeur est le plus grand diviseur commun.

Laissez les chiffres dont le GCD est nécessaire. Si ces nombres n'ont pas de GCD supérieur à 1, cela signifie que leur plus grand diviseur commun est 1. En programmation, la complexité temporelle pour trouver le GCD par soustraction est O (A + B). Si A est 1 et B est 5, les étapes sans programmation seront:

5 - 1 = 4
4 - 1 = 3
3 - 1 = 2
2 - 1 = 1
1 - 1 = 0

Le GCD ici est 1. Il y a cinq étapes ici et pas six étapes par (a + b). Cependant, dans la programmation, le nombre maximal possible d'opérations de code est ce qui est considéré comme la complexité temporelle.

Codage GCD par soustraction

La classe et la méthode du plus grand diviseur commun par soustraction en Java sont:

classe GCDS
int gcds (int a, int b)
si (a == b)
retourner a;
si (a> b)
RETOUR GCDS (A-B, B);
RETOUR GCDS (A, B-A);

Il commence par une déclaration pour la dernière étape mathématique lorsque les deux nombres résultant sont égaux. Les deux déclarations suivantes soustraient le plus petit nombre du plus grand nombre récursivement. Une classe principale Java et la méthode principale Java, pour aller avec la classe ci-dessus, est:

classe publique Main
public static void main (String args [])
Gcds obj = new gcds ();
int ret = obj.GCDS (108, 60);
Système.dehors.println (ret);

La sortie est 12.

GCD par division

Le tableau ci-dessus est répété ici pour une référence facile:

Les deux nombres dont le GCD est nécessaire est de 60 et 108, 108 étant le plus grand nombre. L'explication ci-dessus de la soustraction a commencé avec:

12 + 12 +12 +12 + 12 = 60

12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108

C'est-à-dire:

60 + 12 + 12 + 12 + 12 = 108

Ce qui signifie:

60 + 48 = 108

La division modulo est une division où la réponse est la partie du numéro du quotient, et le reste est également pris en considération. Considérez le reste lors de la division de 108 par 60 et des restes des quotients résultants et de leurs diviseurs correspondants.

108% 60 = 48 (i.E 1 r 48)
60% 48 = 12 (i.E 1 r 48)
48% 12 = 0 (i.E 4 R 0)

La division du module se termine lorsque le reste est 0. Le GCD est le diviseur de la dernière étape. Il était déjà connu, de l'autre méthode ci-dessus, que le plus grand diviseur commun est 12.

108 mod 60 n'est pas zéro. Si le GCD entre 60 et 108 devait être trouvé par soustraction, la première différence pour le GCD entre 60 et 108 serait de 48, et il peut être démontré que le GCD entre 60 et 108 est 12 est 12. 60 mod 48 n'est pas zéro. Si le GCD entre 60 et 48 (le reste précédent) devait être trouvé par soustraction, la première différence pour le GCD entre 60 et 48 serait de 12, et il peut être démontré que le GCD entre 60 et 48 est 12 est 12. 48 mod 12 est zéro et a 0 reste. Si le GCD entre 48 et 12 devait être trouvé par soustraction, la première différence pour le GCD entre 48 et 12 serait 36. 36 n'est pas le GCD entre 48 et 12; Cependant, 36 est un multiple de 12, qui est le GCD.

En utilisant tous les moyens, le lecteur peut prouver avec les étapes ci-dessus qui étant donné que le GCD pour 60 et 108 est de 12, le GCD pour 60 et 48 est également 12; Et le GCD pour 48 et 12 est toujours 12.

Considérez un autre exemple pour trouver le GCD par division. Le problème est maintenant: pour trouver le GCD par division pour les numéros 18 et 30.

Solution:

30% 18 = 12 (i.e. 1 r 12)
18% 12 = 6 (i.e. 1 r 6)
12% 6 = 0 (i.e. 2 r 0)

Le GCD est 6, lu à partir de la dernière ligne, où le module est 0.

30 mod 18 n'est pas zéro. Si le GCD entre 30 et 18 devait être trouvé par soustraction, la première différence pour le GCD entre 30 et 18 serait de 12, et il peut être démontré que le GCD entre 30 et 18 est 6 est 6. 18 mod 12 n'est pas zéro. Si le GCD entre 18 et 12 devait être trouvé par soustraction, la première différence pour le GCD entre 18 et 12 serait de 6, et il peut être démontré que le GCD entre 18 et 12 est de 6. 12 mod 6 est zéro. Si le GCD entre 12 et 6 devait être trouvé par soustraction, la première différence pour le GCD entre 12 et 6 serait de 6, et il peut être démontré que le GCD entre 12 et 6 est de 6. 6 est également un multiple de 6 lui-même, qui est le GCD.

En utilisant tous les moyens, le lecteur peut prouver avec les étapes ci-dessus qui étant donné que le GCD pour 30 et 18 est de 6, le GCD pour 18 et 12 est également 6; Et le GCD pour 12 et 6 est toujours 6.

Considérez maintenant le GCD obtenu à partir de 1 et 5 par division:

5% 1 = 0 (I.e. 5 R 0)

Il n'y a qu'une seule étape (une ligne) ici. Pour terminer cette section, notez que le diviseur de la dernière ligne, lorsque vous recherchez le GCD par division, est le GCD.

Notez également que:

gcd (a, b) = gcd (b, r)

où «a» et «b» sont deux nombres entiers différents et «r» est le reste de la division entre A et «B."" B "peut être plus grand que" A "ou" A "peut être plus grand que B. Cela signifie que si le reste d'une division n'est pas nul, alors le plus grand diviseur commun entre les deux nombres est le même que le plus grand diviseur commun entre le diviseur et le reste. La preuve de cette déclaration a été illustrée ci-dessus.

Cela peut aller directement par la division modulo, comme expérimenté ci-dessus jusqu'à ce que le reste est zéro. Lorsque le reste est nul, cette règle de répétition ne tient pas. À strictement parler, dans la division du module, peu importe que «A» soit plus grand que B ou B est plus grand que «A»; Le reste est le même entier positif.

Codage GCD par division

Si le plus grand diviseur commun par la division entre 60 et 108 est requis mathématiquement, alors les étapes seraient

108% 60 = 48 (i.E 1 r 48)
60% 48 = 12 (i.E 1 r 48)
48% 12 = 0 (i.E 4 R 0)

Notez que c'est le plus grand nombre qui se divise, le plus petit nombre. La classe Java et la méthode pour faire cette division sont:

classe gcdd
int gcdd (int a, int b)
si (un% b == 0)
retour b;
Retour GCDD (B, A% B);

La première déclaration de la méthode explique la dernière étape mathématique. La deuxième déclaration fait la division modulo. Les deux déclarations appellent la méthode récursive. La complexité temporelle de GCD par division est O (log (a + b)). Une bonne classe principale et la méthode principale de ce code sont:

classe publique Main
public static void main (String args [])
Gcdd obj = new gcdd ();
int ret = obj.GCDD (108, 60);
Système.dehors.println (ret);

La sortie est 12.

Conclusion

Le plus grand diviseur commun peut être obtenu en soustrayant d'abord le plus petit nombre du plus grand nombre, puis en continuant à soustraire la Minien de la différence ou de la différence par.

Le plus grand diviseur commun peut également être obtenu en divisant d'abord le plus grand nombre par le plus petit nombre à l'aide de la division du module; puis continuer à diviser le reste par le diviseur ou le diviseur par le reste, selon lequel est plus grand, toujours par la division du module. À strictement parler, dans la division du module, peu importe que «A» soit plus grand que B ou B est plus grand que «A»; Le reste est le même entier positif.

Ceci se fait par programmation récursivement.