Euklid: Pseudocode -> Java-Code

Computer: Software & Programmierung Java
#1

Hallo an alle!

Ich bin am Einbinden des erweiterten euklid. Algo. in rekursiver Form.
Ich habe dazu auf wikipedia Pseudocode gefunden:
http://de.wikipedia.org/wiki/Erweiterter_euklidische…

extended\_euclid(a,b)
1 wenn b = 0
2 dann return (a,1,0)
3 (d',s',t') 

Ich bin nun so weit:


    
     public BigInteger[] extEuklid(BigInteger a1, BigInteger b1, boolean first) {
     if (first) {
     BigInteger[] euklid = new BigInteger[3];
    
     }
     if (b1.compareTo(BigInteger.ZERO) == 0) {
     euklid[0] = a1;
     euklid[1] = BigInteger.ONE;
     euklid[2] = BigInteger.ZERO;
     return euklid;
     }
     3 (d',s',t') 
    Was mache ich aber mit den Zeilen 3-5.
    Muss ich hier drei Variablen anlegen d', s' und t' anlegen und diese setzen durch Aufruf der Methode extEuklid()?
    Nur dann ist mir Zeile 4 unklar: Brauche ich nun auch noch drei Variablen d, s und t (ohne Hochkomma)?
    Und was soll das für eine Berechnung sein: ?
    (d',t',s' - floor(a/b)t')
    
    Hoffe es hat jemand eine Idee?
    
    Danke + Gruß PHANTOM
#2

3 (d’,s’,t’)
Was mache ich aber mit den Zeilen 3-5.
Muss ich hier drei Variablen anlegen d’, s’ und t’ anlegen und
diese setzen durch Aufruf der Methode extEuklid()?

Richtig. Die Methode extEuklid() gibt dir ja ein Tripel aus drei Werten zurück.

Nur dann ist mir Zeile 4 unklar: Brauche ich nun auch noch
drei Variablen d, s und t (ohne Hochkomma)?

Wenn du es so implementieren willst wie in dem Pseudocode angeben, dann ja.

Und was soll das für eine Berechnung sein: ?
(d’,t’,s’ - floor(a/b)t’)

Die Berechnung lautet doch: (d,s,t)

#3

Ah, danke, jetzt habe ich es kapiert wie diese Zuordnung zu lesen ist.
Ja, diese Variablen mit dem ’ brauche ich gar nicht.

Ich hänge nur an dieser Umsetzung noch:
floor(a/b)

-> a und b sind bei mir BigInteger, also:
floor(a.divide(b))

Nur ist das floor ja nicht auf BigInteger als Parameter ausgelegt.
Jetzt könnte ich zwar ein
floor((a.divide(b)).doubleValue())
machen, aber dann habe ich ja ein double-Wert und ich muss ja weiter mit BigInteger arbeiten.

Wie kann ich das floor auf „BigInteger-Verhältnisse“ schreiben?

Gruß PHANTOM

#4

Ich hänge nur an dieser Umsetzung noch:
floor(a/b)

-> a und b sind bei mir BigInteger, also:
floor(a.divide(b))

Nur ist das floor ja nicht auf BigInteger als Parameter
ausgelegt.

Das floor() brauchst du auch überhaupt nicht, weil a.divide(b) bereits nur den ganzzahligen Anteil der Division von a durch b liefert. Zur Erinnerung: BigInteger ist ja ein Ganzzahl-Typ, so dass hier überhaupt keine Nachkommastellen vorkommen können.