Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:teile_und_herrsche:arraysumme:start [26.01.2022 21:03] – [Rekursion! Teile und herrsche...] sbel
+++ faecher:informatik:oberstufe:algorithmen:teile_und_herrsche:arraysumme:start [Unknown date] (aktuell) – gelöscht - Externe Bearbeitung (Unknown date) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-====== 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.
-----
-{{:aufgabe.png?nolink  |}}
-=== (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?
-++++ Antwort: | Wenn das Array die Länge 0 oder 1 hat, ist das Ergebnis sehr einfach zu ermitteln: Im Falle des leeren Arrays ist die Summe 0, im Fall des Arrays mit der Länge 1 ist die Summe der Wert des einzigen Array-Elements.
-++++
-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?
-{{ :faecher:informatik:oberstufe:algorithmen:teile_und_herrsche:arraysumme:arraysum01.drawio.png |}}
-++++ Antwort: |
-Zum Beispiel so:
-{{ :faecher:informatik:oberstufe:algorithmen:teile_und_herrsche:arraysumme:transformed.drawio.png |}}
-++++
-Die Funktionsweise kann man also dem folgenden Flussdiagramm, entnehmen:
-{{ :faecher:informatik:oberstufe:algorithmen:teile_und_herrsche:arraysumme:flow.drawio.png |}}
-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.
-----
-{{:aufgabe.png?nolink  |}}
-=== (A2) ===
-Implementiere die rekursive Methode ''sumRekursiv'' im Bluej-Projekt nach den Erläuterungen dieser Wiki-Seite.((Hinweis: Ein Element aus einer Array List entfernen kann man mit der Methode ''arrayList.remove(0);''))
-----
-{{:aufgabe.png?nolink  |}}
-=== (A3) ===
-Schreibe eine rekursive Methode zum Ermitteln der größten Zahl im Array.