Grundlagen

Der Themenbereich Algorithmen und Datenstrukturen gehört zu den klassischen Themen der Informatik. Ziel ist, verschiedene Lösungsstrategien, Standardalgorithmen und (abstrakte) Datentypen kennenzulernen, die für die erfolgreiche Entwicklung von (größeren) Softwaresystemen nötig sind. Für Erklärungen wird auf dieser Webseite die Programmiersprache Java verwendet.

Felder

Oft muss man in Programmen viele gleichartige bzw. gleich strukturierte Daten verarbeiten. Beispielhaft sei die Sammlung von Kontaktdaten (z. B. Name, Telefonnummer, E-Mail-Adresse), Rechnungsdaten, Messwerte oder Aktienkurse genannt. Zum Speichern und Verarbeiten gleichartiger Daten benutzt man in Java ein Feld. Ein Feld (engl. array) ist eine Reihe von Variablen gleichen Datentyps. Die einzelnen Variablen können über einen Index angesprochen werden, der in rechteckigen Klammern geschrieben wird (z. B. Name[index] oder Wert[nr]).

In Feldern kann man eine begrenzte Anzahl gleichartiger Daten speichern, also zum Beispiel 20 Stringvariablen (z. B. für Namen) oder 12 int-Zahlen (z. B. für Messwerte). Alle Variablen haben damit die gleiche Größe. Im Gegensatz zu einfachen Datentypen wie int, double, char oder boolean ist ein Feld ein sog. strukturierter Datentyp.
Die Feldvariablen werden gemäß folgendem Syntaxdiagramm gebildet:

SyntaxFeld

Sei der Name des Feldes Zahl, dann hat die erste Variable den Namen Zahl[0] und 0 als Index, die vierte den Namen Zahl[3] und 3 als Index. Die Variablennamen beginnen also alle mit dem Namen des Feldes und unterscheiden sich im Index. Der Index beginnt immer bei 0. Beim Erzeugen eines Feldes gibt man an, aus wie vielen Variablen es bestehen soll.

Nachfolgend wird ein Feld mit vier Ganzzahl-Variablen erzeugt:
     int[] Zahl = new int[4];

Der Vorteil von Feldern im Vergleich zu unabhängigen Variablen ist, dass die programmtechnische Verarbeitung mit Schleifen erfolgen kann. Mit einer for-Schleife kann man beispielsweise der Reihe nach alle Feldvariablen mit einer Wertzuweisung initialisieren bzw. die Werte ausgeben:

for (int i = 0; i < 4; i++) {
   Zahl[i] = i*i;
   System.out.println(Zahl[i]);
}



Aufgaben
a) Schreibe ein Konsolenprogramm, das ein Feld Note für 30 double-Werte definiert und die Feldvariablen mit Hilfe einer Schleife mit den Werten 30-i (i entspricht dem jeweiligen Indexwert) initialisiert. Schreibe dann eine Methode, um das Feld vollständig auszugeben.

b) Werden die zwei ersten Glieder einer Zahlenfolge vorgegeben und berechnet sich das n-te Glied nach der Formel
    A(n) = A(n-1) + A(n-2)
so entsteht eine Fibonacci-Folge. Mit den Anfangswerten A(1) = 1 und A(2) = 2 erhält man die Zahlenfolge 1, 2, 3, 5, 8, 13, 21, . . .

Entwickle ein Java-Programm, das das n-te Glied der Folge - also A(n) - unter Zuhilfenahme eines Feldes berechnet. Wie viele Berechnungsschritte sind für A(10) notwendig?


Rekursion

Neben interativen Algorithmen spielen auch rekursive Algorithmen eine wichtige Rolle in der Informatik. Als Rekursion bezeichnet man die Technik eine Funktion durch sich selbst zu definieren (rekursive Definition). Wenn im Funktionskörper ein Aufruf der Funktion steht, spricht man von direkter Rekursion. Sofern eine Funktion über eine andere Funktion aufgerufen wird, spricht man von indirekter Rekursion.

Beim rekursiven Aufruf einer Funktion ist es wichtig zu verstehen, wie einzelne Berechnungen durchgeführt werden. Der Funktionswert f(n+1) einer Funktion f: N0 -> N0 ergibt sich durch Verknüpfung bereits vorher berechneter Werte f(n), f(n-1), ...
Falls außerdem die Funktionswerte von f für hinreichend viele Startargumente bekannt sind, kann jeder Funktionswert von f berechnet werden. Bei einer rekursiven Definition einer Funktion f ruft sich somit die Funktion so oft selbst auf, bis ein vorgegebenes Argument (das Abbruchkriterium) erreicht ist.

Beispiele für einfache rekursive Funktionen sind

Fakultät:   F(n) = F(n-1) * n
Fibonacci-Folge:   A(n) = A (n-1) + A(n-2)

Jeder Aufruf der rekursiven Funktion muss sich durch Entfalten der rekursiven Definition in endlich vielen Schritten auflösen lassen. Man sagt, sie darf nicht in einen infiniten Regress (vulgo Endlosschleife) geraten. Wenn man mehrere Funktionen durch wechselseitige Verwendung voneinander definiert, spricht man von wechselseitiger Rekursion.

Beispiel: "Fibonacci-Folge"

public int fib(int n) {
   if (n>2)
     return fib(n-1)+fib(n-2);
  else
     return 1;
}

public static void main (String[] args) {
  System.out.println(fib(5));
}

LernRek Lernkomponente zu Rekursion
Eine Flash-Anwendung zur Erklärung von Rekursion anhand des Turms von Hanoi wurde von Dustin Gathmann, Timo Glanzner und Timo Sturm entwickelt.
LernRek Bitte hier klicken, um die Lernkomponente zu starten.



Aufgabe
Entwickle ein Java Programm, das die Fakultät F einer natürlichen Zahl n iterativ und rekursiv berechnet.
F(0) = 1, F(1) = 1, F(2) = 2, F(3) = 6, F(4) = 24, ...

Auf folgender Seite findest Du Lösungen zu dieser Aufgabe.



Weitere nützliche Links