Zehn Übungen zur Strategie Teile und herrsche — vom Zuordnen der drei Schritte bis zum eigenen Entwurf.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn du nicht weiterkommst, helfen die gestuften Tipps.
A1
Was Teile und herrsche ausmacht
AFB I
Ein Verfahren soll nach der Strategie Teile und herrsche arbeiten. Gib alle Aussagen an, die dafür zutreffen.
Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Auswahl prüfen“.
Teilen, rekursiv lösen, zusammenführen — plus Basisfall. Bei ungerader Länge sind die Hälften verschieden groß, das schadet nicht. Schneller wird es nur, wenn Teilen und Zusammenführen Arbeit sparen: Das rekursive Maximum braucht genau so viele Vergleiche wie die Schleife. Die Grenzen links und rechts ersparen das Kopieren.
Ansatz: Denke an die drei Schritte und an den Fall, in dem die Rekursion endet.
Weiter: Zwei Aussagen übertreiben („immer“), eine beschreibt unnötigen Speicheraufwand.
A2
Welcher Schritt ist das?
AFB I
Die Karten stammen aus maximum, Mergesort, Quicksort und der binären Suche. Ordne jede Karte dem Schritt der Strategie zu, zu dem sie gehört.
Ziehe jede Karte in den passenden Korb — oder wähle sie mit Enter aus und drücke dann die Ziffer des Korbs (0 legt sie zurück).
1Teilen
2Herrschen
3Zusammenführen
4Basisfall
Quicksort steckt seine Arbeit ins Teilen (zerlege), Mergesort ins Zusammenführen (mische). „Herrschen“ ist immer ein rekursiver Aufruf auf einem kleineren Teil — die binäre Suche macht genau einen davon.
Ansatz: Frage bei jeder Karte: Entsteht hier ein Teilproblem, wird eines gelöst, werden Lösungen verbunden — oder endet die Rekursion?
Weiter:zerlege bereitet die Teile erst vor — gehört also zum Teilen.
A3
Stimmt's? — Maximum von fünf Werten
AFB I
Gegeben ist int[] b = {8, 3, 14, 6, 11}; und die Methode maximum(a, links, rechts) aus dem Unterricht. Wende sie gedanklich auf maximum(b, 0, 4) an und entscheide bei jeder Aussage, ob sie stimmt.
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Aussage 1 von 5
Jede Zusammenführung verringert die Zahl der offenen Teillösungen um eins: aus 5 Basisfällen wird mit 4 Vergleichen eine Lösung.
Ansatz: Berechne zuerst mitte mit ganzzahliger Division.
Weiter: Zähle die Vergleiche: jede Zusammenführung vergleicht genau zwei Teilergebnisse.
A4
Aufrufe verfolgen
AFB II
Gegeben ist int[] c = {5, 12, 7, 9};. Stelle die Aufrufe von maximum(c, 0, 3) in der Reihenfolge dar, in der sie beginnen, und trage jeweils den Rückgabewert ein.
Fülle alle Felder aus und prüfe dann. Enter in einem Feld prüft ebenfalls.
Nr.
Aufruf
Rückgabewert
1
maximum(c, 0, 3)
2
maximum(c, 0, 1)
3
maximum(c, 0, 0)
4
maximum(c, 1, 1)
5
maximum(c, , )
6
maximum(c, 2, 2)
7
maximum(c, 3, 3)
Der linke Teilbaum wird vollständig abgearbeitet, bevor der rechte beginnt: Aufruf 5 startet erst, nachdem Aufruf 2 mit 12 zurückgekehrt ist. Insgesamt 7 = 2 · 4 − 1 Aufrufe.
Ansatz: Ein Aufruf beginnt erst, wenn der vorige rekursive Aufruf in derselben Methode fertig ist.
Weiter: Aufruf 5 ist der zweite rekursive Aufruf von Aufruf 1: maximum(c, mitte + 1, 3).
A5
Vergleiche durch Einsetzen
AFB II
Für das rekursive Maximum gilt \(V(n) = 2\cdot V\!\left(\frac{n}{2}\right) + 1\) mit \(V(1) = 0\). Berechne die Werte Schritt für Schritt.
Rechne die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
\(V(2) =\)Vergleiche
\(V(4) =\)Vergleiche
\(V(8) =\)Vergleiche
\(V(1024) =\)Vergleiche
Einsetzen zeigt das Muster \(V(n) = n - 1\): \(V(2) = 2\cdot0 + 1\), \(V(4) = 2\cdot1 + 1\), \(V(8) = 2\cdot3 + 1\). Für 1024 braucht man die Zwischenwerte nicht mehr.
Ansatz: Setze immer den vorher berechneten Wert ein.
Weiter: Vergleiche die Ergebnisse mit n — welcher Zusammenhang fällt auf?
A6
Wo steckt die Arbeit?
AFB IIMix
Ordne jedes Verfahren in das Schema Teile und herrsche ein, indem du es mit der passenden Beschreibung verbindest.
Klicke links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Die lineare Suche aus Kapitel 2 teilt nichts — sie verkleinert das Problem nur um ein Element. Mergesort und Quicksort sind Gegenstücke: Der eine arbeitet beim Zusammenführen, der andere beim Teilen.
Ansatz: Frage bei jedem Verfahren: Wie viele rekursive Aufrufe gibt es, und was passiert danach?
Weiter: Die binäre Suche verwirft eine Hälfte ganz.
A7
Die fehlerhafte Summe
AFB II
Ein Mitschüler soll die Summe einer Reihung nach Teile und herrsche berechnen. Überprüfe seine Methode und markiere die zwei falschen Zeilen.
In diesem Text stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.
Mit return 0 wäre jede Summe 0. Die Bereiche müssen lückenlos aneinanderstoßen: links … mitte und mitte + 1 … rechts. Mit mitte − 1 ruft z. B. summe(a, 0, 1) den leeren Bereich summe(a, 0, −1) auf, der den Basisfall nie erreicht — StackOverflowError.
Ansatz: Prüfe den Basisfall mit einer Reihung aus einem Element.
Weiter: Schreibe für links = 0, rechts = 3 die beiden Teilbereiche auf. Fehlt ein Index?
A8
Wie viele Aufrufe?
AFB IIITrick
Das rekursive maximum wird für eine Reihung mit 100 Elementen aufgerufen. Bestimme die Gesamtzahl der Aufrufe von maximum einschließlich des ersten.
Überlege selbst und trage das Ergebnis ein — Enter prüft direkt.
Jede Zusammenführung gehört zu einem Aufruf mit mindestens zwei Elementen — das sind \(n - 1 = 99\). Dazu kommen die \(n = 100\) Basisfall-Aufrufe: \(99 + 100 = 199 = 2n - 1\). Wer 99 antwortet, hat nur die Vergleiche gezählt, wer 100 antwortet, nur die Basisfälle.
Ansatz: Unterscheide Aufrufe, die teilen, und Aufrufe, die ein einzelnes Element zurückgeben.
Weiter: Wie viele Basisfälle gibt es, und wie viele Zusammenführungen?
A9
Gerade Zahlen zählen
AFB III
Eine Methode soll nach Teile und herrsche zählen, wie viele gerade Zahlen im Bereich links … rechts stehen. Entwirf die Methode, indem du die Zeilen in die richtige Reihenfolge bringst.
Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1static int zaehleGerade(int[] a, int links, int rechts) {
2if (links == rechts) {
3if (a[links] % 2 == 0) return 1;
4return 0;
5} // Ende Basisfall
6int mitte = (links + rechts) / 2;
7return zaehleGerade(a, links, mitte) + zaehleGerade(a, mitte + 1, rechts);
8} // Ende der Methode
Basisfall zuerst: Ein Element zählt 1 oder 0. Danach teilen und die beiden Teilanzahlen addieren — das Zusammenführen ist hier eine Addition. Für {4, 7, 10, 3, 8} liefert die Methode 3.
Ansatz: Wie beim Maximum: Basisfall, Mitte, zwei rekursive Aufrufe.
Weiter:return 0; gehört noch in den Basisfall — vor dessen schließende Klammer.
A10
Wie viele Vergleiche?
AFB IIIMix
Beurteile für jedes Verfahren auf einer Reihung mit n Elementen, wie viele Vergleiche zwischen Elementen es im ungünstigsten Fall ausführt.
Wähle für jede Zeile eine Stufe: 1 = keine, 2 = etwa log₂ n, 3 = n − 1, 4 = etwa n · log₂ n, 5 = n(n − 1)/2. Mit der Tastatur: Tab zur Zeile, ←/→ zwischen den Stufen, Enter setzt.
1 = keine5 = n(n − 1)/2
Summe aller Elemente nach Teile und herrsche
Binäre Suche in einer sortierten Reihung
Maximum nach Teile und herrsche
Maximum mit einer Schleife
Mergesort
Selectionsort
Die Summe addiert nur, sie vergleicht keine Elemente. Maximum rekursiv und per Schleife sind gleich teuer. Einen echten Gewinn bringt Teile und herrsche erst beim Sortieren: Mergesort liegt bei \(n\log_2 n\), Selectionsort bei \(\frac{n(n-1)}{2}\).
Ansatz: Ein Vergleich ist eine Frage wie „a[i] < a[j]?“ — Rechnen zählt nicht.
Weiter: Das Maximum braucht in jeder Variante für jedes Element außer einem genau einen Vergleich.
