Cet article décrit l'algorithme de Java pour résoudre le plus grand diviseur commun de deux entiers non négatifs. Partagez-le pour votre référence, comme suit:
Fonctions de code:
1. Implémentation Java (code source complet avec les cas de test);
2. Résolvez le plus grand diviseur commun de deux entiers non négatifs P et Q (P> = Q);
3. Deux solutions: méthode de boucle et méthode récursive;
Code source complet:
/ * GCD: GreatEast Diviser commun * / public class GCD {public static void main (String args []) {/ * Test Case * / int p = 32; int q = 24; System.out.println ("Le plus grand diviseur de" + p + "et" + q + "est / n" + "[gcd1]:" + gcd1 (p, q) + "/ n" + "[gcd2]:" + gcd2 (p, q)); } // (q% gcd == 0 et p% gcd == 0 [gcd de q à 1]) public statique int gcd1 (int p, int q) {int gcd = 1; int d = q; while (d> 0) {d--; if (q% d == 0 && p% d == 0) {gcd = d; casser; }} return gcd; } // gcd (p, q) = gcd (q, p% q) [if q = 0, gcd = p] public static int gcd2 (int p, int q) {if (q == 0) return p; int r = p% q; //System.out.println("("+q+" ,"+r+ ")"); retour gcd2 (q, r); }}Capture d'écran en cours:
Explication du code:
Méthode circulaire GCD1 (P, Q)
DESCRIPTION DU LANGUE NATUREL: La méthode de boucle résout le plus grand diviseur commun de deux entiers non négatifs p, q (p> = q), c'est-à-dire résout la valeur maximale du diviseur commun de Q qui est p. Soit D (divisé) la diminution de P (étape de décrémentation = 1) D est toujours "la valeur maximale de la condition qui est sur le point d'être satisfaite". Lorsque d répond à la condition (il peut être divisé par P et divisible par P), D est le diviseur commun de P et Q, et D est le plus grand diviseur commun de P et Q;
Méthode récursive GCD2 (P, Q)
DESCRIPTION DU LANGUE NATUREL: La méthode récursive résout le plus grand diviseur commun de deux entiers non négatifs P, Q (p> = Q). Lorsque q est égal à 0, le plus grand diviseur commun est P; Sinon, prenez le reste de P et Q pour obtenir R = P% Q, et le plus grand diviseur commun de P et Q est le plus grand diviseur commun de Q et R;
Expérience du code:
En ce qui concerne la méthode de boucle, au début, ce à quoi je pensais était d'écrire une méthode pour résoudre des diviseurs communs, d'utiliser un réseau entier pour stocker tous les diviseurs communs d'un entier non négatif, puis comparer et découvrir le plus grand diviseur commun commun à P et Q, qui est le plus grand diviseur commun de deux nombres. Plus tard, je pensais, comme il s'agit de trouver le maximum, ne serait-il pas plus facile de diminuer directement de l'arrière à l'avant? La diminution de l'arrière à l'avant peut garantir que ce nombre est toujours le plus grand à l'heure actuel, car les personnes qui sont plus grandes qu'elle ne remplit pas les conditions (peuvent être divisées par P et Q en même temps) sont éliminées, ce qui évite le problème de trouver le maximum initialement. Bien qu'il existe de nombreuses façons de trouver le maximum, si vous avez ou non eu besoin de prouver et de rechercher, haha, pourquoi vous sentez-vous un peu sur la philosophie?
En ce qui concerne la récursivité, ce que je peux comprendre entièrement en fonction de mon intuition est la seule phrase que le plus grand diviseur commun de P et Q est le plus grand diviseur commun de Q et R (R = P% Q), qui est le début de l'anneau, mais je ne comprends toujours pas très bien que la condition finale de l'anneau est 0, et le retour P;
Bien qu'il s'agisse d'une solution très simple à l'algorithme de diviseur commun, je dois l'écrire de deux manières, principalement pour ressentir la méthode de récursivité que je ne connais pas très bien. Dans le passé, j'ai vu la formule claire de l'algorithme de récursivité pour résoudre les chiffres de la tour Hanovre et des Fibonacci qui y ont été illuminés, et je soupirais que ce sont des mathématiques complètement! Le sentiment que j'ai appris aujourd'hui était encore plus choquant que cette époque. Je me suis demandé ce qui s'était passé et je l'ai résolu étrangement. À cette époque, je ne me souciais pas beaucoup de la mémoire, de l'efficacité et d'autres indicateurs. Je pensais juste que les gars qui pouvaient y penser étaient vraiment intelligents. Pour eux, qu'il s'agisse d'un ordinateur ou d'un langage de programmation, c'était juste un outil pour résoudre le problème. Certaines personnes disent que la récursivité est un algorithme qui permet au cerveau de penser aux ordinateurs de calculer, et cela semble vraiment approprié.
Références
Série de programmes Turing: Algorithms (4e édition) Robert Sedgewick (auteur), Kevin Wayne (auteur), Xie Luyun (traducteur)
Pour plus d'informations sur les algorithmes Java, les lecteurs qui sont intéressés par ce site peuvent afficher les sujets: "Structure de données Java et tutoriel d'algorithme", "Résumé des conseils de nœud de Dom Operation Java", "Résumé du fichier Java et des conseils d'opération de répertoire" et "Résumé des conseils d'opération Java Cache"
J'espère que cet article sera utile à la programmation Java de tous.