Algorithmen und Datenstrukturen 2
Übungsblatt 9: Maximum–Sub-Array–Problem, rekursive Algorithmen
Abgabe bis Montag, 29. Juni, 16:30 Uhr.
Aufgabe 9-1 *
Implementieren Sie den rekursiven, nach dem Prinzip divide and conquer arbeitenden Lösungsalgorithmus des Maximum–Sub-Array–Problems. Verwenden Sie für die Bestimmung der Randmaxima Ihre Methoden aus den Aufgaben 8-1 und 8-2.
Tipp. Verwenden Sie folgende Methodensignatur:
static int methodenName (int[] array, int linkeGrenze, int rechteGrenze)
Tipp. Die Methoden aus den Aufgaben 8-1 und 8-2 müssen leicht angepasst werden, um im Kontext dieses Algorithmus wie nötig funktionieren zu können.
Aufgabe 9-2
- Ist der Algorithmus aus Aufgabe 9-1 als hard split, easy join oder als easy split, hard join zu charakterisieren? Begründen Sie Ihre Antwort. Kennzeichnen Sie in Ihrem Quellcode zu Aufgabe 9-1 jeweils Beginn und Ende von split und join!
- Nennen Sie weitere Beispiele für divide and conquer–Algorithmen und teilen Sie diese als hard split, easy join bzw. easy split, hard join ein!
Zusatzaufgabe 9-3
In dem Array new int[] {1, -1, 1} sind mehrere Maximum–Sub-Arrays mit derselben Summe 1 enthalten.
- Schreiben Sie einen Algorithmus in „natürlicher Sprache“ nach Dr. Bürg, der nicht ein, sondern alle maximalen Sub-Arrays ermittelt und deren Grenzen ausgibt. Verwenden Sie ein Lösungsverfahren Ihrer Wahl.
- Schreiben Sie eine Java-Klasse, deren Objekte geeignet als Rückgabetyp für eine Methode wären, die Ihren Algorithmus aus Teilaufgabe (a) in Java implementiert.
- Kombinieren Sie Teilaufgaben (a) und (b) in einer Klassenmethode in Java.
$Id: HEADER.html 2009-06-22 $
Name Last modified Size Description
Parent Directory -
HEADER.html 2023-10-11 10:00 2.3K
Loesung91.java 2023-10-11 10:00 3.6K