Einführung Algorithmen und Datenstrukturen

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

16. Übungsblatt

Aufgabe 76 - arithmetischer binärer Baum

  1. Als eine Vereinfachung der Problematik, sei der Ausdruck in post order gegeben. Aus dem Beispiel wird dann 20 50 5 / - 2 3 * +. Der Vorteil liegt darin, das die Ausführungsreihenfolge (Klammerung) in der Reihenfolge der Operatoren enthalten ist, und dass dieser Ausdruck wesentlich leichter berechnet oder in einen Baum umgewandelt werden kann. Wie man einen inorder Ausdruck in post order umwandelt wird später behandelt.

    Zum Erstellen des Baumes benötigt man einen stack, auf dem die Zahlen (und Knoten) zwischengespeichert werden. In einem Vorverarbeitungsschritt wird der Ausdruck in eine Folge (Iterator oder Enumeration) von Knoten umgewandelt, die jeweils als Inhalt einen token enthalten, und keine (null) Kinder haben.

    Der Algorithmus nimmt sich nun der Reihe nach alle Knoten der Folge. Ist der Inhalt eine Zahl, so wird der Knoten auf den stack gepackt. Ist der token des Knotens ein Operator, dann werden zwei Knoten vom stack genommen und als neue Kinder des Operators gesetzt. Dann wird der Operator auf den stack gelegt. Am Ende sollte der stack genau ein Element enthalten. Dieses ist dann die Wurzel des Baumes.

    
      Algorithm SyntaxtreeFromPostorder
      Input  : L - Liste von Knoten (token als Datum, keine Kinder)
      Output : Wurzel des Syntaxbaumes
    
      S - empty stack
      while L.hasNext do
          K <- L.next
          if K.getData.isOperator then
              Left <- S.pop
              Rigth <- S.pop
              K.setLeft(Left)
              K.setRight(Right)
          S.push(K)
      return S.pop

    Erläuterung am Beispiel:

    L.nextTypAktionStack
    20Zahlpush20
    50Zahlpush20; 50
    5Zahlpush20; 50; 5
    /Operator50 und 5 als neue Kinder von /20; /[50,5]
    -Operator20 und / als neue Kinder von --[20,/[50,5]]
    2Zahlpush-[20,/[50,5]]; 2
    3Zahlpush-[20,/[50,5]]; 2; 3
    *Operator2 und 3 als neue Kinder von *-[20,/[50,5]]; *[2,3]
    +Operator- und * als neue Kinder von ++[-[20,/[50,5]],*[2,3]]
  2. Die Berechnung erfolgt nun rekursiv über die Knoten. Dabei werden erst die beiden Kinder berechnet, und das Ergebnis wird je nach Operation zusammengenommen und zurückgegeben.

    
      Algorithm EvaluateNode
      Input  : N - Knoten
      Output : Ergebnis als Zahl
    
      if N.getData.isOperator then
          Left <- EvaluateNode(N.getLeft)
          Right <- EvaluateNode(N.getRight)
          if N.getData = add then
              return Left + Right
          if N.getData = multiply then
              return Left * Right
          ...
      else
          return N.getData

    Für das Ergebnis des ganzen Baumes müsste dieser Algorithmus auf die Wurzel angewendet werden. Hier das Beispiel:

    
      root + (Operator)
          Left  - (Operator)
              Left  20 (return 20)
              Right / (Operator)
                  Left  50 (return 50)
                  Right 5 (return 5)
                  return (50 / 5)
              return (20 - (50 / 5))
          Right * (Operator)
              Left  2 (return 2)
              Right 3 (return 3)
              return (2 * 3)
          return ((20 - (50 / 5)) + (2 * 3))

Aufgabe 77 - Syntaxbaum implementieren

Ein Applet: ArithmeticApplet

Aufgabe 78 - Geometrieobjekt - Circle

  1. Nun soll also, zusätzlich zu den in Aufgabe 71 definierten Geometrieobjekten, noch eine Klasse für Kreise erstellt werden. Um ein wenig Schreibarbeit zu sparen, kann man sich überlegen, ob es möglich ist, eine vorhandene Klasse zu erweitern. Da ein Kreis nur aus einem Mittelpunkt und einem Radius besteht, bietet sich hier die Klasse Point an:

    
    public class Circle extends Point {
    
      protected double radius;
    
      public Circle(int x, int y, double r) {
        super(x, y);
        setRadius(r);
      }
    
      ...
    
    }

    Die Methoden zum Verschieben und Positionsermittlung werden dann einfach von Point geerbt.

    
      public void setRadius(double r) {
        radius = Math.abs(r);
      }
    
      public double getRadius() {
        return radius;
      }

    Die Berechnung des Abstands zu einem anderen Punkt stimmt jetzt natürlich nicht mehr. Von diesem Abstand muss nun der Radius abgezogen werden (der Abstand darf dann aber auch nicht negativ sein).

    
      public double distance(int x, int y) {
        double d = super.distance(x, y);
        if (d < radius) {
          return 0;
        }
        return d - radius;
      }

    Interessant ist sicher auch der Durchmesser des Kreises:

    
      public double getPerimeter() {
        return 2.0 * Math.PI * radius;
      }

    Es fehlt noch eine Anpassung der Umwandlung in einen String.

    
      protected String paramString() {
        return ",radius="+radius;
      }
  2. Der Test, ob sich zwei Kreise schneiden (intersect), oder ob ein Kreis ein anderes Objekt schneidet, kann auf den Abstand des Mittelpunktes zu diesem Objekt zurückgeführt werden. Der Fall, dass dieses Objekt vollständig im Kreis enthalten ist (dann schneiden sie sich ja auch nicht) wird grosszügig vernachlässigt.

    
      public boolean intersects(Circle c) {
        return c.distance(x, y) <= radius;
      }

    Äquivalent wäre gewesen super.distance((Point) c) <= radius + c.radius. Dies Berechnet den Abstand der Mittelpunkte (mit Hilfe der distance-Methode von Point), welcher kleiner oder gleich der Summe der Radien sein muss. Der oben verwendete Ausdruck funktioniert aber mit jedem Geometrieobjekt, dass eine distance-Methode besitzt.

  3. Das vollständige Überlagern eines anderen Kreises ist der oben nicht beachtete Spezialfall. Dabei ist der Abstand der Punkte kleiner als die Differenz der Radien.

    
      public boolean contains(Circle c) {
        return super.distance((Point) c) + c.radius <= radius;
      }

Aufgabe 79 - Rot-Schwarz-Baum kontra AVL-Baum

not yet.

Aufgabe 80 - Tutoraufgabe - Dreiecksgeschichten

    • Ein Dreieck ist genau dann gleichseitig (engl. equilateral), wenn zwei verschiedene Paare von Eckpunkten den gleichen Abstand von einander haben, d.h. wenn zwei verschiedene Linien gleich lang sind. Man braucht also nur alle möglichen Kombinationen von Linien zu testen.

      
        public boolean isEquilateral() {
          if (Math.abs(a.distance(b) - b.distance(c)) < 0.01) {
            return true;
          }
          if (Math.abs(b.distance(c) - c.distance(a)) < 0.01) {
            return true;
          }
          if (Math.abs(c.distance(a) - a.distance(b)) < 0.01) {
            return true;
          }
          return false;
        }
    • Das Testen, ob drei Linien ein Dreieck aufspannen ist etwas komplizierter, weil es mehr Fälle zum Unterscheiden gibt. Es muss je ein Punkt einer Linie mit genau einem Punkt genau einer anderen Linie übereinstimmen. Anders ausgedrückt: jede Linie muss ihren Anfangspunkt in der Ecke der zweiten Linie und ihren Endpunkt in der Ecke der dritten Linie haben. Die Methode isVertex innerhalb der Klasse Line sieht so aus:

      
        public boolean isVertex(int x, int y) {
          return a.equals(x, y) || b.equals(x, y);
        }

      Diese Methode testet, ob der übergebene Punkt einer der beiden Eckpunkte ist. Dies muss nun für beide Punkte einer Linie des Dreiecks der Fall sein:

      
        protected static boolean checkLine(Line a, Line b, Line c) {
          if (b.isVertex(a.getX1(), a.getY1()) && c.isVertex(a.getX2(), a.getY2())) {
            return true;
          }
          if (b.isVertex(a.getX2(), a.getY2()) && c.isVertex(a.getX1(), a.getY1())) {
            return true;
          }
          return false;
        }

      Wenn das nun für alle drei Linien getestet wird, dann haben wir ein Dreieck.

      
        public static boolean isTriangle(Line a, Line b, Line c) {
          return checkLine(a, b, c) && checkLine(b, a, c) && checkLine(c, a, b);
        }
  1. Ein Testrahmen ist schnell geschrieben:

    
      public static void main(String args[]) {
        Triangle t1 = new Triangle(50, 0, 30, 100, 70, 100);
        System.out.println("Drecieck 1 = "+t1);
        System.out.println("gleichseitig ? "+t1.isEquilateral());
        System.out.println("Umfang = "+t1.length());
        // dies ist offensichtlich ein Dreieck
        System.out.println("Dreieck ? "+Triangle.isTriangle(t1.getEdge(0),
            t1.getEdge(1), t1.getEdge(2)));
        Line l1 = new Line(50, 0, 30, 90);
        System.out.println("Linie geaendert, Dreieck ? "+Triangle.isTriangle(
            l1, t1.getEdge(1), t1.getEdge(2)));
        Triangle t2 = new Triangle(50, 0, 30, 100, 71, 100);
        System.out.println("Drecieck 2 = "+t2);
        System.out.println("gleichseitig ? "+t2.isEquilateral());
        System.out.println("Umfang = "+t2.length());
      }

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