Strategie Teile und herrsche: Übungen – Informatik Leistungskurs

Dein Fortschritt:

0 / 0 Aufgaben

Übungsaufgaben

Dreißig Ü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.

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.

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.

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.