Algorithmen und Programmierung II

Aufgabe 1 (6 P.)

In der Vorlesung wurde erklärt wie man mit der Methode des rekursiven Abstiegs einen arithmetischen Ausdruck einlesen kann.

Eine Grammatik für arithmetische Ausdrücke mit den Operatoren +, -, *, /, die auch die Präzedenzen berücksichtig, ist:

expression = term { addop term }
term = factor { mulop factor }
factor = number | ( expression )
addop = + | -
mulop = * | /
number = digit { digit }
digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Implementiere einen Calculator (Taschenrechner), der von der Tastatur aus eingegebene arithmetische Ausdrücke zeilenweise einliest, unter Berücksichtigung der Operatorenpräzedenzen auswertet und das Ergebnis zurückliefert.

Bei nicht korrekt gebildeten arithmetischen Ausdrücken soll eine Fehlermeldung (z.B. "parse error") ausgegeben werden. Ob Ihr mit ints oder longs rechnet, bleibt euch überlassen.

Aufgabe 2 (6 P.)

Erweitere das hier verlinkte Rahmenprogramm durch überschreiben der Methode public void paint(Graphics g) (und ggf. durch Hinzufügen von Methoden, z.B. eine rekursive zur Behandlung de Fraktale) derart, daß das Programm eines der unten aufgeführten Fraktale zeichnet, und zwar in der Rekursionstiefe, die von der Kommandozeile aus eingelesen wurde.

Zum Rahmenprogramm siehe auch Einführung in die Fensterprogrammierung unter Java, Teil 1.

• Die Kochkurve, 1904 vom Schwedischen Mathematiker Helge von Koch eingeführt. Das folgende Bild zeigt die ersten sechs Rekursionsschritte.

  Die ersten sechs Rekursionsschritte (Rekursionstiefe null bis fünf) der Kochkurve.

  Bei jedem Rekursionsschritt wird jede Strecke in drei Teile geteilt und die mittlere Teilstrecke durch zwei Strecken ersetzt, die im Winkel von 60 Grad anliegen:

  Die Kurve wird auch Schneeflockenkurve genannt:

  

• Die Hilbertkurve, eingeführt 1908 vom deutschen Mathematiker David Hilbert:

  Die ersten vier Rekursionsschritte.

  Die Ersetzung für einen Rekursionsschritt.

  Hier noch eine verbale Beschriebung der Konstruktion der Hilbertkurve (nach Peitgen et.al., Chaos - Bausteine der Ordnung, Springer-Verlag 1994, S. 544 f.), mit besten Dank an Meike für's Heraussuchen:

  Das Ziel ist eine Kurve, die im Verlauf mit hinreichender Genauigkeit jeden Punkt der Fläche berührt, bzw. sie "vollständig ausfüllt". Das zu füllende Quadrat wird in 4 Teile geteilt, deren Mittelpunkte in der gezeigten Art durch eine Kurve aus drei Teilstücken verbunden ist. Dies ist die erste Stufe der Hilbert-Kurve (links im obigen Bild). In nächsten Schritt ersetzt man dieses "eckige Hufeisen" durch vier ähnliche Figuren, die aber nur halb so groß sind. Zwei von ihnen werden in der gezeigten Weise (obiges Bild, mitte) gedreht. Um die zweite Stufe der Hilbert-Kurve zu vervollständigen, werden die Teile durch drei weitere Streckenstücke (rot gezeichnet) verbunden.

• Das Sierpinski-Dreieck, eingeführt 1916 von dem polnischen Mathematiker Waclaw Sierpinski:

  Die ersten vier Rekursionsschritte.	Konstruktion der gleichseitigen Dreiecke.

Hintergrund:

Der Begriff "Fraktal" bezieht sich auf die gebrochene Dimension einer fraktalen Figur (der Grenzwert der rekursiven Figur für Rekursionstiefe gegen unendlich) und wurde geprägt durch Benoit B. Mandelbrot. Die Dimension entspricht dem Exponenten, mit welchem die Ausdehnung einer Figur potenziert werden muss, um deren Volumen zu erhalten.