Algorithmen und Datenstrukturen 2

Übungsblatt 1: Iteration und Rekursion

Anmerkung. Aufgabe 1-2 konnte aufgrund ihres Schwierigkeitsgrads nicht erwartet werden und wurde daher nachträglich zur Zusatzaufgabe herabgestuft.

Aufgabe 1-1 *

Implementieren Sie einen sequentiellen Suchalgorithmus in einer Methode. Die Methode soll als Parameter einen Array vom Typ int[] und einen Wert vom Typ int übergeben bekommen. Ihr Algorithmus soll diesen Wert in diesem Array iterativ suchen und bei Erfolg den Array-Index der Fundstelle zurückgeben.

Zusatzaufgabe 1-2

Implementieren Sie analog zu Aufgabe 1-1 einen sequentiellen Suchalgorithmus, der rekursiv arbeitet.

Aufgabe 1-3

Die Fibonacci-Folge f_n ist wie folgt definiert:

f_n := f_{n − 1} + f_{n − 2} ∀ n ∈ ℕ, n > 1 : f₀ = 0, f₁ = 1

Schreiben Sie eine Methode mit der Signatur int fibonacci (int n), welche die Fibonacci-Zahl an der Stelle n entsprechend dieser Definition rekursiv berechnet und zurückgibt.

Aufgabe 1-4

Schreiben Sie eine Methode mit der Signatur int[] fibonacciFolge (int length), welche einen Array mit length Elementen erzeugt, mit den Zahlen der Fibonacci-Folge entsprechend der Definition aus Aufgabe 1-3 füllt und zurückgibt. Verwenden Sie dazu einen iterativen Algorithmus.

Zusatzaufgabe 1-5

Vergleichen Sie die Algorithmen zu den Aufgaben 1-3 und 1-4.

1. Geben Sie die Zeitkomplexität beider Varianten in der Groß-O-Notation an.
2. Beurteilen Sie die Ausführungsgeschwindigkeit beider Varianten unabhängig von deren Zeitkomplexität.
3. Es existiert ein Lösungsalgorithmus für das Problem von Aufgabe 1-3, der deutlich schneller als jede der beiden Varianten arbeitet. Recherchieren Sie diesen Algorithmus mit Hilfe von Wikipedia oder anderer Literatur und geben Sie dessen Zeitkomplexität an.
4. Implementieren Sie den Algorithmus aus Teilaufgabe (c) in einer Methode.

$Id: HEADER.html 2009-05-04 $