Übungsaufgaben

zum Kapitel 8.

Kapitel 8.1.1

Übung 8.1: Programmieren Sie eine Funktion, die nach der Formel n! = (n-1)! × n die Fakultät einer natürlichen Zahl rekursiv berechnet:

static int fakultät(int n);

Kapitel 8.1.5

Übung 8.2: Implementieren Sie die folgende Schnittstelle:

interface ILogBehaelter {
   void fuellen(boolean wert) throws VollException;
   void entleeren() throws LeerException;
   boolean inhalt() throws LeerException;
   boolean istGefuellt(); }

Erkennen Sie die Ausnahmesituationen mit Abfrage.

Kapitel 8.2.1

Übung 8.3: Entwickeln Sie eine Prozedur (Methode einer abstrakten Klasse), die die Wertetabelle einer beliebigen Funktion im gegebenen Intervall erstellt. Die zu berechnende Funktion ist eine Rückruffunktion. Die Ergebnisse sollen auch von Rückrufprozeduren übernommen werden:

interface IWertetabelle {
   void wertetabelle(float untergrenze, float obergrenze, int anzahlSchritte);
   float funktion(float x) throws KeinFunktionswertException; // abstract
      // die zu berechnende Funktion
   void ergebnis(float x, float y); // abstract
      // Übernahme der Ergebnisse
   void keinFunktionswert(float x); } // abstract
      // Übernahme, wenn kein Funktionswert berechnet werden kann

Die Schrittweite der Wertetabelle kann mit Hilfe der Formel berechnet werden:

Rufen Sie Ihre Prozedur in einem Testprogramm für die Funktion f(x) = 1/(x-k) und für einen Intervall [a, b] auf, dessen Grenzen (wie auch die Funktionskonstante k) interaktiv eingegeben werden. Die Übernahmeprozedur soll die Wertetabelle in zwei Spalten (x-Wert und y-Wert) ausgeben. An den x-Stellen, für die kein y-Wert berechnet werden kann (z.B. weil x=k), soll keinFunktionswert aufgerufen werden.

Kapitel 8.2.3

Übung 8.4: Implementieren Sie die folgende Schnittstelle Zeichenkette mit Hilfe der Klasse String. Verwenden Sie dabei nur die Methoden length und charAt:

public interface IZeichenkette {
   void austauschen(final char altesZeichen, final char neuesZeichen);
      // tauscht alle Vorkommnisse von altesZeichen auf neuesZeichen aus
   int finden(char zeichen); // const
      // gibt den Index des ersten Vorkommnisses vom zeichen zurück, oder -1
   int finden(int position, char zeichen); // const
      // Index des ersten Vorkommnisses vom zeichen nach position, oder -1
   Zeichenkette unterzeichenkette(int anfang, int ende); // const
   boolean istGleich(final Zeichenkette zeichenkette); // const
   void kopieren(final Zeichenkette zeichenkette);
}

Weil das String-Objekt unveränderbar ist, müssen Sie in den Mutatoren ein neues String-Objekt erzeugen und das alte verwerfen.

Kapitel 8.2.4

Übung 8.5: Schreiben Sie eine Prozedur mit einem int-Parameter (zwischen 1 und 9), welches mithilfe von zwei geschachtelten Schleifen die Bezeichnungen der Felder eines Schachbretts in folgender Form auf System.out ausgibt (Beispiel für Parameter = 8):

A1 A2 A3 A4 A5 A6 A7 A8
B1 B2 B3 B4 B5 B6 B7 B8
C1 C2 C3 C4 C5 C6 C7 C8
D1 D2 D3 D4 D5 D6 D7 D8
E1 E2 E3 E4 E5 E6 E7 E8
F1 F2 F3 F4 F5 F6 F7 F8
G1 G2 G3 G4 G5 G6 G7 G8
H1 H2 H3 H4 H5 H6 H7 H8

Kapitel 8.3.2

Übung 8.6: Programmieren Sie eine Prozedur, mit deren Hilfe anfängliche, abschließende und doppelte Zwischenräume aus einer Zeichenkette entfernt werden können:

public String aufraeumen(String zeichenkette); // entfernt alle überflüssigen
   // Zwischenräume aus zeichenkette und liefert das Ergebnis als String

Übung 8.7: Schreiben Sie ein Hauptprogramm, das Zählen von Buchstaben durchführt. Lesen Sie von der Tastatur eine Zeile ein und zählen Sie die Häufigkeit jedes Buchstabens in einer Tabelle. Geben Sie zum Schluss das Ergebnis auf der Konsole aus.

Übung 8.8: Entwickeln Sie ein Java-Dialogprogramm für das folgende Problem der Zeichenanalyse: Die von der Tastatur eingegebenen Zeichen sollen analysiert und eine Statistik ausgegeben werden. Folgende Informationen werden verlangt:

Die Anzahl der insgesamt eingelesenen Zeichen
Die Anzahl der Klein- und Großbuchstaben
Die Anzahl der Ziffern
Die Anzahl der Vokale
Die Anzahl der Konsonanten
Die Anzahl der Sonderzeichen

Kapitel 8.4.2

Übung 8.9: Erstellen Sie eine (rekursive) Funktionsdeklaration, die die Werte der Ackermann-Funktion liefert. Sie wird durch die folgende Formel definiert:

ackermann(n, m) = n+1                                    wenn m = 0
                  ackermann(m-1, 1)                      wenn m > 0 und n = 0
                  ackermann(m-1, ackermann (m, n-1))     ansonsten

Schreiben Sie ein Testprogramm für diese Funktion. Überwachen Sie die Laufzeit des Funktionsaufrufs mit Hilfe Methode getTime der Klasse java.util.Date (diese parameterlose Funktion liefert einen long-Wert, die Anzahl der Millisekunden seit dem 1. Januar 1970, 0 Uhr GMT). Ermitteln Sie auch die Anzahl der rekursiven Aufrufe und stellen Sie schriftlich eine Tabelle für verschiedene Parameterkombinationen zusammen.

Die Ackermann-Funktion ist ein Beispiel für eine Rekursion, die nicht (oder zumindest nicht direkt) durch Iteration ersetzt werden kann. Ihre Eigenschaft ist bekannt, dass sie stärker wächst als jede sog. primitiv-rekursive Funktion: Der Wert von ackermann(4, 2) kann mit 19729 Dezimalziffern beschrieben werden. ackermann(4, 4) ist größer als 10^N, wo N = 10^M, wo M = 10¹⁹⁰⁰⁰. (Die Anzahl der Elementarteilchen im bekannten Universum liegt nach einigen Schätzungen etwa bei 10⁷⁰.)

Übungsaufgaben zum Kapitel 9