Dreißig Übungen zu Hilfsstapeln, Umladen und Klammerprüfung — von AFB I bis AFB III.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen in gemischter Reihenfolge — du klickst, ziehst, ordnest, rechnest und knobelst. Jede Übung gibt dir sofort eine Rückmeldung, und zu jeder Aufgabe gibt es zwei gestufte Tipps: Der erste zeigt die Richtung, der zweite den entscheidenden Schritt. Die Chips zeigen das Anforderungsniveau: AFB I heißt wiedergeben und direkt anwenden, AFB II selbst entscheiden und verknüpfen, AFB III begründen, beurteilen oder eine Falle durchschauen. Aufgaben mit dem Chip Mix verbinden Wissen aus früheren Unterkapiteln, bei Trick steckt eine Falle drin. Fährst du über ein unterstrichenes Arbeitswort, siehst du, was es genau von dir verlangt.
A1
Baustein und Zweck
AFB I
Ordne jedem Baustein eines Stapel-Algorithmus seinen Zweck zu: Verbinde beide Seiten.
Klicke links an und dann rechts das Passende — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Das Umdrehen entsteht durch push und pop, das Durchsehen durch Umladen. Zurückladen stellt den Stapel wieder her, ein Zähler liefert die Anzahl, und ein nicht leerer Stapel am Ende verrät eine offene Klammer.
Frage dich bei jedem Baustein: Was soll am Ende anders oder bekannt sein, die Reihenfolge, der Inhalt, eine Zahl oder ein Fehler?
Das Zurücklegen stellt etwas wieder her, ein Zähler liefert eine Zahl, und der Rest im Stapel am Ende zeigt, dass etwas offen geblieben ist.
A2
Der Hilfsstapel füllt sich
AFB II
Ein Lager führt seine 24 Kisten auf einem Stapel s. Eine Methode lädt sie nacheinander auf den leeren Hilfsstapel h um und zählt dabei mit:
int n = 0;
while (!s.isEmpty()) {
h.push(s.pop());
n++;
}
Ermittle mit dem Regler jeweils die kleinste Zahl k an Durchläufen, für die die Zielzeile erfüllt ist. Die Zahl der Durchläufe stellst du am Regler ein.
Verschiebe den Regler (ziehen oder auf die Skala tippen) bzw. nutze die Knöpfe − und +; die Werte darüber laufen live mit. Tastatur: Tab zum Regler, ←/→ ein Schritt, Bild↑/Bild↓ zehn Schritte, Pos1/Ende Anfang/Ende, Enter prüft.
Pro Durchlauf wandert eine Kiste von s nach h: Nach k Durchläufen liegen 24 − k Kisten in s und k in h. Bei k = 12 sind es 12 zu 12, erst k = 13 bringt mehr Kisten nach h. Jeder Durchlauf ruft pop und push je einmal auf, also 2k Aufrufe: 28 bei k = 14, 30 bei k = 15.
Beobachte beim Verschieben des Reglers, wie sich die Zahl der Kisten in s und in h ändert.
Pro Durchlauf gibt es einen Aufruf von pop und einen von push, nach k Durchläufen also 2k Aufrufe. Vergleiche das mit 30.
A3
Größten Kassenbon finden
AFB II
Eine Kasse legt die Beträge ihrer Kassenbons (in Cent, ganze Zahlen) auf einem Stapel s ab. Die Methode soll den größten Betrag liefern und s danach unverändert lassen. Der leere Hilfsstapel h ist bereits angelegt.
Untersuche den Quelltext: Welche Zeilen sind falsch?
In diesem Heft stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.
Die erste Schleife sucht das Maximum und lädt s auf h um, die zweite lädt zurück. Zwei Fehler: Der Vergleich muss auf „größer“ prüfen, und beim Zurückladen muss pop() das Element entnehmen — mit top() bliebe h für immer gefüllt.
Teste jede Schleife einzeln: Endet sie, und was liegt danach im jeweiligen Stapel? Prüfe außerdem, ob der Vergleich wirklich das Größte sucht.
Beim Maximum wird ersetzt, wenn der neue Wert größer ist. Zum Zurückladen muss das Element wirklich aus h genommen werden.
