Dieser Artikel beschreibt Javas Algorithmus zur Lösung des größten gemeinsamen Teils von zwei nicht negativen Ganzzahlen. Teilen Sie es für Ihre Referenz wie folgt weiter:
Codefunktionen:
1. Java -Implementierung (Vollquellcode mit Testfällen);
2. Lösen Sie den größten gemeinsamen Divisor von zwei nicht negativen Ganzzahlen P und Q (p> = q);
3. zwei Lösungen: Schleifenmethode und rekursive Methode;
Komplette Quellcode:
/ * GCD: GreatEast Common Divisor */public class gcd {public static void main (String args []) {/ * Testfall */int p = 32; int q = 24; System.out.println ("Die größte Teilung von"+p+"und"+q+"ist /n"+"[gcd1]:"+gcd1 (p, q)+" /n"+"[gcd2]:"+gcd2 (p, q)); } // (q % gcd == 0 und p % gcd == 0 [GCD von q bis 1]) public static 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; brechen; }} 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+","s IENRESSIEREN ")")); Return GCD2 (Q, R); }}Laufen Screenshot:
Code Erläuterung:
Rundmethode GCD1 (p, q)
Beschreibung der natürlichen Sprache: Die Schleifenmethode löst den größten gemeinsamen Divisor von zwei nicht negativen Ganzzahlen P, q (p> = q), dh den maximalen Wert des gemeinsamen Divisors von q, der P ist. Sei D (geteilt) Decrement von P (Dekrementschritt = 1) D ist immer "der maximale Wert der Erkrankung, die erfüllt wird". Wenn D auf die Erkrankung trifft (es kann durch P geteilt und durch P geteilt werden), ist D der gemeinsame Divisor von P und Q, und D ist der größte gemeinsame Divisor von P und Q;
Rekursive Methode GCD2 (p, q)
Beschreibung der natürlichen Sprache: Rekursive Methode löst den größten gemeinsamen Divisor von zwei nicht negativen Ganzzahlen P, q (p> = q). Wenn Q gleich 0 ist, ist der größte gemeinsame Divisor p; Ansonsten nehmen Sie den Rest von P und Q, um r = p%q zu erhalten, und der größte gemeinsame Divisor von P und Q ist der größte gemeinsame Divisor von Q und R;
Codeerfahrung:
In Bezug auf die Schleifenmethode war das, woran ich dachte, eine Methode zur Lösung gemeinsamer Divisors zu schreiben, ein ganzzahliges Array zu verwenden, um alle gemeinsamen Divisoren einer nicht negativen Ganzzahl zu speichern und dann den größten gemeinsamen Divisor in P und Q zu vergleichen und herauszufinden. Später, dachte ich, wäre es nicht einfacher, das Maximum von hinten nach vorne direkt zu verringern? Das Abnehmen von Rücken nach vorne kann sicherstellen, dass diese Zahl derzeit immer die größte ist, da Menschen, die größer sind, als sie nicht den Bedingungen erfüllen (gleichzeitig durch P und Q geteilt werden können), beseitigt werden, was die Mühe vermeidet, das Maximum anfänglich zu finden. Obwohl es viele Möglichkeiten gibt, das Maximum zu finden, wenn Sie nachweisen und nicht suchen müssen, haha, warum fühlen Sie sich ein bisschen über die Philosophie?
In Bezug auf die Rekursion ist das, was ich aufgrund meiner Intuition vollständig verstehen kann, der einzige Satz, dass der größte gemeinsame Divisor von P und Q der größte gemeinsame Divisor von Q und R (R = P%q) ist, der der Beginn des Rings ist, aber ich verstehe immer noch nicht ganz, dass der Endzustand des Rings 0 und zurück -Rendite ist.
Obwohl es eine sehr einfache Lösung für den größten gemeinsamen Divisor -Algorithmus ist, muss ich ihn auf zwei Arten schreiben, hauptsächlich, um die Rekursionsmethode zu spüren, mit der ich nicht sehr vertraut bin. In der Vergangenheit sah ich die klare Formel des Rekursionsalgorithmus für die Lösung des dort beleuchteten Hannover -Turms und Fibonacci -Zahlen, und ich seufzte, dass dies völlig Mathematik ist! Das Gefühl, das ich heute gelernt habe, war noch schockierender als in dieser Zeit. Ich fragte mich, was passiert ist und löste es seltsam. Zu diesem Zeitpunkt war es mir egal, wie ich mich sehr für Gedächtnis, Effizienz und andere Indikatoren interessierte. Ich dachte nur, dass die Jungs, die daran denken konnten, wirklich schlau waren. Ob es sich um einen Computer oder eine Programmiersprache handelte, es war nur ein Werkzeug, um das Problem zu lösen. Einige Leute sagen, dass Rekursion ein Algorithmus ist, der es dem Gehirn ermöglicht, über Computer nachzudenken, und es fühlt sich wirklich angemessen an.
Referenzen
Turing -Programmierreihe: Algorithmen (4. Ausgabe) Robert Sedgewick (Autor), Kevin Wayne (Autor), Xie Luyun (Übersetzer)
Für weitere Informationen zu Java -Algorithmen können Leser, die an dieser Website interessiert sind, die Themen "Java -Datenstruktur und Algorithmus -Tutorial", "Zusammenfassung der Java -Operation DOM -Knoten -Tipps", "Zusammenfassung der Java -Datei- und Verzeichnisoperationstipps" und "Zusammenfassung der Java -Cache -Operation Tipps" anzeigen
Ich hoffe, dieser Artikel wird für Java -Programme aller hilfreich sein.