Größter gemeinsamer Teiler bei Java

Computer: Software & Programmierung Java
#1

Hallo!
Momentan beschäftigen wir uns in Informatik mit Java, wo wir nun den größten gemeinsamen Teiler herausfinden müssen.
Grundsätzlich verstehe ich die verschiedenen Wege in der Mathematik, um an den GGT ranzukommen… nur haben wir ein Skript erhalten, wo ich irgendwie keine der Methoden (Primfaktorzerlegung, Teilermengen, Algorithmus von Euklid) wiederfinden kann…

Zitat:

___________________________________________

Vielleicht erinnerst du dich an deinen Mathematikunterricht früherer Jahrgangstufen.
Dort wirst du verschiedene Lösungsmöglichkeiten zur ggT-Berechnung
kennengelernt haben: eine basierend auf den beiden Primfaktorzerlegungen …, und
mindestens eine weitere basierend auf den Teilermengen beider Zahlen …
Das letztere der genannten Verfahren greifen wir zunächst auf, d. h. wir suchen
Teiler beider Zahlen. Java hat einen Operator, mit dem man den Rest einer Division
berechnen kann:
Der Befehl int rest = a % b bedeutet: a wird durch b geteilt und der Rest dieser
Division wird in der Variablen rest gespeichert. Z. B. würde die Variable
int rest = 17 % 5 den Wert 2 bekommen.
Wenn du also zunächst probierst, ob die größere der beiden Zahlen durch die
kleinere teilbar ist (was i. a. recht selten sein wird…), dann die kleinere wiederholt um
eins verringerst, solange bis diese „Laufzahl“ beide gegebenen Zahlen a und b
ganzzahlig teilt, so hast du mittels dieser „Laufzahl“ den ggT von a und b bestimmt!
Wir haben es hier also wieder mit einer Wiederholungsanweisung zu tun, welche
sich allerdings ein wenig von der bekannten for-Schleife unterscheidet.

______________________________________

Was ist mit Laufzahl gemeint? Und wieso muss ich eine Zahl um eins verringern? Kann mir vielleicht jemand bitte ein Zahlenbeispiel machen?

Danke im Voraus!!

#2

Hi,
ich hab zwar jetzt nicht so ganz deine Frage verstanden aber ich habe hier eine Lösung für dich:
http://wiki.zum.de/Java/ggT
Diese Lösung nutzt den Algorithmus von Euklid.
Erklären kann es dir sicher wer anders.
Lg Knerd

#3

Hallo.

Das letztere der genannten Verfahren greifen wir zunächst auf,
d. h. wir suchen
Teiler beider Zahlen. Java hat einen Operator, mit dem man den
Rest einer Division
berechnen kann:
Der Befehl int rest = a % b bedeutet: a wird durch b geteilt
und der Rest dieser
Division wird in der Variablen rest gespeichert. Z. B. würde
die Variable
int rest = 17 % 5 den Wert 2 bekommen.
Wenn du also zunächst probierst, ob die größere der beiden
Zahlen durch die
kleinere teilbar ist (was i. a. recht selten sein wird…),
dann die kleinere wiederholt um
eins verringerst, solange bis diese „Laufzahl“ beide gegebenen
Zahlen a und b
ganzzahlig teilt, so hast du mittels dieser „Laufzahl“ den ggT
von a und b bestimmt!
Wir haben es hier also wieder mit einer Wiederholungsanweisung
zu tun, welche
sich allerdings ein wenig von der bekannten for-Schleife
unterscheidet.

______________________________________

Was ist mit Laufzahl gemeint? Und wieso muss ich eine Zahl um
eins verringern? Kann mir vielleicht jemand bitte ein
Zahlenbeispiel machen?

Mit Laufzahl ist so etwas gemeint wie die Variable bei einer for-Schleife.
Mal eine Vorüberlegung, du hast 2 Zahlen, a und b. Der ggT muss offensichtlich kleiner oder gleich der kleineren dieser beiden Zahlen sein. Wenn du also mit der kleineren anfängst, prüfst, ob diese beide teilt, und wenn nicht, um eins verringerst, bis das dann geht, dann findest du den ggT.
Beispiel:
a=16, b=6
i = b = 6.
Teilt i a? 16%6=4 -> nein
i = i - 1 = 5
Teilt i a? 16%5=1 -> nein
i = i - 1 = 4
Teilt i a? 16%4=0 -> ja
Teilt i b? 6%4=2 -> nein
i = i - 1 = 3
Teilt i a? 16%3=1 -> nein
i = i - 1 = 2
Teilt i a? 16%2=0 -> ja
Teilt i b? 6%2=0 -> ja
2 ist also ggT von 16 und 6.

Sebastian.

#4

Achso vielen Dank!! Welches Verfahren wird denn verwendet? Wie heißt es denn mathematisch?

#5

Hallo.

Achso vielen Dank!! Welches Verfahren wird denn verwendet? Wie
heißt es denn mathematisch?

Das ist der Euklidische Algorithmus.

Sebastian.

#6

Danke…

Ich weiß nur nicht, wie ich in eine while-Schleife folgende Bedinungen einbauen soll:

Input: a, b: zwei ganze Zahlen
Output: eine ganze Zahl

__________________________________

Lokal: laufzahl eine ganze Zahl
gefunden eine boolsche Variable

_____________________________________

• wenn a

#7

Hi,

machs dir nicht so schwer :wink:

public int ggt(int a, int b) {
int min = Math.min(a, b); // Schon hast du die kleinere Zahl
for (int i=min; i>=2; i–) { // Du testest alle Zahlen bis zur 2
// Wenn bis dahin kein ggt gefunden
// wurde, bleibt nur die 1
if (a%i == 0 && b%i == 0) { // der Test
return i; // Dein Ergebnis
}
}
return 1; // Falls sonst kein ggT gefunden wurde…
}

Grüße, Keks

#8

Danke :smile:
Aber wir müssen eine while-Schleife benutzen…

#9

Danke :smile:

Kein Ding

Aber wir müssen eine while-Schleife benutzen…

Die kleine Änderung sollte kein Problem für dich sein :wink:

Grüße, Keks