Einführung Algorithmen und Datenstrukturen

exemplarische Lösung der Aufgaben SS 03 von Markus Durzinsky. Zurück zur Algodat Hauptseite.

15. Übungsblatt

Aufgabe 71 - Geometrie-Objekte

Normarler Weise bevorzuge ich englische Bezeichnungen für Klassen und auch Kommentare in Englisch, weil diese dann allgemein verständlich sind (und auch besser klingen als deutsche Namen, und kürzer ist das Ganze auch noch).

Das Interface Moveable wurde schon in der Aufgabenstellung definiert:


public interface Moveable {
  void move(int dx, int dy);
}

Fangen wir nun mit dem Punkt an. So eine Objekt muss natürlich seine Position kennen. Also werden ihm ein paar Eigenschaften verpasst.


public class Point implements Moveable {

  protected int x, y;

  public Point() {
    this(0, 0);
  }

  public Point(int x, int y) {
    setPosition(x, y);
  }

  ...
}

Auch die Methoden zum Lesen und Verändern dieser Eigenschaften (die der Konstruktor schon verwendet) sollte man in der Klasse definieren.


  public void setPosition(int x, int y) {
    this.x = x;
    this.y = y;
  }

  public int getX() { return x; }
  public int getY() { return y; }

Nun muss noch das Interface Moveable implementiert werden. Zum Beispiel so:


  public void move(int dx, int dy) {
    x += dx;
    y += dy;
  }

Bei der Ausgabe einer Instanz ist es in Java üblich, den Namen der Klasse auszugeben, gefolgt von den Eigenschaften der Instanz eingeschlossen in eckige Klammern. Das sieht zum Beispiel so aus:


  java.awt.Color[r=0,g=255,b=0]

Den Namen der Klasse kann man entweder eintippen, oder den Aufruf getClass().getName() benutzen. Der funktioniert in jedem Objekt. Die Eigenschaften des Objekts kann man auch in eine eigene Methode auslagern. Das hat dann einige Vorteile beim Erweitern der Klasse: Wenn zum Beispiel eine andere Klasse von unserer erbt, liefert getClass().getName() automatisch den richtigen Namen (den der neuen Klasse). Die neue Klasse braucht nur die Methode für die Parameter zu überschreiben.


  public String toString() {
    return getClass().getName() + "[" + paramString() + "]";
  }

  protected String paramString() {
    return "x=" + x + ",y=" + y;
  }

Die Ausgabe lautet zum Beispiel: Point[x=10,y=15]

Als Beispiel zum Erweitern der Klasse sei folgendes gegeben:


public class ColoredPoint extends Point {

  protected Color color;

  // constructor, getColor, setColor, ...

  protected String paramString() {
    return super.paramString() + ",color="+color.toString();
  }
}

Eine entsprechende Ausgabe:


  ColoredPoint[x=10,y=15,color=java.awt.Color[r=0,g=255,b=0]]

Zu beachten ist, dass die toString() Methode nicht überschrieben werden muss und trotzdem der richtige Klassenname (ColoredPoint) erscheint, und dass die alte paramString() Methode benutzt werden kann.

Nun fehlt noch die Berechnung des Abstandes. Dabei hilft und Pythagoras bzw. der euklidische Abstand:


  public double distance(int x, int y) {
    x -= this.x;
    y -= this.y;
    return Math.sqrt(x * x + y * y);
  }

  public double distance(Point pt) {
    return (pt == null) ? -1.0 : distance(pt.x, pt.y);
  }

Die zweite Methode ist hilfreich um zum Beispiel die Länge einer Linie zu berechnen, wenn sie mit Hilfe zweier solcher Punkte gespeichert wurde: a.distance(b) statt a.distance(b.getX(), b.getY()).

Die beiden Klassen für eine Linie und ein Dreieck sind im Wesentlichen identisch (nur das beim Dreieck mit drei Punkten gerechnet wird). Wegen dieser (beinahen) Identität ist es durchaus sinnvoll das Dreieck als eine Erweiterung der Linie zu definieren. Dann können alle Methoden der Linie auch vom Dreieck benutzt werden (z.B. Verschieben der beiden Eckpunkte) und es muss nur noch der Unterschied (der dritte Punkt) implementiert werden.

Linie Dreieck

Als erstes definieren wir die Eigenschaften und Konstruktoren der Klassen. Da die beiden Punkte a und b als protected definiert wurden kann auch die Klasse Triangle darauf zugreifen.


public class Line implements Moveable {

  protected Point a, b;

  public Line() {
    this(0, 0, 0, 0);
  }

  public Line(Point a, Point b) {
    this(a.getX(), a.getY(), b.getX(), b.getY());
  }

  public Line(int x1, int y1, int x2, int y2) {
    setPosition(x1, y1, x2, y2);
  }
  ...
}

public class Triangle extends Line {

  protected Point c;

  public Triangle() {
    this(0, 0, 0, 0, 0, 0);
  }

  public Triangle(Point a, Point b, Point c) {
    this(a.getX(), a.getY(),
        b.getX(), b.getY(), c.getX(), c.getY());
  }

  public Triangle(int x1, int y1,
      int x2, int y2, int x3, int y3) {
    super(x1, y1, x2, y2);
    c = new Point(x3, y3);
  }
  ...
}

Die Methoden zum direkten Auslesen und Ändern der Koordinaten. Dabei können natürlich die schon in Point definierten Methoden benutzt werden. Wer Lust hat, kann auch noch Methoden schreiben, an die Objekte vom Typ Point übergeben werden. Dabei muss aber aufgepasst werden. Dieser Punkt kann ja nach dem Schreiben der Position verändert werden, was keine Auswirkungen auf die Linie haben darf. Also nicht einfach die Referenz kopieren, sondern ein neues Objekt erstellen. (Solche Probleme hat man nicht, wenn ein Objekt nicht mehr verändert werden darf, aber der Punkt sollte ja eine move() Methode enthalten)


  public void setPosition(int x1, int y1,
      int x2, int y2) {
    a = new Point(x1, y1);
    b = new Point(x2, y2);
  }

  public int getX1() { return a.getX(); }
  public int getY1() { return a.getY(); }
  public int getX2() { return b.getX(); }
  public int getY2() { return b.getY(); }

  public void setPosition(int x1, int y1,
      int x2, int y2, int x3, int y3) {
    super.setPosition(x1, y1, x2, y2);
    c = new Point(x3, y3);
  }

  // get[X,Y][1,2] werden von Line vererbt

  public int getX3() { return c.getX(); }
  public int getY3() { return c.getY(); }

Das Interface Moveable muss auch noch implementiert werden.


  public void move(int dx, int dy) {
    a.move(dx, dy);
    b.move(dx, dy);
  }

  public void move(int dx, int dy) {
    super.move(dx, dy);
    c.move(dx, dy);
  }

Dann sollten die Klassen noch eine Methode zur String-Ausgabe enthalten.


  public String toString() {
    return getClass().getName()
        + "[" + paramString() + "]";
  }

  protected String paramString() {
    return "x1="+a.getX()+",y1="+a.getY()
        +",x2="+b.getX()+",y2="+b.getY();
  }

  // wir benutzen einfach die toString() Methode
  // von Line, diese muss hier NICHT neu
  // deklariert werden

  protected String paramString() {
    return super.paramString()
      +",x3="+c.getX()+",y3="+c.getY();
  }

Die Länge der Linie ist der Abstand der beiden Punkte.

Beim Dreieck wird das dann drei mal berechnet.


  public double length() {
    return a.distance(b);
  }

  public double length() {
    return a.distance(b) + b.distance(c)
                         + c.distance(a);
  }

Aufgabe 72 - (2,4)-Baum - Einfügen von Elementen

not yet.

Aufgabe 73 - (2,4)-Baum - Löschen von Elementen

not yet.

Aufgabe 74 - die Sache mit dem Interface

  1. Das Entwerfen des interface ist sicherlich das geringste Problem:

    
      interface SimpleFunction {
        double at(double x);
      }
  2. Schwieriger wird es beim Implementieren durch sinnvolle Funktionen, weil Java dafür mehrere Möglichkeiten bietet. Es ist logisch, dass eine neue Klasse erstellt werden muss. Die "Standard"-Variante ist diese:

    
      class Square implements SimpleFunction {
        public double at(double x) {
          return x * x;
        }
      }

    Instanziiert wird diese Klasse durch

    
      SimpleFunction f1 = new Square();

    Java bietet aber noch eine andere Möglichkeit, die auch in den Java Beispielprogrammen und Tutorials bevorzugt wird. Dabei wird das interface sozusagen "inline" implementiert.

    
      SimpleFunction f2 = new SimpleFunction() {
        public double at(double x) {
          return Math.sqrt(x);
        }
      }; // Semikolon nicht vergessen

    Dieser Aufruf erstellt nebenbei eine neue Klasse. Da man der Klasse keinen Namen geben kann, werden solche Klassen vom Compiler durchnumeriert. Steht dieser Aufruf zum Beispiel in einer Klasse namens ueb15.java, so erstellt der Compiler die Dateien

    ueb15.classdie Hauptklasse
    ueb15$1.classdie inline implementierte Klasse
    ueb15$2.classund noch eine, ...

    Es fehlt noch die dritte Klasse:

    
      SimpleFunction f3 = new SimpleFunction() {
        public double at(double x) {
          return x + x;
        }
      };
  3. Nun die Ausgabe der Wertetabelle

    
      static void werteTafel(SimpleFunction f) {
        for (double x = 1.0;  x < 10.5;  x += 1.0) {
          System.out.println("x = "+x+"   f(x) = "+f(x));
        }
      }
  4. Zum Ausgeben der Tabelle können alle schon geschriebenen Klassen und Deklarationen benutzt werden.

    
      public static void main(String args[]) {
        SimpleFunction f1 = new Square();
        SimpleFunction f2 = new SimpleFunction() { ... };
        SimpleFunction f3 = new SimpleFunction() { ... };
        System.out.println("Quadrat");
        werteTafel(f1);
        System.out.println("Wurzel");
        werteTafel(f2);
        System.out.println("Verdoppeln");
        werteTafel(f3);
      }

    Eine etwas besser formatierte Ausgabe:

    
           x |      x^2 |  sqrt(x) |      x+x
    ---------+----------+----------+---------
         0.0 |      0.0 |      0.0 |      0.0
         1.0 |      1.0 |      1.0 |      2.0
         2.0 |      4.0 | 1.414213 |      4.0
         3.0 |      9.0 | 1.732050 |      6.0
         4.0 |     16.0 |      2.0 |      8.0
         5.0 |     25.0 | 2.236067 |     10.0
         6.0 |     36.0 | 2.449489 |     12.0
         7.0 |     49.0 | 2.645751 |     14.0
         8.0 |     64.0 | 2.828427 |     16.0
         9.0 |     81.0 |      3.0 |     18.0
        10.0 |    100.0 | 3.162277 |     20.0

    wird von meinem Programm erzeugt, dass aber noch die Klasse MethodParameter aus dem Paketverzeichnis benötigt.

Aufgabe 75 - Tutoraufgabe - Schleifen durch Rekursion

not yet.


Erstellt von Markus Durzinsky, aktualisiert 23. Dezember 2003
Für Fragen, Probleme oder Anregungen stehe ich gerne zur Verfügung