Tutorium Algorithmen und Datenstrukturen 2
Übungsblatt 6: Maximum–Sub-Array, brute force
Aufgabe 6-1*
Schreiben Sie eine Methode zur Lösung des Maximum–Sub-Array–Problems im naïven Verfahren (brute force). Ihre Methode soll einen Array des Typs int[] als Parameter akzeptieren und die maximale Teilsumme dieses Arrays zurückgeben.
Aufgabe 6-2
Finden Sie einen „halb-naïven“ Lösungsalgorithmus, der ebenfalls im Brute-Force–Verfahren arbeitet, jedoch durch Einsparen einer Schleife eine Zeitkomplexität von O(n²) statt O(n³) erreicht.
- Nennen Sie den entscheidenden Unterschied zum naïven Algorithmus aus Aufgabe 6-1.
- Implementieren Sie diesen Algorithmus in sog. „natürlicher Sprache“ entsprechend den Vorlesungsunterlagen der vergangenen Semester.
- Implementieren Sie diesen Algorithmus in Java.
Zusatzaufgabe 6-3
Erweitern Sie die Klasse, die Ihre Lösung zu Aufgabe 6-1 enthält, zu einem ausführbaren Programm. Schreiben Sie dazu eine Methode mit der Signatur public static void main (String[]) zum Testen der Klasse. Die main-Methode muss:
- einen geeigneten Array vom Typ
int[] erzeugen und mit Zahlen füllen,
- eine neue Instanz (Objekt) Ihrer Klasse erstellen,
- auf diesem Objekt Ihre Methode aus Aufgabe 6-1 aufrufen, und
- das Ergebnis des Methodenaufrufs ausgeben.
$Id: HEADER.html,v 1.2 2008/06/04 12:37:32 aj3 Exp $