Einführung Algorithmen und Datenstrukturen

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

07. Übungsblatt

Aufgabe 31 - Palindrome

  1. Es gilt zu testen, ob ein angegebener String, nennen wir ihn s, ein Palindrom ist. Trivialerweise darf die reverse()-Methode (dir gar nicht in String definiert ist) nicht benutzt werden. Dieser Hinweis bezieht sich meiner Meinung nach auf die Methode in StringBuffer. Damit ist s ein Palindrom, genau dann wenn gilt:

    
      s.equals((new StringBuffer(s)).reverse().toString())

    Dies sei nur am Rande erwähnt. Der "manuelle" Test ist nicht wesentlich schwieriger. Es muss gelten

    
      s.charAt(i) == s.charAt(s.length()-1-i)    für alle i

    Hinweis: Die Länge der Zeichenkette ist s.length(). Da aber bei Null begonnen wird zu zählen, ist s.length()-1 das letzte Zeichen. Um nicht doppelt zu testen läuft i nur bis s.length()/2. Wenn die Länge ungerade ist, muss das mittlere Zeichen ebenfalls nicht getestet werden. Die Grenze für i ist demnach s.length()/2-1 oder besser ausgedrückt i < s.length()/2.

    
      public static boolean palindromic(String s) {
        for (int i = 0;  i < s.length() / 2;  i++) {
          if (s.charAt(i) != s.charAt(s.length()-1-i)) {
            return false;
          }
        }
        return true;
      }

    Ist ein einzelner Test negativ, kann der gesamte Ausdruck kein Palindrom sein. Was passiert eigentlich bei einer leeren Zeichenkette? Dann ist bei i = 0 der Ausdruck i < s.length() gleich false. Die Schleife wird nicht ein einziges Mal durchlaufen und die Methode liefert true zurück.

  2. Im zweiten Teil der Aufgabe wird die oben angegebene Methode so erweitert, dass Satz- und Sonderzeiten ignoriert, d.h. vor dem Test entfernt werden. Dazu wird ein neuer String erstellt, in den alle Zeichen des Originalstrings hineinkopiert werden, bis auf die Satzzeichen:

    
      s = s.toLowerCase();
      String h = "";
      for (int i = 0;  i < s.length();  i++) {
        char c = s.charAt(i);
        if (c >= 'a' && c <= 'z') h += c;
      }

    Die erste Zeile wandelt alle grossen in kleine Buchstaben um. Es fehlt noch der eigentliche Test, der aber aus Aufgabenteil a benutzt werden kann.

    
      return palindromic(h);

Aufgabe 32 - H-Palindrome

Die theoretische Vorgehensweise zum Lösen dieses Problems wurde schon im Hinweis der Aufgabenstellung gegeben. Es muss nur noch eine geeignette Methode gefunden werden, die Klammern von innen nach aussen aufzulösen. Dafür gibt es verschiedene Möglichkeiten:

Es gilt also das letzte Vorkommen von "(" zu suchen. Benutzt werden kann dabei eine der indexOf-Methoden der Klasse String, genauer: first = s.lastIndexOf('('). Diese Methode liefert die Position der letzten Klammer als int zurück. Wird keine Klammer gefunden ergibt sich -1. Dies ist auch die Abbruchbedingung der Schleife, und es braucht nur noch getestet werden palindromic(s) aus Aufgabe 31.

Wird aber eine "(" gefunden, befindet sich hoffentlich dahinter eine ")". Diese wird durch last = s.indexOf(')', first) ermittelt. Wenn last < 0 ist, wurde die Klammer nicht gefunden und der Ausdruck ist bezüglich der Klammern nicht paarig (siehe Aufgabe 30) und damit auch kein H-Palindrom.

Der Ausdruck innerhalb der Klammern sollte nun ein Palindrom sein: palindromic(s.substring(first+1,last)). Damit ist der Ausdruck ohne die Klammern gemeint ("(xxx)" kann kein Palindrom sein, weil "(" ungleich ")"). Die substring(a, b)-Methode liefert den Teil-String zurück, der von a bis b-1 geht. Demnach ist der innere Ausdruck von first bis last abzüglich der Klammern [first+1, last]. Wenn dies kein Palindrom ist, ist s auch kein H-Palindrom. Wenn aber doch, muss der Ausdruck durch "*" ersetzt werden. Als Hilfestellung betrachten wir diese Grafik. Palindrombeispiel Der neue String besteht aus

Achtung: ist first = 0 oder last+1 > s.length() wirft substring eine Exception aus, weil die Länge der neuen Zeichenkette negativ wäre. Dies muss also vorher getestet werden. Der komplette Programmcode:


  public static boolean hPalindromic(String s) {
    int first;
    while ((first = s.lastIndexOf('(')) >= 0) {
      int last = s.indexOf(')', first);
      if (last < 0) return false;      // bracket-parity doesn't match

      if (palindromic(s.substring(first+1, last))) {
        s = (first > 0 ? s.substring(0, first) : "") + "*"
          + (last < s.length()-1 ? s.substring(last+1, s.length()) : "");
      } else {
        return false;             // inner bracket is not a palindrom
      }
    }
    return palindromic(s);
  }

Aufgabe 33 - Datum als eigene Klasse

  1. Das Datum anhand einer festen Monatslänge von 30 Tagen zu berechnen ist eine einfache Sache. Intern sollte eine absolute Datumsangabe (z.B. die Tage seit dem 1. Januar im Jahre 0) gespeichert werden. Dies vereinfacht die Berechnung von Folgetagen und die Vergleichsoperation. Das Objekt muss diese Tagesanzahl nur in das Datum umrechnen:

    • In die eine
      • days = day + 30*month + 360*year
    • und in die andere Richtung
      • day = days % 30
      • month = (days / 30) % 12
      • year = days / 360

    Bei dieser Berechnung muss beachtet werden, dass die Tage von 0 bis 29 und die Monate von 0 bis 11 gehen. Dies vereinfacht die interne Berechnung.
    Der Benutzer sollte bei der Erstellung einer neuen Instanz der Klasse Date die Wahl zwischen beiden Möglichkeiten haben. Gibt er die absolute Zahl an, braucht diese nur gespeichert werden. Bei der Angabe eines vollständigen Datums, muss man diese erst berechnen.

    
      public class Date {
    
        private long days;
    
        public Date(long days) {
          if (days < 0) throw new IllegalDateException("Datum ist negativ");
          this.days = days;
        }
    
        public Date(int day, int month, int year) {
          if ((day < 0) || (day > 29))
            throw new IllegalDateException("der Tag " + day
                + " liegt nicht zwischen 0 und 11");
          if ((month < 0) || (month > 11))
            throw new IllegalDateException("der Monat " + month
                + " liegt nicht zwischen 0 und 29");
          if (year < 0)
            throw new IllegalDateException("Das Jahr ist negativ");
    
            days = (long) day + 30 * (long) month + 360 * (long) year;
        }
    
        // ...
    
      }

    Falsche Daten sind solche, bei denen der Tag oder der Monat ausserhalb des Bereiches liegt, oder das Jahr negativ ist (den Test auf das negative Jahr könnte man entfernen, dann müsste nur die Berechnung von days angepasst werden).

    Wegen dieser Vorarbeit ist die Implementierung der Methoden einfach:

    
        public Date next() {
          return new Date(days + 1);
        }
    
        public Date previous() throws IllegalDateException {
          return new Date(days - 1);
        }
    
        public long between(Date date) {
          return Math.abs(days - date.days);
        }

    Da Tag, Monat und Jahr immer neu aus days berechnet werden braucht man sich auch keine Gedanken darüber zu machen, ob next() einen neuen Monat oder ein neues Jahr ergibt. Um dem Ganzen einen Sinn zu geben sollte man das Datum auch ausgeben können. Zu beachten ist aber, dass days%30 zum Einen vom Typ long und zum Anderen einen Wert von 0 bis 29 ergibt.

    
        public String toString() {
          int day = (int) (days % 30) + 1;
          int month = (int) ((days / 30) % 12) + 1;
          int year = (int) (days / 360);
          return day + "." + month + "." + year;
        }

    Die verwendete Exception muss noch deklariert werden. Dies könnte zum Beispiel so aussehen:

    
      public class IllegalDateException extends IllegalArgumentException {
    
        public IllegalDateException(String msg) {
          super(msg);
        }
    
        public IllegalDateException() {
          super();
        }
    
      }
  2. Das Hauptproblem in dieser Fragestellung lautet: Was heisst eigentlich "geeignete" Testklasse? Am besten ist wohl eine Klasse, die alle definierten Methoden testet:

    
      public class DateTestClass {
    
        public static void main(String args[]) {
          Date date = new Date(7, 11, 2002);  // das ist der 08.12.2002
          System.out.println(date);
          System.out.println("Abstand von gestern bis morgen: "
            +date.prev().between(date.next()));
        }
    
      }

Auch in der Java-Bibliothek gibt es (im Paket java.util) die Klasse Date, für die man aber die Klasse GregorianCalendar zum Berechnen von Tagen benötigt, was das Ganze etwas umständlich macht. Eine selbst programmierte Date-Klasse, die mit den korrekten Monatslängen arbeitet, Schaltjahre beachtet und den Wochentag berechnet, kann hier heruntereladen werden. Ein Applet dazu gibt es auch noch.

Aufgabe 34 - Verwandschaften

Gegeben seien folgende Relationen:

Daraus folgt:

    • istWeiblich(X) und istElternteilVon(X,Y) => istMutter(X)
    • istMännlich(X) und istElternteilVon(X,Y) => istVater(X)
    • istWeiblich(X) und istElternteilVon(X,Y) und istElternteilVon(Y,Z) => istGrossmutter(X)
    • istMännlich(X) und istElternteilVon(X,Y) und istElternteilVon(Y,Z) => istGrossvater(X)
    • istElternteilVon(Y,X) und istElternteilVon(Y,Z) und X != Z => istGeschwister(X)
    • istGeschwister(X) und istWeiblich(X) => istSchwester(X)
    • istGeschwister(X) und istMännlich(X) => istBruder(X)

Aufgabe 35 - Tutoraufgabe MyMath


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