Frage zum Euklidischen Algorithmus

KogoroMori21

KogoroMori21

Aktives Mitglied
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)

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;
 }

Das ist meine Ausgabe:
1621703445442.png


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.
 
temi

temi

Top Contributor
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;
}

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

KogoroMori21

Aktives Mitglied
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;
}

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
 
O

Onur

Mitglied
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?
 
Zuletzt bearbeitet:
mihe7

mihe7

Top Contributor
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").
 
O

Onur

Mitglied
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

mihe7

Top Contributor
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.
 
O

Onur

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


1621703445442-png.15412

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
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Frage zu printWriter Java Basics - Anfänger-Themen 5
C Frage zu OLSMultipleLinearRegression Java Basics - Anfänger-Themen 31
S Verständnis-Frage zu einer HÜ? Java Basics - Anfänger-Themen 1
F Frage betreff Programm mit dem man C++-Code in JAVA-Code übersetzen lassen kann Java Basics - Anfänger-Themen 2
L Frage zur Ticket Maschine Java Basics - Anfänger-Themen 1
J Frage zu OOP-Klassendiagramm Java Basics - Anfänger-Themen 8
OSchriever Frage zu Compiler Java Basics - Anfänger-Themen 8
H Frage zu Throw Exception Java Basics - Anfänger-Themen 2
TimoN11 Frage zu Java-Vererbung (Cast) Java Basics - Anfänger-Themen 5
Bademeister007 Hallo Leute ich hab eine Frage zur ArrayList Java Basics - Anfänger-Themen 8
F Frage betreff Programmierbücher zu Lagerverwaltung als Konsolenprogramm Java Basics - Anfänger-Themen 3
dieter000 Kurze Frage kann mir ejmand kurz diesen Code erklären, bzw wie man die zeilen erklärt und so Java Basics - Anfänger-Themen 1
I String.split regex Frage Java Basics - Anfänger-Themen 2
C Best Practice Frage zum MVC-Pattern Java Basics - Anfänger-Themen 2
dieter000 Frage zu einem Beispiel... Java Basics - Anfänger-Themen 5
J Frage zum Loggen Java Basics - Anfänger-Themen 18
J Methoden Frage: Array-Werte in anderer Methode ändern Java Basics - Anfänger-Themen 4
Zrebna Frage zum "Referenzen-konzept" in Java Java Basics - Anfänger-Themen 8
JD_1998 Array-Position aus einer Methode in einer anderen ausgeben (Kurze Frage) Java Basics - Anfänger-Themen 2
marcooooo Frage zu bestimmten Beispiel Java Basics - Anfänger-Themen 31
NeoLexx equals()-Methode Verständnis Frage anhand Code Beispiel Java Basics - Anfänger-Themen 22
N Input/Output Eine Frage über system.out.println. Java Basics - Anfänger-Themen 10
B Erste Schritte Learning Coding (!) Frage an erfahrene Programmierer. Java Basics - Anfänger-Themen 23
M konzeptuelle Frage: In welcher Klasse definiert man am Besten Methoden, die die Kommunikation mit dem User regeln? Java Basics - Anfänger-Themen 8
B Frage zum Code verständnis im Resultat Java Basics - Anfänger-Themen 10
C Exception-Frage Java Basics - Anfänger-Themen 3
J Eine Frage zur Schreibweise == ? : Java Basics - Anfänger-Themen 3
S Frage des Designs Java Basics - Anfänger-Themen 1
JavaTalksToMe Extends/Implements Frage Java Basics - Anfänger-Themen 3
pkm Frage zu Servletfunktion Java Basics - Anfänger-Themen 0
B Frage zur Währungsumrechnung Java Basics - Anfänger-Themen 3
S Allgemeine Frage über Generics und Vererbungen Java Basics - Anfänger-Themen 5
Kirby.exe Frage zur Verwendung von Interfaces Java Basics - Anfänger-Themen 6
D Frage zu Strings einer Exception Java Basics - Anfänger-Themen 4
L Wie frage ich ab, ob in einem Array, Werte doppelt vorkommen? Java Basics - Anfänger-Themen 4
D Frage zur IDE IntelliJ IDEA Java Basics - Anfänger-Themen 6
H Frage zum 2d Array Java Basics - Anfänger-Themen 1
N Frage zum Newton-Fraktal Java Basics - Anfänger-Themen 1
H Frage zu interfaces Java Basics - Anfänger-Themen 1
J Frage dazu Variablen klassenübergreifend zu verändern Java Basics - Anfänger-Themen 22
I Frage zu SkipList Java Basics - Anfänger-Themen 4
G Frage zu JScrollPane Java Basics - Anfänger-Themen 12
Kirby.exe Allgemeine Frage Java Basics - Anfänger-Themen 3
W Frage zu anonymen Klassen Java Basics - Anfänger-Themen 4
J Kleine Frage zu OOP Java Basics - Anfänger-Themen 371
S Frage Klasse und Objekte Java Basics - Anfänger-Themen 2
F Frage zu Iteratoren Java Basics - Anfänger-Themen 2
C Erste Schritte Frage zur ArrayList Java Basics - Anfänger-Themen 15
J Frage zur Vererbung Java Basics - Anfänger-Themen 1
H Frage zur ermittlung eines doppelte Paars aus Sotieralgorithmus Java Basics - Anfänger-Themen 4
H Frage zum Array Java Basics - Anfänger-Themen 17
G Schach -Frage 2- Maussteuerung Java Basics - Anfänger-Themen 7
G Schach in Java - Allgemeine Frage zur Architektur Java Basics - Anfänger-Themen 7
B Fachliche Frage bei Rechnungen Java Basics - Anfänger-Themen 16
B Frage zu: String... strings -> Ungleiche Anzahl an Parameter? Java Basics - Anfänger-Themen 4
B Frage zu Datenbank Design - Rechnungen, Angebote... und deren Positionen Java Basics - Anfänger-Themen 4
H Frage zu Parameter einer Methode Java Basics - Anfänger-Themen 2
H Einfache Frage zur Punktnotation objektname.methode(wert) Java Basics - Anfänger-Themen 2
H Frage zu Parameter einer Methode Java Basics - Anfänger-Themen 3
H Frage zur if-Bedingung bzw switch case Java Basics - Anfänger-Themen 6
H Frage um Eingbeaufforderung zu realisieren Java Basics - Anfänger-Themen 4
H Frage zu Methoden/Funktionen Java Basics - Anfänger-Themen 3
X Frage zur einer ArrayList in einer ArrayList Java Basics - Anfänger-Themen 5
S Frage zu Scanner Java Basics - Anfänger-Themen 3
M Rationale Zahl erkennen - Kurze Frage zum Restwert nach Division Java Basics - Anfänger-Themen 3
D Komplizierte Frage zum Writer Java Basics - Anfänger-Themen 4
I Frage zu Generics und Wildcards Java Basics - Anfänger-Themen 2
G Frage an die Experten Java Basics - Anfänger-Themen 39
H Frage zu fehler Java Basics - Anfänger-Themen 24
F Konstruktor richtig implementiert? Frage zu Benutzereingaben... Java Basics - Anfänger-Themen 9
B Frage zu Arrays Java Basics - Anfänger-Themen 3
O Bedingter Operator eine Frage! Java Basics - Anfänger-Themen 10
B Threads Thread sleep() Method einfache Frage Java Basics - Anfänger-Themen 8
W Stream Array List - Frage Java Basics - Anfänger-Themen 5
B Verständnis Frage zu der Aufgabe Java Basics - Anfänger-Themen 30
Koookie Kleines Frage - Antwort Programm (Anfänger) Java Basics - Anfänger-Themen 5
O Ganz einfache Frage - Array Java Basics - Anfänger-Themen 5
F Erste Schritte Frage zu simplem Taschenrechner(switch) Java Basics - Anfänger-Themen 16
D Frage zu Exceptions Java Basics - Anfänger-Themen 8
H Frage um den Code bildlich darzustellen Java Basics - Anfänger-Themen 2
D regex Aufbau Frage Java Basics - Anfänger-Themen 4
J Frage zu Pfaden Java Basics - Anfänger-Themen 1
J Frage zur Darstellung Java Basics - Anfänger-Themen 2
D Wie frage ich ab ob die Linke maus Taste gedrückt wurde? Java Basics - Anfänger-Themen 3
J Float Frage Java Basics - Anfänger-Themen 1
H Frage zu Übungsaufgabe, Array Java Basics - Anfänger-Themen 7
ralfb1105 Frage zu Thread Synchronisation mit wait() und notify() Java Basics - Anfänger-Themen 3
D Doofe Frage... Java Basics - Anfänger-Themen 2
M Frage, wie dieser Code funktioniert, bzw. weshab er bei mir nicht funktioniert Java Basics - Anfänger-Themen 4
L Frage zu LibGDX Java Basics - Anfänger-Themen 2
O boolean Array Frage! Java Basics - Anfänger-Themen 4
A Frage zur Aufgabe Uhrzeit einstellen mit Objekten Java Basics - Anfänger-Themen 18
S Frage zu Rekursion... Java Basics - Anfänger-Themen 15
S Noch eine Frage zur Rekursion... Java Basics - Anfänger-Themen 11
S Frage zu einer Rekursion Java Basics - Anfänger-Themen 15
S Sudoku Checker Frage Java Basics - Anfänger-Themen 1
pkm Frage wegen möglichem grouping-hack Java Basics - Anfänger-Themen 22
S Erste Schritte Berechnung des Paketportos - Problem/Frage Java Basics - Anfänger-Themen 52
K Operatoren Frage zu Vergleichsoperatoren Java Basics - Anfänger-Themen 3
R Input/Output Frage zu System.out.println Java Basics - Anfänger-Themen 5

Ähnliche Java Themen


Oben