Praktikum Datenverarbeitung 3. Aufgabe

SS 1996 - Fachhochschule Köln
Fachbereich Nachrichtentechnik
Matthias Groß

Praktikum Datenverarbeitung - 3. Aufgabe

Abgabetermin für alle: Montag 24.06. 1996 im DV-Labor

Bei dieser Praktikumsaufgabe sollen alle erlernten Fähigkeiten einmal gesammelt verwendet und zu einem Programm vereinigt werden. Diese Aufgabe enthält auch viele Komponenten, die für die Klausur wichtig sind. Es werden zur konkreten Bearbeitung folgende Hilfsmittel benötigt: Bäume und die Anwendung dieser Strukturen für sortierte Ausgaben und Auswertungen in Verbindung mit dynamischer Speicherverwaltung, Stringbearbeitung und die Verwendung rekursiver Funktionen.

Es soll ein Programm zum symbolischen Differenzieren geschrieben werden, d.h. aus einem Ausdruck der Form f(x)=a*x^3+x*(x+2*x^2) soll f'(x)=a*3*x^2+1*(x+2*x^2)+x*(1+2*2*x^1) oder noch besser f'(x)=a*3*x^2+x+2*x^2+x*(1+4*x) werden.

Wer Lust hat, kann auch leicht Erweiterungen wie sin(x), cos(x), exp(x) etc. hinzunehmen.

Beachten Sie bitte auch alle weiteren Hinweise aus der Vorlesung. Verwenden Sie bitte das Beispielprogramm ableit.c mit dem Headerfile ableit.h

Bei dieser Aufgabe stellen sich Ihnen mehrere Probleme:

Wie soll die Funktion f(x) gespeichert werden? (Thema: Bäume und dynamische Speicherverwaltung)
Wie soll f(x) eingelesen werden? (Thema: Stringbearbeitung)
Wie wird die Generierung der Ableitung realisiert? (Thema: Rekursive Funktionen)

Die Speicherung der Funktion erfolgt in Form eines Binär-Baumes, der sich schrittweise wie folgt aufbaut:

1. Schritt 2. Schritt 5. Schritt

Der Baum
__+__ a*x^3 x*(x+2*x^2)

_____+____ __*__ __*__ a x^3 x x+2*x^2

____+______ __*__ __*__ a __^__ x __+__ x 3 x __*__ 2 __^__ x 2

	1. Schritt	2. Schritt	5. Schritt
Der Baum	__+__ ax^3 x(x+2*x^2)	_____+____ ____ ____ a x^3 x x+2*x^2	____+______ ____ ____ a __^__ x __+__ x 3 x __*__ 2 __^__ x 2

Man erkennt im obigen Beispiel recht gut, wie an jedem Knoten des B-Baumes, der zwei Nachfolger hat, jeweils ein Operator (+, -, *, /, ^) steht und an den Blättern jeweils eine Zahl oder x bzw. eine andere Variable. Eine Speicherung mathematischer Ausdrücke in dieser Form nennt man Syntaxbaum. Hat man diesen Syntaxbaum einmal aufgebaut, so kann man davon ausgehend viele Dinge tun. Die erste Aufgabe ist die Ausgabe des eingegebenen und im B-Baum abgespeicherten Ausdruckes sowohl in Postfix-Notation (2 x 3 ^ * x x 2 x 2 ^ * + * +) als auch wieder in Infix-Notation (a*x^3+x*(x+2*x^2)). Das fertige Programm sollte nachher ein kurzes Menue wie folgt aufweisen:

Eingeben eines neuen Ausdrucks.
Ausgabe des Ausdrucks in Infix- und Postfix-Notation
n-te Ableitung ausgeben (n natürliche Zahl), Ausgabe als Infix- oder Postfix-Notation
Berechnung des Ausdrucks für x beliebige reelle Zahl.

Tips und Anregungen:

Wie sieht ein Baumknoten aus?
Machen Sie sich Gedanken zu der Rangfolge der Operatoren.
Wie kann man die Ausdrücke evtl. etwas kürzen?
Was machen Sie mit Klammern (a+x)*(2+x^2)? Dieses Problem stellt sich sowohl beim Einlesen, als auch bei der Ausgabe.
Wie lesen Sie den mathematischen Ausdruck ein? (Die einfachste Version ist das Einlesen als Postfixnotation von hinten aus...)

Literatur: Algorithmen in C, Robert Sedgewick, Addison-Wesley 1992.

Seite zuletzt aktualisiert am 12.06.1996 von Matthias Groß.
Diese Seite ist Teil des WWW-Dienstes der FH-Köln, Germany.