MINT üben

Algorithmen analysieren

Dreißig Übungen zum Analysieren von Algorithmen: Variablenrollen, Durchläufe, Terminierung und Korrektheit.

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
Rollen in der Schritte-App
AFB I

Eine App wertet die Schritte einer Woche aus:

Pseudocode
gesamt ← 0
ziele ← 0
beste ← 0
für tag von 1 bis 7 wiederhole
  Eingabe: schritte
  gesamt ← gesamt + schritte
  wenn schritte ≥ 10000 dann
    ziele ← ziele + 1
  ende wenn
  wenn schritte > beste dann
    beste ← schritte
  ende wenn
ende für
Ausgabe: gesamt, ziele, beste

Beschreibe die Rolle jeder Variablen, indem du in jedem Menü den passenden Eintrag wählst.

Wähle in jedem Menü den passenden Eintrag und prüfe dann.

Die Variable gesamt ist ein .

ziele ist ein und beste ist ein .

Die Schleife läuft . Erreicht ein Tag das Ziel von 10 000 Schritten, wächst um 1.

gesamt sammelt wechselnde Beträge auf (Akkumulator), ziele wächst immer nur um 1 (Zähler) und beste hält den bisher größten Wert fest (Merker). Die Zählschleife von 1 bis 7 läuft siebenmal.
Frage dich bei jeder Variablen: Wächst sie immer um 1, sammelt sie wechselnde Beträge oder hält sie den bisher besten Wert fest?
gesamt addiert in jedem Durchlauf einen anderen Betrag (schritte), ziele nur eine 1 und beste wird nur bei einem neuen Bestwert überschrieben.
A2
Die Reihenfolge der Schritte
AFB II

Dieser Algorithmus läuft mit k = 3 als Startwert:

Pseudocode
k ← 3
solange k > 0 wiederhole
  Ausgabe: k
  k ← k − 2
ende solange
Ausgabe: k

Erkläre den Ablauf: Ziehe die acht Ereignisse in der Reihenfolge, in der sie nach der Zeile k ← 3 eintreten, auf den Zeitstrahl.

Ziehe jede Karte am Griff ⠿ auf den Zeitstrahl — sie rastet an der nächsten Marke ein. Ohne Ziehen: Karte antippen, dann auf den Zeitstrahl tippen. Tastatur: Enter nimmt die Karte, ←/→ (oder ↑/↓) springt von Marke zu Marke, Enter setzt, Entf legt zurück.
Geprüft wird vor jedem Durchlauf: 3 > 0 und 1 > 0 sind wahr, dann folgen Ausgabe und Änderung von k. Nach dem zweiten Durchlauf ist k = −1, die dritte Prüfung ist falsch und die letzte Ausgabe zeigt −1 — nicht 1.
Die Prüfung der Bedingung steht immer vor dem Rumpf. Beginne mit der ersten Prüfung nach dem Startwert.
Im Rumpf kommt erst die Ausgabe, dann die Änderung von k. Nach der Änderung folgt wieder die Prüfung — die letzte Ausgabe steht erst nach der Schleife.
A3
Von Worten zur Rechenkette
AFB IIMix

Ein Algorithmus ist in Worten beschrieben:

  1. Lies die Zahl x ein.
  2. Verdopple x und speichere das Ergebnis in y.
  3. Ziehe von y die Zahl 3 ab.
  4. Gib y geteilt durch 5 aus.

Stelle die Rechenkette auf, die als Verarbeitung aus der Eingabe die Ausgabe macht. Zwei Blöcke gehören nicht dazu.

Stecke die Rechenmaschine zusammen: Klick auf einen Block hängt ihn hinten an die Kette, Klick auf einen Kettenblock nimmt ihn wieder heraus. Der Probelauf zeigt unter jedem Block den Zwischenwert. Tastatur: Enter wie Klick, in der Kette Shift+←/→ verschiebt, Entf entfernt.
Eingabe, Verarbeitung, Ausgabe: Aus x wird zuerst 2 · x, dann 2 · x − 3 und zuletzt (2 · x − 3) : 5. Für x = 4 ergibt das 1, für x = 9 ergibt es 3 und für x = 14 ergibt es 5.
Setze die Schritte der Beschreibung in genau der genannten Reihenfolge als Blöcke zusammen.
„Verdopple“ ist · 2, „ziehe 3 ab“ ist − 3 und „geteilt durch 5“ ist : 5. Die Blöcke + 3 und · 5 werden nicht gebraucht.