Arraysumme
In diesem – für das Teile-und-Herrsche-Prinzip etwas künstliche – Problem soll die Summe aller Zahlen in einem Array aus Integer-Zahlen berechnet werden.
(A1)
Lade dir das Bluej-Projekt von https://codeberg.org/qg-info-unterricht/array-summe herunter.
- Untersuche und teste den Konstruktor der Array-Klasse.
- Implementiere die iterative Methode
sumIterativ(), die mit Hilfe einer Schleife die Summe aller Array-Elemente berechnet.
Rekursion! Teile und herrsche...
Wie kann man dieses Problem rekursiv lösen? Zur Erinnerung:
- Finde einen einfachen Fall, den du als Basisfall verwenden kannst.
- Finde heraus, wie du die Aufgabe vereinfachen kannst, um zum Basisfall zu gelangen.
Was ist der direkt lösbare Basisfall für dieses Problem? Wie muss ein Array beschaffen sein, damit man die Summe aller Array Elemente unmittelbar erkennen kann?
Um das Teile-und-Herrsche Prinzip anwenden zu können muss man sich nun einen Rekursionsfall überlegen, der uns dem Basisfall, dem "Ziel" des leeren Arrays immer näher bringt.
Wie kann man also beispielsweise die folgende Situation so verändern, dass die zur Summe aus kleineren Array(s) führt?
Die Funktionsweise kann man also dem folgenden Flussdiagramm, entnehmen:
Das ist nun wieder eine klassische Rekursion, deren Aufrufe alle auf dem Call-Stack landen, bis der Basisfall erreicht ist. Erst dann können die vorigen Aufrufe abgeschlossen werden.
(A2)
Implementiere die rekursive Methode sumRekursiv im Bluej-Projekt nach den Erläuterungen dieser Wiki-Seite.1)
(A3)
Schreibe eine rekursive Methode zum Ermitteln der größten Zahl im Array.
arrayList.remove(INDEX);