Einführung Algorithmen und Datenstrukturen

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

06. Übungsblatt

Aufgabe 26 - O-Notation

  1. Um die Komplexität zu ermitteln, benötigt man die Anzahl der am häufigsten ausgeführten bzw. der aufwendigsten Operation. In diesem Fall ist dies eine Anweisung innerhalb der for-Schleifen.

    • Das erste Beispiel besteht aus zwei hintereinander ausgeführten Schleifen:

      
        for (i = 1;  i < n;  i++);
        for (i = n;  i > 0;  i--);

      Es ist leicht zu sehen, dass die erste Schleife n-1 mal und die zweite Schleife n mal ausgeführt wird. Demnach ist die Gesamtanzahl 2*n-1 und der Algorithmus ist in O(n).

    • Im zweiten Beispiel wird die Laufvariable i immer mit 2 multipliziert.

      
        for (i = 1;  i < n;  i*=2);

      Die Schleife bricht nach x-1 Durchläufen ab, wenn ix > n, also nach log2n Operationen. Der Aufwand entspricht O(log n).

    • Das dritte Beispiel besteht aus zwei verschachtelten Schleifen, wobei die Komplexität der inneren Schleife nicht von der äusseren Schleife abhängt (innere Grenzen unabhängig von i):

      
        for (i = 1;  i < n; i++)
          for (j = 1;  j <  n*n;  j++);

      Die Anweisung wird (n-1)*(n*n-1) mal ausgeführt. Dies ergibt n3-n2-n+1 und eine Komplexität von O(n3).

  2. Als erstes erzeugt man einen Algorithmus aus der angegebenen Abbildung, um sich die Funktionsweise zu veranschaulichen:

    Potenzierungsformel
    
      // Variante 1:
      double power(double x, int n) {
        if (n <= 0) return 1;
        if (n == 1) return x;
        if (n % 2 == 0) return power(x, n/2) * power(x, n/2);
        return power(x, n/2) * power(x, n/2) * x;
      }
    
      // Variante 2:
      double power(double x, int n) {
        if (n <= 0) return 1;
        if (n == 1) return x;
        if (n % 2 == 0) return power(x*x, n/2);
        return power(x*x, n/2) * x;
      }

    Hinweis: der Test auf n ≤ 0 dient nur dem Abfangen falscher Benutzereingaben. Man könnte auch schreiben

    
        if (n < 0) {
          return power(1/x, -n);
        }
        if (n == 0) {
          return 1;
        }

    Die beiden Varianten unterscheiden sich im Wesentlichen dadurch, dass sich die erste zwei mal rekursiv aufruft. Die Halbierung des Exponenten bei jeder Rekursionsebene wird durch den doppelten Aufruf wieder aufgehoben. Der Aufwand ist also O(n). Genau genommen ist er sogar noch grösser als beim Algorithmus aus Aufgabe 16, weil die Anzahl der Aufrufe auf die nächste Zweierpotenz (bzw. 2x-1) aufgerundet wird. Bei der zweiten Variante erfolgt nur ein rekursiver Aufruf (höchstens aber log2n mal wie bei Variante 1). Die Komplexität entspricht demnach O(log n). Durch einfaches zwischenspeichern des Ergebnisses lassen sich die beiden identischen Aufrufe aus Variante 1 vermeiden:

    
      double power(double x, int n) {
        if (n <= 0) return 1;
        if (n == 1) return x;
        double p = power(x, n/2);
        if (n % 2 == 0) return p * p;
        return p * p * x;
      }

    Dadurch wird die Komplexität von Variante 1 ebenfalls zu O(log n).

Aufgabe 27 - Hornerschema

  1. Das Horner-Schema basiert darauf, die Variable x soweit wie möglich aus einem Polynom auszuklammern. Man erhält die in der Aufgabenstellung angegebene Formel, die sich leicht in Java implementieren lässt:

    
      public static double hornerPolynomial(double[] a, double x) {
        double f = a[a.length-1];
        for (int i = a.length-2;  i >= 0;  i--)
          f = f * x + a[i];
        return f;
      }

    Wenn an der erste (und höchste) Parameter ist, ist zu beachten, dass dies a[a.length-1] entspricht, weil die Länge des Feldes gleich n+1 ist.

  2. Die Methode besteht aus einer einzelnen Schleife, die n mal durchlaufen wird. Die Komplexität ist also O(n).

Aufgabe 28 - Ratinale Zahlen

  1. Eine rationale Zahl besteht aus einem Bruch zweier ganzer Zahlen. Der Nenner darf nicht 0 sein und in unserem Fall wird das Vorzeichen im Zähler gespeichert. Zum Erstellen eines neuen Objektes der Klasse Rational ruft man den Konstruktor mit dem entsprechenden Zähler und Nenner auf. Ist der Nenner 0, wird eine InvalidDenominatorException ausgeworfen. Die Zeile rat3 = new Rational(5,0); wird sicher zu diesem Fehler führen. Was aber nicht weiter schlimm ist, da er ja in der nächsten Zeile abgefangen wird mittels catch (InvalidDenominatorException e).

    Nun werden die ersten beiden Brüche addiert. Da sich der angegebene Algorithmus nicht die Mühe mach den kleinsten Hauptnenner auszurechnen wird einfach das Produkt der Nenner als neuer Nenner verwendet. Die Zähler werden entsprechend erweitert und addiert. Ein neues Rational-Objekt wird als Ergebnis zurückgegeben. Diese Verfahrensweise, bei der ein einmal erstelltes Objekt nicht wieder verändert werden darf, ist häufiger anzutreffen, zum Beispiel bei java.awt.Color oder auch java.lang.String. Dies stellt sicher, dass es nicht zu unerwarteten Ergebnissen kommt, weil ein Objekt zwischenzeitlich verändert wurde.

    Durch System.out.println(rat1); wird automatisch die Methode rat1.toString() aufgerufen. Diese Methode dient dazu den Bruch in geeignetter Weise in einen String umzuwandeln. Also in Zähler+"/"+Nenner. Ist der Nenner gleich eins, wird er weggelassen.

  2. Beim Kürzen des Bruches werden sowohl Zähler als auch Nenner durch deren grössten gemeinsamen Teiler geteilt. Also z/n := z/ggT(z,n) / n/ggT(z,n). Zu beachten sind folgende Dinge:

    • Ist der Zähler gleich 0, so ist der ggT nicht definiert. Um dennoch ein eindeutiges Ergebnis zu erhalten sollte das Ergebnis 0 / 1 sein.

    • Es hängt von der Implementierung der ggT-Methode ab, wie diese auf negative Zahlen reagiert. Vorsichtshalber sollte mit den absoluten Beträgen gerechnet werden.

    • Um die absolute Gleichheit (von Zähler und Nenner) von zwei Brüchen nach dem Kürzen sicherzustellen habe ich die Konvention verwendet, das Vorzeichen nur im Zähler zu führen, wie dies auch schon im Konstruktor geschieht.

    Daraus folgt diese Implementierung:

    
      public Rational normalize() {
        if (num == 0) {
          return new Rational(0, 1);
        }
        int x = ggT(Math.abs(num), Math.abs(denom));
        if (denom < 0) {
          x = -x;
        }
        return x == 1 ? this : new Rational(num / x, denom / x);
      }
    
      // ggT aus Aufgabe 10
      private static int ggT(int a, int b) {
        int r;
        do {
          r = a % b;  a = b;  b = r;
        } while (r != 0);
        return a;
      }

    Die Division zweier Brüche ist einfacher, da nur mit dem Reziproken des zweiten Bruches multipliziert werden muss:

    
      public Rational divide(Rational r) {
        return new Rational(num*r.denom, denom*r.num);
      }

    Hinweis:

    • Wenn der Zähler von r gleich 0 ist, wirft der Konstruktor eine InvalidDenominatorException aus. Die divide-Methode braucht dies nicht zu kümmern, da nicht abgefangene Exceptions automatisch an die aufrufende Methode weitergeleitet werden.

    • Warum kann überhaupt "this" auf r.num zugreifen, obwohl dieses als private deklariert wurde? Dies liegt daran, dass es sich zwar um zwei verschiedene Objekt handelt, die aber der selben Klasse angehören. Das Prinzip der Datenkapselung wird nicht verletzt, weil nur der Programmierer, der die Klasse Rational geschrieben hat, den Zugriff verwenden darf. Alle anderen Objekte, die nicht vom Typ Rational sind haben keinen Zugriff. Auch nicht solche Klassen, die von Rational erben. (d.h. private heisst "Klassen-privat" und nicht "Objekt-privat")

    Eine Erweiterung der Klasse Rational um Methoden zum Multiplizieren, Subtrahieren, Potenzieren und Vergleichen, sowie ein Applet zum Testen der Methoden ist hier zu finden.

  3. Zurück zur Aufgabenstellung. Bleibt noch die Anpassung von RationalTest:

    
      public static void main(String args[]) {
        System.out.println("Aufgabe 28: Rationale Zahlen");
        Rational r1 = new Rational(4,3), r2 = new Rational(15,6);
        System.out.println(r1+" + "+r2+" = "+r1.add(r2)+" = "+r1.add(r2).normalize());
        System.out.println(r1+" / "+r2+" = "+r1.divide(r2)+" = "+r1.divide(r2).normalize());
        r1 = new Rational(0, 3);
        System.out.println(r1+" = "+r1.normalize());
      }

    Dies sollte zur Ausgabe

    
      Aufgabe 28: Rationale Zahlen
      4/3 + 15/6 = 69/18 = 23/6
      4/3 / 15/6 = 24/45 = 8/15
      0/3 = 0

    führen.

Aufgabe 29 - OOP / Stack

  1. Der Konstruktor einer Klasse wird jedes mal aufgerufen, wenn ein neues Objekt dieser Klasse erzeugt wird. Als erstes belegt Java den benötigten Speicherplatz, dann wird der eigentliche Programmcode des Konstruktors ausgeführt. Deshalb hat der Konstruktor im Wesentlichen die Aufgabe die Eigenschaften des Objektes zu initialisieren. Eine Klasse kann mehrere Konstruktoren haben (eine Art von Überladung), die sich anhand der übergebenen Parameter (Signatur) unterscheiden.

    Jeder Konstruktor muss als erste Anweisung genau einen Konstruktor der Klasse aufrufen, von der die Klasse erbt oder einen anderen eigenen Konstruktor. Dies erfolgt durch den Aufruf super(...); bzw. this(...);. Fehlt diese Zeile wird automatisch super(); ausgeführt (Hinweis: enthält super keinen parameterlosen Konstruktor, weiss der Compiler nicht welcher Konstruktor aufgerufen werden soll und ein Fehler wird ausgegeben).

    Da die Angabe der übergeordnetten Klasse (mit Konstruktor, Methoden und Eigenschaften) durch super eindeutig ist, kann eine Klasse nur von genau einer anderen Klasse erben (mittels extends). Um dennoch einige Vorteile der Vielfachvererbung zu nutzen, wurden in Java Interfaces eingeführt. Ein Interface ist so etwas ähnliches wie eine Klasse, mit dem Unterscheid, dass in einem Interface keine Methoden implementiert sind und keine Eigenschaften (Variablen) vorhanden sind. Es besteht demnach nur aus abstrakten Methoden und Konstanten.

    Wenn eine Klasse von einem Interface erbt (durch implements), müssen alle im Interface definierten Methoden implementiert werden (oder die Klasse wird als abstract deklariert und kann nicht instanziiert werden). Eine Klasse kann aber beliebig viele Interfaces implementieren. Es ist auch möglich, dass ein Interface von einem anderen Interface erbt (durch extends). Ein Interface kann sogar von mehreren anderen Interfaces erben. Der eigentliche Nutzen der Interfaces liegt darin, dass eine Klasse, die ein Interface implementiert, zu diesem Interface gecastet werden kann:

    
      class aClass implements aInterface {
        ...
      }

    zum Beispiel durch:

    
      aClass aObject = new aClass();
      aInterface i = (aInterface) aObject;

    Die Klasse ArrayStack macht sich dies zunutze. Es gibt zum Beispiel zwei Konstruktoren: Dem einen wird die Grösse des Feldes übergeben, dem anderen nicht. Letzterer ruft einfach this(CAPACITY); auf, wobei CAPACITY die Standardgrösse ist. Obwohl der Konstruktor ArrayStack(int) keinen Konstruktoraufruf enthält, wird dennoch super(); aufgerufen (dies geschieht automatisch durch den Compiler, wenn kein Konstruktor angegeben wird).

    Zum anderen implementiert der ArrayStack das Interface Stack. Ein anderes Programm könnte also mit einem Objekt vom Typ Stack arbeiten, ohne sich darum kümmern zu müssen, um welche implementierende Klasse es sich handelt:

    
      void doSomething(Stack stack) {
        ...
      }

    Diese Methode kann mit jedem Objekt, das Stack implementiert, als Parameter aufgerufen werden.

    Das schon erwähnte Umwandeln eines Objektes in eine andere Klasse nennt man Casting. Programmiert wird es durch die Angabe des neuen Types in Klammern vor dem Objekt: (aClass) aObject. Ein Objekt kann nur in ein Objekt einer anderen Klasse umgewandelt werden, wenn es auch von der neuen Klasse abstammt bzw. erbt. Sei zum Beispiel folgendes implementiert:

    
      class Class1 {
        ...
      }
      class Class2 extends Class1 {
        ...
      }

    Nun ist dies möglich:

    
      Class2 object2 = new Class2();
      Class1 object1 = (Class1) object2;

    Auch ein "zurückcasten" ist möglich, da object1 ja in Wirklichkeit vom Typ Class2 ist:

    
      (Class2) object1;

    Folgender Code funktioniert aber nicht:

    
      object1 = new Class1();
      (Class2) object1;

    Derartige grobe Verstösse werden zur Laufzeit mit einer ClassCastException bestraft! Dafür gibt es in Java aber auch die Möglichkeit zu testen ob eine Objekt eine Instanz einer bestimmten Klasse ist: der instanceof-Operator gibt einen entsprächenden Booleanwert zurück.

    
      Class2 object2 = new Class2();
      Class1 object1 = (Class1) object2;
      object1 instanceof Class2         // ergibt true
      object2 instanceof Class1         // ergibt true, weil Class2 von Class1 erbt
      (new Class1()) instanceof Class2  // ergibt false

    Grundsätzlich ist es auch möglich Primitivtypen (byte, int, short, long, float, double, char) mittels Casting ineinander umzuwandeln:

    
      double d = 1.0;
      int i = (int) d;
      float f = (float) i;

    Wenn bei der Umwandlung keine Daten verloren gehen, muss das Casting nicht explizit angegeben werden (d.h. der Compiler castet implizit):

    
      int i = d;        // das geht nicht
      float f = i;      // aber das geht

    Bei solchen Fehlern meldet der Compiler einen möglichen Verlust der Genauigkeit. Übrigens sind Zahlen mit Komma (z.B. 1.354) standardmässig double und Zahlen ohne Komma (z.B. 123) immer int. Man kann den Typ aber durch Anhängen eines Buchstaben angeben:

    
      long l = 1234567890L;
      float f = 1.0F;
      f = 1.0;          // dies ergibt einen Fehler weil 1.0 = 1.0D (double)
  2. Nun zum Testen der Klasse ArrayStack (Hinweis: ArrayStack implementiert Stack? welchen Stack. Dieses Interface gibt es nicht in der Java-API. Ebenfalls StackFullException und StackEmptyException sucht man vergebens). Die nötigen Klassen sind auf dieser Seite verfügbar.

    Wie man ein Feld erstellt wurde schon öfter behandelt:

    
      int[] x = new int[20];
      for (int i = 0;  i < x.length;  i++) {
        x[i] = (int) (100 * Math.random());
      }

    Diese Werte sollen in einem ArrayStack abgelegt werden. Da dieser nur Objekte akzeptiert und keine Primitivtypen, muss x[i] in ein Objekt umgewandelt werden. Es folgt das Hinzufügen aller Elemente zum Stack:

    
      ArrayStack stack = new ArrayStack(20);
      for (int i = 0;  i < x.length;  i++) {
        stack.push(new Integer(x[i]));
      }

    Nun wird der Stack wieder ausgelesen. Die pop-Methode liefert ein Objekt vom Typ Object zurück. Dies muss in ein Integer-Objekt gecastet. Mit der Methode intValue() bekommt man dann den ursprünglichen Wert:

    
      while (!stack.isEmpty()) {
        x[i] = ((Integer) stack.pop()).intValue();
      }

    Die Elemente des Feldes sollten nun in umgekehrter Reihenfolge gespeichert sein.

Aufgabe 30 - arithmetischen Ausdruck überprüfen

Wie testet man einen arithmetischen Term, ob die Anzahl der Klammern stimmt? Zum einen kann eine Klammer nur geschlossen werden, wenn vorher eine geöffnet wurde. Zum anderen muss es genau so viele schliessende Klammern geben, wie man vorher auch geöffnet hat. Zur Lösung des Problems mit Hilfe des ArrayStacks:
Als erstes muss der Stack erstellt werden. Wenn die Grösse des Stacks, der Länge des Strings entspricht (gleich der maximalen Anzahl von Klammern) wird eine StackFullException vermieden. Dann wird der String nach Klammern durchsucht. Bei '(' fügen wir dem Stack ein Objekt hinzu, bei ')' wird eines entfernt. Die Art der Objekte ist eigentlich egal. Es interessiert ja nur die Grösse des Stacks, und das diese nicht negativ wird. Gibt es eine schliessende Klammer zu viel, tritt eine StackEmptyException auf, welche abgefangen werden sollte. Am Ende stimmt die Anzahl der Klammern, wenn die Grösse des Stacks gleich 0 ist.


  public static boolean testBrackets(String s) {
    ArrayStack stack = new ArrayStack(s.length());
    try {
      for (int i = 0;  i < s.length();  i++)
        if (s.charAt(i) == '(') stack.push(new Object());
        else if (s.charAt(i) == ')') stack.pop();
    } catch (StackEmptyException e) {
      return false;
    }
    return stack.getSize() == 0;
  }

Man könnte auch einfach den Wert von stack.capacity speichern, dann könnte man auf den Stack verzichten (aber dies soll ja eine Übung für den ArrayStack sein).

Der Term muss nur noch in das Programm eingegeben werden. Dies geschieht durch eine der folgenden Varianten:


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