Einführung Algorithmen und Datenstrukturen

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

11. Übungsblatt

Aufgabe 51 - reverse Engeneering

  1. Was macht wohl diese Methode?

    
      static int was(int m, int n) {
        for (int i = 1;  i <= n;  i++) {
          if (m * i % n == 0) {
            return m * i;
          }
        }
        return 0;
      }

    Wenn einem der Algorithmus nicht direkt etwas sagt, wird man eventuell erst ein mal ein paar Werte probieren. Also etwas in der Art:

    
      for (int m = 1;  m < 10;  m++) {
        for (int n = 1;  n < 10;  n++) {
          System.out.print(was(m, n) + "\t");
        }
        System.out.println();
      }

    Man erkennt vieleicht, dass die Werte der m-ten Zeile durch m teilbar sind. Da die Ausgabetabelle symmetrisch ist (a[i,j] = a[j,i]), gilt dies auch für jede Spalte. Dieses Verhalten ist nicht weiter verwunderlich, da ja immer ein Vielfaches (i-faches) von m zurückgeliefert wird. Dieser Wert ist ebenfalls durch n teilbar, da m * i % n == 0 gilt. Weil nun mit dem kleinsten i begonnen wird, ist das Ergebnis der Methode das kleinste gemeinsame Vielfache von m und n.

  2. Um den Algorithmus zu kommentieren könnte man so vorgehen:

    
      static int kgV(int n, int m) {
        // Test für alle n
        for (int i = 1;  i < n;  i++) {
          // Berechne Produkt
          int vielfach = m * i;
          // ist das Produkt durch n teilbar ?
          if (vielfach % n == 0) {
            return vielfach;
          }
        }
        // m und n sind teilerfremd
        return m * n;
      }

    Da die Methode was() spätestens bei i = n terminiert (da offensichtlich m * n % n = 0), wird die Zeile return 0; nie erreicht. Die Methode kgV() spart sich den Durchlauf für i = n (und den Modulo-Test) und gibt dann m * n zurück. (Im Allgemeinen sollte man sich Gedanken um das allgemeine Design des Algorithmus machen, wenn es nötig ist, jede Zeile zu kommentieren.)

    Diese Variante zur Berechnung des kgV ist ziemlich aufwendig. Die innere Schleife läuft linear bis n, wenn die Zahlen teilerfremd sind (also O(n)). Es geht auch schneller. Wie man leicht sieht, gilt ja kgV(m, n) = m * n / ggT(m, n). Die Berechnung des ggT() nach Euklid (Aufgabe 10c)

    
      public static int ggT(int a, int b) {
        int r;
        do {
          r = a % b;    a = b;    b = r;
        } while (r != 0);
        return a;
      }

    ist da etwas effektiver. Der worst case tritt ein, wenn a und b zwei aufeinander folgende Fibonacci-Zahlen sind (thankz to Dr. Volker John), da der Rest der Division dann die nächst kleinere Fibonacci-Zahl ist. Mehr zu diesen Zahlen in Aufgabe 19. Der Euklidische Algorithmus durchläuft dann diese Zahlen rückwärts und benötigt damit für ggT(fib(n), fib(n-1)) genau n Schritte. Da das Wachstum der Fibonacci-Zahlen exponentiell ist (irgendwas mit O(xn) (wobei x der goldene Schnitt ist), ist der Aufwand des ggT logarithmisch O(log n).

Aufgabe 52 - Traversierung an einem binären Baum

Erst einmal heisst mein Suchbaum auch BinarySearchTree. Muss man eigentlich alles "eindeutschen"? Was ist denn eine Präorder. Oder soll das eine Preanordnung sein.

  1. Das Einfügen ist einfach, da die Methode insertElement() schon in Aufgabe 50 programmiert wurde. Es ist nur zu beachten, dass die einzufügenden Elemente auch Objekte sein müssen, die Comparable implementieren. Gut das es schon eine geeignete Klasse gibt: java.lang.Integer

    
      BinarySearchTree tree = new BinarySearchTree();
      int[] elements = {4, 2, 6, 8, 9, 7, 5, 3, 1};
      for (int i = 0;  i < elements.length;  i++) {
        tree.insertElement(new Integer(elements[i]));
      }
  2. Preorder, Inorder, Postorder und Eulertour als Kombination der ersten drei.

  3. Da die drei Varianten alles Spezialfälle der EulerTour sind, ist es am sinnvollsten diese zu implementieren und entsprechend auszulegen. Dazu erstellt man ein Template (in Java eine abstrakte Klasse).

    
      public abstract class EulerTour {
        private BinaryTreeNode root;
    
        public EulerTour(BinarySearchTree tree) {
          this(tree.getRoot());
        }
    
        public EulerTour(BinaryTreeNode node) {
          root = node;
        }
    
        public void visitLeft(BinaryTreeNode node) {}
        public void visitBelow(BinaryTreeNode node) {}
        public void visitRight(BinaryTreeNode node) {}
        ...
      }

    Für die drei Traversierungsarten müssen nur die entsprechenden Methoden überschrieben werden (das wird weiter unten beschrieben). Initialisiert wird die Eigenschaft root entweder mit der Wurzel eines Baumes oder einem explizit angegebenen Knoten. Es fehlt noch die Implementierung der eigentlichen Tour.

    
        private void eulerTour(BinaryTreeNode node) {
          if (node != null) {
            visitLeft(node);
            eulerTour(node.getLeft());
            visitBelow(node);
            eulerTour(node.getRight());
            visitRight(node);
          }
        }

    Gestartet wird das Ganze durch diese Methode:

    
        public void startTour() {
          eulerTour(root);
        }

    Dadurch wurde zwar die Klasse BinarySearchTree nicht um "traversierende" Methoden erweitert. Dazu hätte man noch ein Iterator-Interface schreiben müssen und drei Klassen, die dieses mit den Traversierungen implementieren. Was dann erheblich mehr Aufwand gewesen wäre.

  4. Aber wie benutzt man solch eine abstrakte Klasse am einfachsten? Die Vorgehensweise ist schon aus der Verwendung von Adaptern in der Java API bekannt (z.B. java.awt.event.MouseAdapter), jedenfalls den Programmierern, die sich mal mit event handling befasst haben.

    Da eine abstrakte Klasse nicht direkt instantiiert werden kann, muss man eine neue Klasse schreiben, die von dieser Klasse erbt. Dann müssen aber nur die Methoden überschrieben werden, die man auch benötigt (Vorteil gegenüber der Verwendung eines Interface). In Java besteht eine sehr schöne Möglichkeit dies zu tun:

    
      // ueberschreibe visitBelow() fuer inorder
      EulerTour tour = new EulerTour(tree) {
        public void visitBelow(BinaryTreeNode node) {
          System.out.print(" "+node.getData());
        }
      };

    Obwohl EulerTour eine abstrakte Klasse ist, kann man mit new EuterTour() ein neues Objekt dieser Klasse erstellen. Genauer gesagt wird eine neue Klasse definiert, die von EulerTour erbt (durch dir Klammern {}). Da diese Klasse keinen Namen hat (weil man ihr keinen gegeben hat, und ihr auch keinen geben kann), numeriert Java diese Klassen einfach durch. Das Resultat ist eine Datei namens ueb11$1.class, weil meine Hauptklasse ueb11 heisst. Die Tour braucht dann nur noch gestartet werden.

    
      System.out.print("inorder:");
      tour.startTour();
      System.out.println();

    Die Ausgabe sollte die korrekte Funktionsweise bestätigen:

    
      inorder: 1 2 3 4 5 6 7 8 9

    Mit den anderen beiden Traversierungsarten funktioniert dass genauso.

    
      // ueberschreibe visitLeft() fuer preorder
      tour.startTour();
      System.out.println();
      tour = new EulerTour(tree) {
        public void visitLeft(BinaryTreeNode node) {
          System.out.print(" "+node.getData());
        }
      };
    
      System.out.print("preorder:");
      tour.startTour();
      System.out.println();
    
      // ueberschreibe visitRight() fuer postorder
      tour = new EulerTour(tree) {
        public void visitRight(BinaryTreeNode node) {
          System.out.print(" "+node.getData());
        }
      };
    
      System.out.print("postorder:");
      tour.startTour();
      System.out.println();

    Hier die Ausgabe:

    
      preorder: 4 2 1 3 6 5 8 7 9
      postorder: 1 3 2 5 7 9 8 6 4
    binary tree

    Der Baum sieht übrigens so aus. Dieser entsteht beim Einfügen nach Sortierungskriterium. Ein kleines Applet zum selbst probieren gibt es auf dieser Seite.

Aufgabe 53 - AVL Bäume

  1. Die Anzahl der Knoten in einem Teilbaum ist die Anzahl im linken Unterbaum, die Anzahl im rechten Unterbaum und 1 aufaddiert. Ein leerer Baum hat genau null Knoten.

    
      public int countNodes() {
        return countNodes(root);
      }
    
      protected int countNodes(BinaryTreeNode node) {
        return node == null
            ? 0
            : countNodes(node.getLeft()) + countNodes(node.getRight()) + 1;
      }
  2. Die Höhe des Baumes ist sicherlich gleich der Höhe der Wurzel.

    
      public int getHeight() {
        return getHeight(root);
      }

    Die Höhe eines "null"-Knotens ist 0 (kein Knoten hat auch keine Höhe). An sonsten muss die Höhe der beiden Kinder rekursiv ermittelt werden. Davon benötigt man dann das Maximum. Da der Knoten selbst auch noch Platz der Höhe 1 verbraucht, muss man diesen Wert noch inkrementieren.

    
      public int getHeight(BinaryTreeNode node) {
        if (node == null) {
          return 0;
        }
        return 1 + Math.max(getHeight(node.getLeft()), getHeight(node.getRight()));
      }
  3. Einen höhen-balancierten Baum bezeichnet man auch als AVL-Baum. Ein Teilbaum entspricht dem ALV-Kreiterium, wenn sich die Höhe des linken und des rechten Unterbaumes um höchstens 1 unterscheidet. Der ganze Baum ist AVL, wenn jeder Teilbaum bzw. Knoten AVL ist. Dieses Kriterium ist wesentlich schwächer, aber auch leichter einzuhalten, als das des vollständig ausgeglichenen Baumes (bei dem die Anzahl der Knoten im rechten bzw. linken Unterbaum sich nur um 1 unterscheiden darf). Durch diese Abschwächung erhöht sich die Gesamthöhe des Baumes aber höchstens um 1. Der Aufwand zum Durchsuchen ist damit immer noch logarithmisch.

    
      public boolean isAVL() {
        return isAVL(root);
      }
    
      protected boolean isAVL(BinaryTreeNode node) {
        if (node == null) {
          return true;
        }
        if (abs(getHeight(node.getLeft()) - getHeight(node.getRight())) > 1) {
          return false;
        }
        return isAVL(node.getLeft()) && isAVL(node.getRight());
      }

Aufgabe 54 - noch mal Traversierung

  1. Da die Klasse EulerTour schon in Aufgabe 52 definiert wurde, braucht man sie nur noch zu überschreiben. Da die Superklasse EulerTour keinen leeren Konstruktor besitzt, muss man auch in der SumTour einen definieren.

    
      public class SumTour extends EulerTour {
        private int sum = 0;
    
        public SumTour(BinarySearchTree tree) {
          super(tree);
        }
    
        public void visitLeft(BinaryTreeNode node) {
          Integer i = (Integer)node.getData();
          sum += i.intValue();
        }
    
        public int getSum() {
          return sum;
        }
    
      }
  2. Zum Testen wird ebenfalls der in Aufgabe 52 deklarierte Baum verwendet.

    
      ueb11SumTour stour = new ueb11SumTour(tree);
      stour.startTour();
      System.out.println("Summe: "+stour.getSum());

    Und das Ergebnis 45 erscheint auf dem Bildschirm.

Aufgabe 55 - Tutoraufgabe - Baum des Pythagoras

Ein kleines Applet zu diesem Bild, und ein paar Erläuterungen, findet man auf dieser Seite.

Pythagorasbaum

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