Kurseinheit 3 - größter gemeinsamer Teiler

Dr Franke Ghostwriter
KE 3 - größter gemeinsamer Teiler

Hallo,

in KE 3 soll man eine Übungsaufgabe zum ggt (Euklid) erstellen.
Die Lösung ist folgende:


public int gcd(int a, int b) // wir gehen davon aus,
{ // dass a, b > 0
int m = a; //Schritt 1: setze m=a, und n=b
int n= b;
int r; // Hilfsvariable
do {
if (m < n) // Schritt 2: falls m < n
{
r = m; // vertausche m und n
m = n;
n = r;
}
r = m - n; // Schritt 3: berechne r
m = n; // Schritt 4: setze m und n
n = r;
} while ( r != 0); // Schritt 5: weiter mit Schritt 2
return m; // beende das Verfahren, m liefert
} // den ggt von a und b


Ich Frage mich nur, ob die Hilfsvariablen und das vertauschen überhaupt notwendig sind?
Reicht nachstehender Code nicht auch aus?
while ( a != b )
{
if ( a > b )
{
a -= b;
}
else if ( a < b )
{
b -= a;
}
}
return a;
 
Ja dein Code ist auf jedenfall kürzer, was ich nur anmerken möchte ist, bei der Musterlösung werden schon mit Absicht die variablen a und b durch m und n ersetzt, weil man sonst nach dem alg. nicht mehr auf diese zugreifen kann, einfaches beispiel wäre zb, wenn man vor dem return direkt eine ausgabe machen möchte a la "Der ggT von 'a' und 'b' ist 'm'." wird es schwierig, weil du direkt a und b veränderst, soll keine Kritik sein nur eine kleine Anmerkung... Das kann einem nämlich später, wenn es nicht mehr um primitive Typen sondern um Objekte geht, probleme bereiten, wenn man das ursprungsobjekt verändert.
ggf noch schneller ginger:
int m=a;
int n=b;
int r;
while(n!=0) {
r = m%n;
m = n;
n = r;
}
return m;
das ist der "neue" Euklid
 
Ja bei Objekten gibt es ein paar besonderheiten dabei... weil m = a, nicht so ganz das macht was man erst denkt, weil wenn man nun etwas in m ändert ändert sich dies auch bei a... Dafür gibt es die methode clone(), da durch wird sicher gestellt, dass änderungen an m nicht auf a zurück wirken. Ich versuch es mal einem Beispiel zu verdeutlichen.
Ich habe eine Klasse Test geschrieben, die ein Attribut (String str) besitzt und in der auch 2 Objekte von Test erzeugt werden t1 und t2. Habe hoffentlich alles ausreichend Kommentiert und der unterschied zwischen = und clone() wird deutlich.
Der Code kann so in BlueJ in eine Klasse Test eingefügt werden und über die Methode void main(..) aufgerufen werden.
Code:
/**
 * Die Klasse <b>Test</b> soll den Unterschied zwischen = und clone() verdeutlich.<hr />
 * Kurze Erklärung zu sachen die Überlesen werden sollten:<br />
 * <i>implements Cloneable</i>, ist nötig, damit man Objekte vom Typ Test clonen kann.<br />
 * <i>throws CloneNotSupportedException</i> bei manchen Methoden<br />
 * habe ich eingefügt um die Lesbarkeit zu erhöhen und keine try-catch- Blöcke einfügen muss.
 * @author Martin
 * @version 0.1
 *
 */
public class Test implements Cloneable{
    private String str;
    
    /**
     * Erzeugt ein Test Objekt mit einem bestimmten String.
     * @param str
     */
    public Test(String str) {
        this.str = str;
    }
    
    /**
     * Ändert den aktuellen String auf den String neu
     * @param neu
     */
    public void setStr(String neu) {
        this.str = neu;
    }
    
    /**
     * Main methode, kann ohne Objekt aufgerufen werden.
     * @param args
     * @throws CloneNotSupportedException
     */
    public static void main(String[] args) throws CloneNotSupportedException {
        Test t1 = new Test("a");    // Objekt von Test erzeugen.
        Test t2;                    // t2 initialisieren.
        
        // Gleichsetzen:
        t2 = t1;
        System.out.println(t1 + " " + t2);    // Ausgabe: a a
        
        // t1 wird geändert auf "b":
        t1.setStr("b");
        System.out.println(t1 + " " + t2);    // Ausgabe: b b
        
        // t2 wird geändert auf "c":
        t2.setStr("c");
        System.out.println(t1 + " " + t2);    // Ausgabe: c c
        
        // changeDirect aufruf (a=b):
        changeDirect(t1);
        System.out.println(t1 + " " + t2);    // Ausgabe: d d
        
        // changeIndirect aufruf (a=b):
        changeIndirect(t1);
        System.out.println(t1 + " " + t2);    // Ausgabe: e e
        
        // changeClone aufruf (a=b):
        changeClone(t1);
        System.out.println(t1 + " " + t2);    // Ausgabe: e e
                
        System.out.println();    // Leer Zeile
        
        
        t1 = new Test("a");        // t1 auf Ausgang zurücksetzen.
        t2 = null;                // t2 auf Ausgang zurücksetzen.
        
        // Clone():
        t2 = (Test) t1.clone();
        System.out.println(t1 + " " + t2);    // Ausgabe: a a
        
        // t1 wird geändert auf "b":
        t1.setStr("b");
        System.out.println(t1 + " " + t2);    // Ausgabe: b a
        
        // t2 wird geändert auf "c":
        t2.setStr("c");
        System.out.println(t1 + " " + t2);    // Ausgabe: b c
        
        // changeDirect aufruf (b = a.clone()):
        changeDirect(t1);
        System.out.println(t1 + " " + t2);    // Ausgabe: d c
        
        // changeIndirect aufruf (b = a.clone()):
        changeIndirect(t1);
        System.out.println(t1 + " " + t2);    // Ausgabe: e c
        
        // changeClone aufruf (b = a.clone()):
        changeClone(t1);
        System.out.println(t1 + " " + t2);    // Ausgabe: e c
    }
    
    /**
     * Ändert den String von t direkt.
     * @param t
     */
    public static void changeDirect(Test t) {
        t.setStr("d");
    }
    
    /**
     * Ändert den String von t indirekt über t3 (t3 = t).
     * @param t
     */
    public static void changeIndirect(Test t) {
        Test t3 = t;
        t3.setStr("e");
    }
    
    /**
     * Ändert den String von t an einem Clone t3 (t3 = t.clone())
     * @param t
     * @throws CloneNotSupportedException
     */
    public static void changeClone(Test t) throws CloneNotSupportedException {
        Test t3 = (Test)t.clone();
        t3.setStr("f");
    }
    
    @Override
    public String toString() {
        return str;
    }

}
 
Oben