Algorithmen mit Stapeln: Übungen – Informatik Leistungskurs

Dein Fortschritt:

0 / 0 Aufgaben

Übungsaufgaben

Dreißig interaktive Übungen zum Klicken, Ziehen und Knobeln — von AFB I bis AFB III. Jede Übung gibt dir sofort Rückmeldung.

Welcher Wert liegt oben?

AFB I

Ein Stapel ist anfangs leer. Wende push, pop und top an und setze zwischen die beiden Angaben das passende Zeichen.

Setze zwischen die beiden Angaben das passende Zeichen: Klick schaltet ? → < → = → > weiter. Mit der Tastatur: Tab zum Feld, dann <, = oder >.

top() nach push(4), push(9), pop()top() nach push(4), push(9)

top() nach push(6), push(2), pop()top() nach push(6)

erstes pop() nach push(3), push(7), push(5)erstes pop() nach push(5), push(7), push(3)

letztes pop() nach push(1), push(2), push(3)erstes pop() nach push(1), push(2)

Summe aller pop-Werte nach push(2), push(5)Summe aller pop-Werte nach push(5), push(2)

Im ersten Fall liegt nach pop() die 4 oben, sonst die 9. Im zweiten bleibt in beiden Fällen die 6 liegen. Das erste pop() liefert immer den zuletzt gelegten Wert: 5 gegen 3. Das letzte pop() nach 1, 2, 3 liefert die 1, das erste nach 1, 2 die 2. Die Summe 7 hängt nicht von der Reihenfolge ab.

Zeichne den Stapel senkrecht und führe die Aufrufe der Reihe nach aus. Das oberste Element ist das zuletzt gelegte.

pop() liefert immer den obersten Wert und nimmt ihn weg; top() liefert ihn nur. Bei einer Summe über alle Werte spielt die Reihenfolge keine Rolle.

Je mehr, desto …

AFB III

Formuliere vier Zusammenhänge zu Stapel-Algorithmen: Stelle die Wörter in jedem Je-desto-Satz so ein, dass er stimmt.

Klicke auf die farbig hinterlegten Wörter: Jeder Klick schaltet zur nächsten Möglichkeit weiter. Stelle jeden Satz so ein, dass er stimmt. Tastatur: Tab zum Wort, Enter/Leertaste oder ↑/↓ schaltet um.

Je mehr Elemente ein Stapel enthält, desto Durchläufe braucht die Schleife zum Umladen.

Je früher ein Element auf den Stapel gelegt wurde, desto liefert pop() es zurück.

Je tiefer die Klammern eines Ausdrucks ineinander verschachtelt sind, desto wird der Stapel bei der Prüfung.

Je öffnende Klammern am Ende noch im Stapel liegen, desto schließende Klammern fehlen dem Ausdruck.

Jedes Element braucht einen Durchlauf zum Umladen. Das zuerst gelegte Element liegt ganz unten und kommt zuletzt heraus. Jede weitere Verschachtelungsebene legt eine Klammer mehr auf den Stapel. Was am Ende noch im Stapel liegt, ist genau das, was nie geschlossen wurde: Mehr offene Klammern heißen mehr fehlende, weniger heißen weniger.

Überlege bei jedem Satz an einem kleinen Beispiel mit zwei und mit vier Elementen, in welche Richtung sich die zweite Größe bewegt.

Beim letzten Satz sind zwei Lösungen möglich: Beide Stellen müssen in dieselbe Richtung zeigen, denn offene und fehlende Klammern gehören zusammen.

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.