Größter gemeinsamer Teiler in allen Programmiersprachen
Größter gemeinsamer Teiler in Java
Gepostet: , Zuletzt aktualisiert:
Java ™ ist eine kompilierte Sprache, die für viele Zwecke verwendet wird, von eingebetteten Systemen über UI-Anwendungen bis hin zu Webservern.
Zur ImplementierungGrößter gemeinsamer Teiler in Javascript
Gepostet: , Zuletzt aktualisiert:
JavaScript JavaScript ist eine interpretierte Skriptsprache, die zuvor hauptsächlich in Webseiten verwendet wurde (die in Browsern…
Zur ImplementierungGrößter gemeinsamer Teiler in Python
Gepostet: , Zuletzt aktualisiert:
Python Python™ ist eine interpretierte Sprache, die für viele Zwecke verwendet wird, von der eingebetteten Programmierung bis zur Webentwicklung, wobei einer der größten Anwendungsfälle die Datenwissenschaft ist.
Zur ImplementierungGrößter gemeinsamer Teiler in C
Gepostet: , Zuletzt aktualisiert:
C ist eine kompilierte Sprache, die für viele Zwecke verwendet wird, obwohl sie hauptsächlich in Systemen zu finden ist, in denen Wichtigkeit wichtig ist. Dies liegt daran, dass C viel Unterstützung auf niedriger Ebene für die Optimierung bietet, auf Kosten der Tatsache, dass einige der praktischen Abstraktionen, die andere Sprachen bieten, nicht vorhanden sind. C tritt daher hauptsächlich in Situationen auf, in denen die verfügbare Rechenleistung gering ist, wie beispielsweise eingebettete Systeme, oder in Situationen, in denen die erforderliche Rechenleistung hoch ist, wie z. B. Simulation oder Deep Learning.
Zur ImplementierungGrößter gemeinsamer Teiler in R
Gepostet: , Zuletzt aktualisiert:
R R ist eine interpretierte Sprache, die erstmals 1993 veröffentlicht wurde und in den letzten Jahren erheblich an Popularität gewonnen hat…
Zur ImplementierungÜber den Algorithmus und die Programmiersprache in diesem Snippet:
Euklid's größter gemeinsamer Teiler (GGT) Algorithm
Der größte gemeinsame Teiler zweier Zahlen (in diesem Fall a und b) ist die größte Zahl, durch die beide Zahlen ohne Rest geteilt werden können. Dieser größte gemeinsame Divisor (Teiler)-Algorithmus, der als euklidischer Algorithmus bezeichnet wird, bestimmt diese Zahl. Der größte gemeinsame Teiler wird auch oft als gcd abgekürzt.
Beschreibung des Algorithmus
Das Grundprinzip hinter diesem gcd-Algorithmus besteht darin, den gcd von a und b rekursiv zu bestimmen, indem der gcd von b und a%b bestimmt wird Dies hängt von der Tatsache ab, dass der gcd von zwei Zahlen auch ihre Differenz teilt, z. Der größte gemeinsame Teiler von 16 und 24 (das ist 8) ist auch der größte gemeinsame Teiler von 24-16=8. Dies gilt daher auch für 16 und 40 - anstatt die Differenz zu nehmen, kann der Rest auch verwendet werden (ein wiederholtes Wiederkehren der Differenz führt zwangsläufig dazu, dass der Rest “bestanden” wird). Zusammenfassend verwendet der euklidische gcd-Algorithmus diese beiden Schritte:
- Wenn a oder b 0 ist, geben Sie den anderen zurück.
- Wiederholen Sie dies mit dem neuen a als b und dem neuen b als a%b.
Die Verwendung des Restes hat eine viel schnellere Laufzeit als die Verwendung des Unterschieds.
Beispiel des Algorithmus
Bei der Berechnung der GCD von 1071 und 462 werden die folgenden Schritte ausgeführt:
- a ist 1071, neu b ist 462
- Rekursiv mit neuem a = b und neuem b = a% b …
- Neu a ist 462, neu b ist 147
- Rekursiv mit neuem a = b und neuem b = a% b …
- Neu a ist 147, neu b ist 21
- Rekursiv mit neuem a = b und neuem b = a% b …
- Neu a ist 21, neu b ist 0
- b ist 0, Stopp der Rekursion, a ist die gcd: 21
Laufzeitkomplexität des Algorithmus
Die Laufzeitkomplexität des euklidischen größten gemeinsamen Divisor-Algorithmus ist O(log (max (a, b))) (der Logarithmus des Maximums der beiden Zahlen). Die Verwendung des Restes anstelle des Unterschieds ist erheblich schneller - wenn der Unterschied verwendet worden wäre, hätte dieser größte gemeinsame Divisor-Algorithmus eine Laufzeit von O(max (a, b)) gehabt
Speicherkomplexität des Algorithmus
Die Speicherkomplexität des größten gemeinsamen Divisor-Algorithmus der Euklidischen Welt entspricht der Laufzeit, da jeder rekursive Aufruf im Stapel gespeichert wird und alles andere konstant ist.