Algorithmen und Programmierung II

 

SS 2002 Dr. Hannes Federrath
Übung 5 Natalie Ardet
Abgabe bis zum Do. 06.06.02

Die Lösung der Aufgaben und die Abgabe der Lösungen erfolgt in Zweiergruppen!

Hinweis: Benutze die Ressourcen der ALP2 Webseite.

Aufgabe 1 (4 + 4 + 1 + 2  = 11P.)

Die Reihe der Lucas'sche Zahlen ist wie folgt definiert :

ì
ï
í
ï
î
L1 = 1 ;  
L2 = 3 ;  
Lk = Lk-1 + Lk-2  für  k > 2 .

1. Schreibe eine Java Klasse Lucas die eine rekursive Methode enthält die das n-te  Element der Lucas'sche Reihe berechnet und am Bildschirm ausgibt. Die Signatur der Methode ist vorgegeben:
    int getElementRec(int n)

2. Füge der Klasse Lucas eine iterative Methode hinzu die das n-te  Element der Lucas'sche Reihe berechnet und am Bildschirm ausgibt. Die Signatur der Methode ist vorgegeben:
    int getElementIter(int n)

3. Verwende deine Klasse Lucas mit einer Testtreiberklasse (z.B. den ALP2Wrapper) um das 1. , das 2., das 30. und das 40. Element der Lucas'sche Reihe zu berechnen, sowohl rekursiv als auch iterativ.     
    a. Welche ist die 40. Lucas'sche Zahl?
    b. Vergleiche die Dauer der iterativen und rekursiven Berechnung.

Aufgabe 2 ( 10 P.)

Entwickle eine rekursive Methode

void permute(char[] aWord, int length)

die alle Permutationen der ersten length Zeichen in der Reihung aWord, jeweils gefolgt von den übrigen (unveränderten) Zeichen am Bildschirm ausgibt. Die Zeichen in aWord dürfen dabei modifiziert werden. 

Hinweis: Um i Elemente zu permutieren, kann man nacheinander jedes dieser Elemente an eine feste Position bringen (z.B. die erste oder letzte) und für jede solche Konstellation die übrigen i-1 Elemente permutieren.

Aufgabe 3 ( 12 P.)

Eine FIFO-Queue  (First-In-First-Out-Schlange) verwaltet eine Folge von Elementen und unterstützt die Operationen Einfügen  und Löschen. Einfügen fügt ein neues Element am Ende der Folge ein. Löschen entfernt das erste Element und liefert es zurück. Zu Beginn ist die Folge leer. 

Entwerfe  eine Klasse FIFOQueue, die FIFO-Queues mit Hilfe zweier Stapel repräsentiert (d.h. Datenstrukturen, die nur die Operationen push und pop unterstützen, dies aber in konstanter Zeit). Die Kapazität der FIFO-Queue ist begrenzt und wird bei der Erzeugung der FIFO-Queue festgelegt. Das Einfügen setzt voraus, dass die FIFO-Queue nicht voll ist. Das Löschen setzt voraus, dass die FIFO-Queue nicht leer ist. Die FIFO-Queue verwaltet Elemente vom vordefinierten Java-Typ "Object".

Hinweis: Die Ergebnisse der 2. Aufgabe vom 4. Übungsblatt dürfen wiederverwendet werden :)  

03.06.2002