zu den Aufgaben im Kapitel 3
Aufgabe 3.1: Erstellen Sie eine Funktion, die die Werte der Ackermann-Funktion (zumindest für kleine Parameter) mit Hilfe eines Gedächtnisses liefert. Überwachen Sie die Laufzeit des Funktionsaufrufs mit Hilfe der Methode getTime der Klasse java.util.Date. Ermitteln Sie auch die Anzahl der rekursiven Aufrufe und stellen Sie eine Tabelle für verschiedene Parameterkombinationen zusammen.
Lösung:
public class Ackermann {
private int max, nax;
private long ged[][]; // Gedächtnis
public Ackermann(int max, int nax) {
this.max = max;
this.nax = nax;
ged = new long[max][nax];
for (int i = 0; i < max; i++)
for (int j = 0; j < nax; j++)
ged[i][j] = 0; // vorbesetzen
}
public long ackermann(int n, int m) {
// requires 0 <= n < max && 0 <= m < max
if (ged[n][m] == 0)
ged[n][m] = n == 0 ? m + 1 :
(m == 0 ? ackermann(n - 1, 1) :
ackermann(n - 1, (int)ackermann(n, m - 1)));
return ged[n][m];
}
public static void main(String[] args) {
System.out.println("Ackermann mit Gedaechtnis");
if (args.length < 3)
System.out.println("Usage: Ackermann max nax m n");
else {
int max = Integer.parseInt(args[0]);
int nax = Integer.parseInt(args[1]);
int m = Integer.parseInt(args[2]);
int n = Integer.parseInt(args[3]);
try {
java.util.Date datum = new java.util.Date();
long anfang = datum.getTime();
long ack = new Ackermann(max, nax).ackermann(m, n);
long ende = datum.getTime();
System.out.println("ackermann(" + m + ", " + n + ") = " + ack);
System.out.println("Zeitbedarf: " + (ende - anfang) + " millisekunden");
} catch(IndexOutOfBoundsException e) {
System.out.println("Gedaechtnis zu klein: " + e);
} catch(StackOverflowError e) {
System.out.println("Systemstapel zu klein: " + e);
}
}
}
}
Aufgabe 3.2: Entwickeln Sie eine Funktion permutationen für die rekursive Berechnung von Permutationen. In der Funktion sollen Sie eine zweidimensionale Reihung lokal anlegen, die die Permutationen aus n-1 Elementen enthält. Sie sollen diese in das Ergebnis (ebenfalls eine lokale zweidimensionale Reihung der Größe n! × n, ) n-mal kopieren und das letzte Element an die 1-ste, 2-te, ... n-te Stelle einschieben. Eine geschickte Manipulation der Reihungsindizes ist hier der Schlüssel für eine elegante Lösung.
Lösung: fehlt noch
Aufgabe 3.3: Ein Iterator läuft über alle Elemente einer Liste oder Reihung und führt an jedem Element eine bestimmte Operation aus. Diese kann gegebenenfalls eine Bedingung überprüfen, der das Element genügen muss, z.B. um verändert zu werden. Beispielsweise könnte die Operation heißen, jede ungerade Zahl in einer Liste inkrementieren. Sie muss dann in der Elementklasse programmiert werden, wie etwa:
public void operation() { if (wert % 2 == 1) // wert ist die Komponente der Elementklasse wert++; }
Iteratore werden oft mit Hilfe einer Schleife programmiert:
public void iterator() { for (int index = 0; index < inhalt.length; index++) inhalt[index].operation(); // operation für jedes Element aufrufen }
Programmieren Sie den iterator für eine Reihung auch rekursiv. Programmieren Sie ihn für eine verkettete Liste sowohl rekursiv wie auch iterativ.
Lösung für die Reihung:
public void iteratorRekursiv(int index) { // requires 0 <= index && index < inhalt.length; inhalt[index].operation(); // operation für akutelles Element aufrufen if (index < inhalt.length - 1) iteratorRekursiv(index + 1); }
Lösung für die Liste:
public void iterator() {
Knoten knoten = this.aelteste;
while (knoten != null) { // Listen nicht zu Ende
knoten.wert.operation();
knoten = knoten.verbindung; } }
private void iteratorRekursiv(Knoten knoten) {
if (knoten != null) {
knoten.wert.operation();
iteratorRekursiv(knoten.verbindung); } }
public void iteratorRekursiv() {
iteratorRekursiv(aelteste); }
Aufgabe 3.4: Programmieren Sie die Schneeflockenkurve mit einem gleichseitigen Dreieck als Initiator. Der Generator setzt auf jeder Seite des Dreiecks an.
Lösung: fehlt noch
Aufgabe 3.5: Untersuchen Sie das Programm der Drachenkurveund zeichnen Sie die ersten drei Stufen:
final static double wurzelZwei = Math.sqrt(2); public void drache(int stufe, double laenge, boolean richtung) { // zeichnet Drachenkurve der angegebenen Stufe if (stufe == 0) // Rekursion abbrechen k.strecke(laenge); else { // zweimal rekursiver Aufruf final int gradLinks = 45 * (richtung ? -1 : 1); final int gradRechts = 90 * (richtung ? 1 : -1); laenge /= wurzelZwei; stufe--; k.richtung(gradLinks); drache(stufe, laenge, false); k.richtung(gradRechts); drache(stufe, laenge, true); k.richtung(gradLinks); } }
Lösung: fehlt noch
Aufgabe 3.6: Die Sierpinski-Kurve wird nach einem ähnlichen Prinzip, jedoch etwas komplexer aufgebaut:
Hierbei besteht die Kurve Sk aus vier Exemplaren von Sk-1, die in unterschiedliche Richtungen gedreht und am Eck (rechts unten, rechts oben, links oben bzw. links unten) mit einer Verbindungsstrecke doppelter Länge verbunden werden.
Entwickeln Sie eine der Klasse Hilbert ähnliche Klasse Sierpinski, mit deren Hilfe Annäherungen der Sierpinski-Kurve gezeichnet werden können.
Lösung: fehlt noch
Aufgabe 3.7: Gestalten Sie den Algorithmus Weg des Springers so um, dass er nicht nur eine Lösung, sondern alle Lösungen ermittelt.
Lösung: fehlt noch
Aufgabe 3.8: Entwerfen Sie einen Algorithmus, der das Problem der Stabilen Liebesbeziehungen löst. Hier müssen n Ehepaare so einander zuneigen, dass ihre Ehen ungefährdet sind. Jeder der 2n Beteiligten besitzt eine Liste der Länge n, in der die Personen des anderen Geschlechts in der Reihenfolge der Zuneigung aufgeführt sind. Eine Ehe gilt als gefährdet, wenn es einen anderen Mann und eine andere Frau gibt, dem die Frau bzw. der der Mann mehr zugeneigt ist als dem Ehepartner.
Die Abbildung 3.22 zeigt zum Beispiel eine instabile Liebesbeziehung, wenn die Größe der Pfeile das Maß der Zuneigung repräsentiert: Adam hat Bella lieber als seine Ehefrau Anna, und Bella hat Adam lieber als ihren Ehemann Berthold.
Lösung: fehlt noch
Aufgabe 3.9: In der Programmiersprache Ada gilt die Regel, dass ein Bezeichner keine zwei Unterstriche nebeneinander und auch keinen Unterstrich am Anfang und am Ende enthalten darf. Entwerfen Sie einen regulären Ausdruck, der die Sprache der Bezeichner „im Ada-Stil“ beschreibt.
Lösung: Grammatik:
Regulärer Ausdruck:
(a|b|...|z|A|B|...|Z) (_|e)(a|b|...|z|A|B|...|Z|0|1|...|9)) * e
Aufgabe 3.10: Schreiben Sie einen regulären Ausdruck auf, der die Sprache aller Binärbrüche beschreibt. Ein Binärbruch enthält genau einen Punkt (als Binärpunkt), vor und nach dem mindestens je eine Binärziffer (0 oder 1) stehen muss. Er darf keine führenden und abschließenden (d.h. überflüssigen) Nullen enthalten, wenn der Ganzteil oder der Bruchteil keine Einser enthält: 1000100101001.10011110101, 1.1, 0.1, 1.0 und 0.0 sind Binärbrüche, während 1, 1.2, 1.10, 01.1, .1, 0.10.1 und 1,1 keine Binärbrüche sind.
Lösung:
((1 Ziffer * e) | 0) . (0 | (Ziffer * e 1))
Aufgabe 3.11: Wandeln Sie die regulären Ausdrücke aus den Aufgaben 3.9 und 3.10 zu einer – besser lesbaren – regulären Grammatik um.
Lösung:
Bezeichner ® Buchstabe ((_ | e) (Buchstabe | Ziffer)) * e Buchstabe ® a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z| A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z| Ziffer ® 0|1|3|4|5|6|7|8|9
Binärbruch ® Ganzteil . Bruchteil Ganzteil ® 0 | 1 Ziffernfolge Bruchteil ® 0 | Ziffernfolge 1 Ziffernfolge ® Ziffer * e Ziffer ® 0|1|3|4|5|6|7|8|9
Aufgabe 3.12: Schreiben Sie eine Java-Funktion, die die Arbeitsweise eines endlichen Automaten implementiert. Ihr Parameter ist der endliche Automat und das zu erkennende Wort, ihr Ergebnistyp ist boolean. Das Ergebnis ist true, wenn das Wort zur Sprache des Automaten gehört und false, wenn nicht. Sie müssen selbstverständlich auch die Klasse vereinbaren, die den endlichen Automaten darstellt.
Lösung:
public class EndlicherAutomat { private int[][] automat; private boolean[] endzustand; public EndlicherAutomat(int[][] automat, boolean[] endzustand) { // requires automat[i][j] >= 0 && automat[0][j] == 0 && endzustand[0] == false; this.automat = automat; this.endzustand = endzustand; public boolean gehoertZurSprache(int[] wort) { int zustand = 1; for (int i = 0; i < wort.length; i++) zustand = automat[zustand][wort[i]]; // Zustandsübergang return endzustand[zustand]; } }