Frage zum Euklidischen Algorithmus

[KogoroMori21]

Guten Tag, meine Aufgabe ist es den Euklidischen Algorithmus darzustellen und den habe ich soweit verstanden und gelöst, aber ich versteh meinen Code bei einer Sache nicht so ganz. (Genaue Frage steht unten)

[CODE lang="java" title="Euklidischer Algorithmus"] public Integer groessterGemeinsamerTeiler2(Integer a, Integer b) {
if (a==null) {
return b;
}
while(b!=0) {
if (a > b) {
a = a - b;

} else {
b = b - a;
}
}
return a;
}[/CODE]

Das ist meine Ausgabe:


Er berechnet den GGT jeweils richtig aus, auch von (156,66) = 6 , nur versteh ich nicht genau warum er das ausrechnen kann. Wenn ich mir den Code so anschaue, dann müsste doch bei ggT(156,66) das Ergebnis 90 sein, weil ich doch durch die erste if-Abfrage, wenn (156>66) , dann a = 156-66; stehen hab. Deshalb versteh ich die Berechnung der 6 nicht, bei den anderen Beispielen versteh ich es.

 

[kneitzel]

Das Ergebnis 90 ist doch nur ein Zwischenergebnis. Das ist doch in einer while Schleife und daher wird weiter gerechnet.

 

[temi]

[CODE lang="java" title="Mit korrekter Einrückung"]
public Integer groessterGemeinsamerTeiler2(Integer a, Integer b) {
if (a == null) {
return b;
}

while(b != 0) {

if (a > b) {
a = a - b;
} else {
b = b - a;
}

}

return a;
}[/CODE]

Nebenbei: Musst du "Integer" verwenden? Es ist immer günstiger den primitiven Datentyp "int" zu verwenden, wenn es keine Notwendigkeit für die Wrapper-Klassen gibt.

 

[KogoroMori21]

[CODE lang="java" title="Mit korrekter Einrückung"]
public Integer groessterGemeinsamerTeiler2(Integer a, Integer b) {
if (a == null) {
return b;
}

while(b != 0) {

if (a > b) {
a = a - b;
} else {
b = b - a;
}

}

return a;
}[/CODE]

Nebenbei: Musst du "Integer" verwenden? Es ist immer günstiger den primitiven Datentyp "int" zu verwenden, wenn es keine Notwendigkeit für die Wrapper-Klassen gibt.

Ja muss ich leider

 

[Onur]

dann müsste doch bei ggT(156,66) das Ergebnis 90 sein,

Wenn du dir mal das genau überlegst wie soll 90 ein Teiler von 66 sein 😉

Den größte gemeinsame Teiler (ggT) kann du zur not über den weg der Primfaktorzerlegung ermittel um es gegenprüfen zu können, hier wird es auch echt einfach erklärt wie du es machen kannst.


Kannst du den fall b == null ausschließen?

 

[mihe7]

Den größte gemeinsame Teiler (ggT) kann du zur not über den weg der Primfaktorzerlegung ermittel um es gegenprüfen zu können, hier wird es auch echt einfach erklärt wie du es machen kannst.

Das geht auch einfach über BigInteger#gcd

 

[Onur]

Das geht auch einfach über BigInteger#gcd

Das geht auch ^_^

Ich verscuh mich im Forum für die anfänger Themen daran zu halten keine fertigen Lösungen zu schreiben (obwohl es manschmal echt heftig in meinen Fingern juckt), sonder eher so Denkanstöße zu geben.

 

[mihe7]

Das geht auch ^_^

Ich verscuh mich im Forum für die anfänger Themen daran zu halten keine fertigen Lösungen zu schreiben (obwohl es manschmal echt heftig in meinen Fingern juckt), sonder eher so Denkanstöße zu geben.

Das ist auch völlig richtig BigInteger#gcd ist auch keine Lösung sondern dient lediglich der Kontrolle ("um es gegenprüfen zu können").

 

[Onur]

Das ist auch völlig richtig BigInteger#gcd ist auch keine Lösung sondern dient lediglich der Kontrolle ("um es gegenprüfen zu können").

okay (BigInteger#gcd) wusste ich selber nicht bin auch aus dem C# Berreich...

was ich nicht verstehe ist wieso der TE der Meinung ist das es 90 sein muss.

Er berechnet den GGT jeweils richtig aus, auch von (156,66) = 6 , nur versteh ich nicht genau warum er das ausrechnen kann. Wenn ich mir den Code so anschaue, dann müsste doch bei ggT(156,66) das Ergebnis 90 sein, weil ich doch durch die erste if-Abfrage, wenn (156>66) , dann a = 156-66; stehen hab. Deshalb versteh ich die Berechnung der 6 nicht, bei den anderen Beispielen versteh ich es.

er hast den Euklidischen ALgorithmus richtig Implementiert ( mit ein par schönheitsfehlern )..
Wieso Wundert er sich das das Ergebnis richtig ist

 

[mihe7]

Wieso Wundert er sich das das Ergebnis richtig ist

Weil er die Schleife ignoriert. 156 > 66 also wird 156-66 gerechnet und damit wird a zu 90.

Würde er die Schleife berücksichtigen, ging es eben weiter:

90 > 66 also wird 90 - 66 gerechnet und damit wird a zu 24.
24 <= 66 also wird 66 - 24 gerechnet und damit wird b zu 42.
24 <= 42 also wird 42 - 24 gerechnet und damit wird b zu 18.
24 > 18 also wird 24 - 18 gerechnet und damit wird a zu 6.
6 <= 18 also wird 18 - 6 gerechnet und damit wird b zu 12.
6 <= 12 also wird 12 - 6 gerechnet und damit wird b zu 6.
6 <= 6 also wird 6 - 6 gerechnet und damit wird b zu 0.

Jetzt wird die Schleife verlassen und a (6) zurückgegeben.

 

[Onur]

Uff jetzt habe ich dich erst verstanden so viel bescheurter Zufall muss erst mal gegeben sein....

Du hast immer werte genommen die bei deinem ersten Durchgang ( schon die richtigen ergebnisse geliefert haben ).
weswegen du vlt. davon ausgegangen bist das der Euklidischen Algorithmus dir eine einfache Subtraction ausliefert.


+ das hier

Weil er die Schleife ignoriert. 156 > 66 also wird 156-66 gerechnet und damit wird a zu 90.

Würde er die Schleife berücksichtigen, ging es eben weiter:

90 > 66 also wird 90 - 66 gerechnet und damit wird a zu 24.
24 <= 66 also wird 66 - 24 gerechnet und damit wird b zu 42.
24 <= 42 also wird 42 - 24 gerechnet und damit wird b zu 18.
24 > 18 also wird 24 - 18 gerechnet und damit wird a zu 6.
6 <= 18 also wird 18 - 6 gerechnet und damit wird b zu 12.
6 <= 12 also wird 12 - 6 gerechnet und damit wird b zu 6.
6 <= 6 also wird 6 - 6 gerechnet und damit wird b zu 0.

Jetzt wird die Schleife verlassen und a (6) zurückgegeben.

@KogoroMori21 aber trotztdem was machst du wenn b == null ist dass musst du mit berücksichten bitte und auch den Fall das beide eingabe Parameter == null sind

 

[KogoroMori21]

Ich danke euch @Onur @mihe7, ich hab das schon verstanden durch die Antwort von @kneitzel . Mein Fehler war einfach, dass ich die Schleife nicht berücksichtigt habe .
Aber danke euch allen trotzdem <3