Größter gemeinsamer Divisor mit Python

Ein Faktor ist eine Zahl, die in eine andere Zahl ohne Rest eingehen kann. Eine Dividende teilt einen Divisor, um den Quotienten zu geben. Wenn die Dividende und der Divisor eine ganze Zahl sind und der Quotient einen Rest von Null hat (kein Rest), wird der Divisor als Faktor der Dividende bezeichnet. Der größte gemeinsame Divisor ist abgekürzt, G.C.D oder einfach GCD. Ein anderer Name für den größten gemeinsamen Divisor ist der höchste gemeinsame Faktor, abgekürzt H.C.F.

Finden g.C.F per Definition

Das Problem ist, den höchsten gemeinsamen Faktor zu finden, der auch als der größte gemeinsame Divisor für die Zahlen 108 und 240 bezeichnet wird.

Lösung:

Alle Faktoren, die größer als 1 sind, werden in der folgenden Tabelle platziert:

108: 2 3 4 6 9 12 18 26 36 54 108
240: 2 3 4 5 6 8 10 12 15 16 20 24 30 48 60 120 240

Die erste Reihe hat die Faktoren von 108 in aufsteigender Reihenfolge. Die zweite Reihe hat die Faktoren von 240 in aufsteigender Reihenfolge.

Häufige Faktoren (Divisoren) für 108 und 240 sind: 2, 3, 4, 6 und 12.

Durch Inspektion ist der größte Faktor (Divisor), der den Zahlen 108 und 240 gemeinsam ist, 12. Das heißt, GCD oder H.C.F für 108 und 240 sind 12.

Das Schreiben eines Programms, das die GCD wie oben erläutert findet, wird zu lange dauern. Zwei kürzere Methoden zur Ermittlung der GCD sind: GCD durch Subtraktion und GCD nach Division.

GCD durch Subtraktion

Durch Inspektion aus der obigen Tabelle ist GCD für 108 und 240 12. Dies bedeutet, dass, wenn 12 wiederholt hinzugefügt wird, das Ergebnis zu 108 wird, was der kleinere beider Zahlen ist. Wenn die Zugabe von 12 fortgesetzt wird, wird das Ergebnis 240, was die größere von beiden Zahlen ist. Das ist:

12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240

Das ist:

108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240

Was bedeutet:

108 + 132 = 240

Wenn die GCD wiederholt hinzugefügt werden kann, um eine der Zahlen (108 und 240) zu geben, aus denen die GCD erforderlich ist, kann es möglich sein, eine Art Subtraktion wiederholt durchzuführen, beginnend mit den angegebenen Zahlen, um die GCD zu haben, um die GCD zu haben. Tatsächlich ist es möglich, eine bestimmte Art von Subtraktion wiederholt durchzuführen und den GCD zu erhalten. Dies beginnt mit dem Unterschied der angegebenen Zahlen.

Problem: Finden Sie den größten gemeinsamen Divisor (höchster gemeinsamer Faktor) für 108 und 240 durch Subtraktion.

Lösung:

240 - 108 = 132
132 - 108 = 24
108 - 24 = 84
84 - 24 = 60
60 - 24 = 36
36 - 24 = 12
24 - 12 = 12
12 - 12 = 0

Zwischen 108 und 240 ist 240 die größere Zahl. Nach der Differenz dieser gegebenen Zahlen werden die Differenz der resultierenden Differenz (132 für den ersten Schritt) und der Subtrahend (108 für den ersten Schritt) wiederholt erhalten, bis die endgültige Differenz Null ist. In den Schritten wird die kleinere Zahl von der größeren Zahl abgezogen. Im letzten Schritt sind die Minuend und der Subtrahend gleich. Der gleiche Wert ist der größte gemeinsame Divisor.

Lassen Sie die Zahlen, deren GCD benötigt wird, "a" und "B" sein. Wenn diese Zahlen keine GCD mehr als 1 haben, bedeutet dies, dass ihr größter gemeinsamer Divisor 1 ist. In der Programmierung ist die zeitliche Komplexität, um die GCD durch Subtraktion zu finden, O (A+B). Wenn 'A' 1 und B 6 ist, sind die Schritte ohne Programmierung:

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

Der GCD hier ist 1. Hier gibt es sechs Schritte und nicht sieben Schritte von (a + b). Bei der Programmierung wird jedoch die maximal mögliche Anzahl von Codevorgängen als Zeitkomplexität angenommen.

Codierung von GCD durch Subtraktion

Die Funktion für den größten gemeinsamen Divisor durch Subtraktion in Python lautet:

Def gcds (a, b):
Wenn a == b:
Rückkehr a
Wenn a> b:
Return GCDs (a - b, b)
anders:
Return GCDs (a, b - a)

Die erste Aussage kümmert sich um den letzten Mathematikschritt. Die nächste zusammengesetzte Aussage (wenn/sonst) führt die Subtraktion zwischen dem Minuend und der Differenz durch, je nachdem, welche größer ist.

Eingehende Übersicht über die GCD-Mathematik-Subtraktionen

240 - 108 = 132
132 = 12 x 11 (132 hat 12 als Faktor)
132 - 108 = 24
24 = 12 x 2 (24 hat 12 als Faktor)
108 - 24 = 84
84 = 12 x 7 (84 hat 12 als Faktor)
84 - 24 = 60
60 = 12 x 5 (60 hat 12 als Faktor)
60 - 24 = 36
36 = 12 x 3 (36 hat 12 als Faktor)
24 - 12 = 12
12 = 12 x 1 (12 hat einen Faktor oder 12 - selbst)
24 - 12 = 12
12 = 12 x 1 (12 hat einen Faktor oder 12 - selbst)

Der letzte Schritt hat einen Unterschied von 0. Es markiert das Ende der Subtraktionsschritte und gibt dem GCD als Subtrahend oder Minuend an.

GCD von Division

Zwischen 108 und 240 ist die GCD größer als 1.

12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240

Das ist:

108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240

Was bedeutet:

108 + 132 = 240

Das ist:

12 x 9 + 12 x 11 = 240

Auch 108 = 12 x 9 und 240 = 12 x 20.

Wenn die GCD nun mit einer ganzen Zahl (positive Ganzzahl) multipliziert werden kann, um eine der Zahlen (108 oder 240) zu geben, aus denen die GCD erforderlich ist, kann es möglich sein, wiederholt eine Art Teilung durchzuführen, beginnend mit dem gegebene Zahlen, um die GCD zu haben. Tatsächlich ist es möglich, eine bestimmte Art von Teilung wiederholt durchzuführen und die GCD zu erhalten. Diese Abteilung ist eine spezielle Wiederholungsmodulabteilung. Es beginnt mit der Modulteilung der angegebenen Zahlen.

In der Modul -Abteilung ist der Rest für den Quotienten die Antwort, wenn die Dividende durch den Divisor geteilt wird.

Problem: Finden Sie den größten gemeinsamen Divisor (höchster gemeinsamer Faktor) für 108 und 240 nach Modul -Division:

Lösung:

240 % 108 = 24 (i.e. 2 R 24)
108 % 24 = 12 (i.e. 4 R 12)
24 % 12 = 0 (i.e. 2 r 0)

In der letzten Zeile, in der der Rest Null ist, ist der Divisor der größte gemeinsame Divisor (höchster gemeinsamer Faktor).

Dieses Problem besteht darin, die GCD zwischen 108 und 240 nach Division zu finden. Die Lösung hier machte 3 Schritte. Das vorherige Problem war ähnlich, aber es bestand darin, durch Subtraktion nach dem gleichen GCD zu suchen. Und es hatte 8 Schritte. Während die zeitliche Komplexität für die Subtraktionsmethode O (A + B) ist, lautet die zeitliche Komplexität der Teilungsmethode O (log (a + b)).

In der Modulabteilung spielt es keine Rolle, ob 'A' größer als B oder B größer ist als 'A'; Der Rest ist die gleiche positive Ganzzahl.

Finden Sie mathematisch den größten gemeinsamen Divisor nach Teilung für die Zahlen 5 und 2.

Lösung:

5 % 2 = 1
1 % 1 = 0

Die GCD ist 1. Dies erforderte zwei mathematische Schritte.

Codierung von GCD nach Division

Das Wort „Division“ hier bezieht sich auf die Modulabteilung. Die Funktion ist:

Def GCDD (a, b):
if (a % b == 0):
Rückkehr b
anders:
Return GCDD (b, A % b)

Die IF-Teil des If/Else-Construct kümmert sich um die letzte mathematische Aussage für die Schritte der Modulabteilung. Der sonstige Teil kümmert sich um die tatsächliche Modulo -Division (was zum Rest führt). In der Modulabteilung spielt es keine Rolle, ob 'A' größer als B oder B größer ist als 'A'; Der Rest ist die gleiche positive Ganzzahl.

Um einen GCD anzurufen und auszudrucken, kann der folgende Code verwendet werden:

Ret = GCDD (240, 108)
print (ret, end = '\ n')

Eingehende Übersicht über die GCD-Mathematikabteilungen

240 % 108 = 24 (die GCD zwischen 240 und 108 ist 12)
24 = 12 x 2 (24 hat 12 als Faktor)
108 % 24 = 12 (die GCD zwischen 108 und 24 ist 12)
12 = 12 x 1 (12 hat 12 als Faktor selbst)
24 % 12 = 0 (die GCD zwischen 24 und 12 ist 12)

Es wurde hier demonstriert, dass:

GCD (A, B) = GCD (B, R)

wobei 'a' und b zwei verschiedene ganze Zahlen sind und 'R' der Rest der Trennung zwischen A und B ist. B kann größer sein als 'A' oder 'A' kann größer sein als B. Wenn der Rest einer Teilung nicht Null ist, dann ist der größte gemeinsame Divisor zwischen den beiden angegebenen Zahlen der gleiche gemeinsame Divisor zwischen dem Divisor und dem Rest. Dies verläuft in verschiedenen Schritten, bis der Rest Null ist, auch wenn die GCD 1 ist.

Der letzte Schritt hat einen Rest von 0. Es markiert das Ende der Modul -Divisionsschritte und der GCD ist der Divisor.

Abschluss

Der größte gemeinsame Divisor kann durch wiederholte Subtraktionen oder wiederholte Modulo -Abteilungen bestimmt werden.

Wenn es durch Subtraktion der Fall ist, liegt der Rest der Subtraktionen nach der Subtraktion der angegebenen Zahlen zwischen der Differenz und dem Minuend, je nachdem, welche größer ist. Wenn die Differenz Null ist, ist der Subtrahend gleich dem Minuend und entweder das GCD.

Wenn es nach der Teilung ist, sind die wiederholten Abteilungen Modul -Abteilungen. In dieser Situation befindet sich nach der Modulaufteilung der angegebenen Zahlen der Rest der Modulabteilungen zwischen dem Divisor und dem Rest, je nachdem, welche größer ist. Wenn der Rest Null ist, ist der Divisor der GCD. Streng genommen spielt es in der Modul -Division keine Rolle, ob 'A' größer als B oder B größer ist als 'A'; Der Rest ist die gleiche positive Ganzzahl.