MINT lernen

Abituraufgaben: Algorithmen analysieren

Zwei Abituraufgaben zum Analysieren, Testen und Widerlegen von Algorithmen — mit Hinweisen und Erwartungshorizont.

Dein Fortschritt:
0 / 0 Aufgaben
1

Die Kundenkarte

AFB I–II

Ein Supermarkt vergibt auf seiner Kundenkarte Bonuspunkte. Am Monatsende wertet ein Programm die n Einkäufe eines Kunden aus; die Beträge werden in ganzen Euro eingegeben. Das Programm arbeitet nach folgendem Algorithmus:

Pseudocode
Eingabe: n
punkte ← 0
groesster ← 0
für i von 1 bis n wiederhole
  Eingabe: betrag
  punkte ← punkte + betrag
  wenn betrag > groesster dann
    groesster ← betrag
  ende wenn
ende für
wenn groesster ≥ 50 dann
  punkte ← punkte + 10
ende wenn
Ausgabe: punkte
  1. Bestimmen Sie die Ausgabe für vier Einkäufe mit den Beträgen 12 €, 55 €, 30 € und 8 €.
  2. Erläutern Sie die Rollen der Variablen i, punkte und groesster und formulieren Sie in einem Satz, welche Bonusregel der Algorithmus umsetzt.
  3. Weisen Sie nach, dass der Algorithmus für jede zulässige Eingabe (n ≥ 0) terminiert.

Hinweise

Hinweis zu Aufgabe a)
Führe die Werte von punkte und groesster nach jedem Einkauf mit. Die Verzweigung nach der Schleife wird nur einmal geprüft.
Hinweis zu Aufgabe b)
Unterscheide Zähler, Akkumulator und Merker. Was bekommt man pro Euro, und wann gibt es einen Extrabonus?
Hinweis zu Aufgabe c)
Wie viele Durchläufe hat eine Zählschleife „von 1 bis n“? Welche Anweisungen stehen außerhalb der Schleife?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

punkte: 12 → 67 → 97 → 105; groesster: 12 → 55 → 55 → 55. Nach der Schleife: 55 ≥ 50, also punkte ← 115. Ausgabe: 115.

Erwartungshorizont zu Aufgabe b)

i ist die Schleifenvariable und zählt die Einkäufe von 1 bis n (Zähler). punkte ist ein Akkumulator, der die Beträge aufsummiert. groesster ist ein Merker für den bisher größten Einzelbetrag.

Regel: Der Kunde erhält pro Euro Umsatz einen Punkt und einmalig 10 Extrapunkte, wenn mindestens ein Einkauf 50 € oder mehr betrug.

Erwartungshorizont zu Aufgabe c)

Die einzige Schleife ist eine Zählschleife von 1 bis n: i wird in jedem Durchlauf um 1 erhöht und im Rumpf nicht verändert, sie läuft also genau n-mal (für n = 0 gar nicht). Alle übrigen Anweisungen stehen außerhalb der Schleife und werden höchstens einmal ausgeführt. Damit endet der Algorithmus nach endlich vielen Schritten.

2

Die ganzzahlige Wurzel

AFB II–III

Für ein Geometrie-Lernspiel wird die Kantenlänge des größten Quadrats gebraucht, das sich aus n gleich großen quadratischen Fliesen legen lässt — also die abgerundete Quadratwurzel von n (z. B. 3 für n = 10, weil 3 · 3 ≤ 10 < 4 · 4). Eine Schülerin legt folgenden Algorithmus vor und behauptet: „Er gibt für jede natürliche Zahl n die abgerundete Quadratwurzel aus.“

Pseudocode
Eingabe: n
w ← 0
solange w · w < n wiederhole
  w ← w + 1
ende solange
Ausgabe: w
  1. Untersuchen Sie den Algorithmus für die Eingaben n = 0, n = 9, n = 10 und n = 16. Geben Sie jeweils die Anzahl der Schleifendurchläufe und die Ausgabe an.
  2. Widerlegen Sie die Behauptung der Schülerin und ändern Sie den Algorithmus so, dass er korrekt arbeitet.
  3. Schätzen Sie ab, wie viele Schleifendurchläufe Ihr korrigierter Algorithmus für n = 1 000 000 und für n = 10¹² benötigt, und beurteilen Sie damit, ob das Verfahren auch für große Zahlen praktikabel ist.

Hinweise

Hinweis zu Aufgabe a)
Lege eine kleine Tabelle mit den Spalten w und w · w an und prüfe vor jedem Durchlauf die Bedingung.
Hinweis zu Aufgabe b)
Ein einziges Gegenbeispiel genügt. Überlege dann: Soll w erhöht werden, solange w · w kleiner als n ist — oder solange das nächste Quadrat noch passt?
Hinweis zu Aufgabe c)
Die Schleife endet, wenn w die Wurzel erreicht. Wie groß ist √n für die beiden Zahlen?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

n = 0: 0 · 0 < 0 ist falsch → 0 Durchläufe, Ausgabe 0. · n = 9: w = 0, 1, 2 erfüllen w · w < 9 → 3 Durchläufe, Ausgabe 3. · n = 10: w = 0, 1, 2, 3 (9 < 10) → 4 Durchläufe, Ausgabe 4. · n = 16: w = 0 bis 3 → 4 Durchläufe, Ausgabe 4.

Für Quadratzahlen stimmt die Ausgabe, für n = 10 nicht.

Erwartungshorizont zu Aufgabe b)

Gegenbeispiel n = 10: Ausgabe 4, aber 4 · 4 = 16 > 10; richtig wäre 3. Der Algorithmus liefert die aufgerundete Wurzel (kleinstes w mit w · w ≥ n). Damit ist die Behauptung widerlegt.

Pseudocode
Eingabe: n
w ← 0
solange (w + 1) · (w + 1) ≤ n wiederhole
  w ← w + 1
ende solange
Ausgabe: w

Jetzt wird nur erhöht, wenn auch das nächste Quadrat noch passt. Test: n = 10 → w = 3 (16 > 10 stoppt), n = 16 → 4, n = 0 → 0.

Erwartungshorizont zu Aufgabe c)

Die Schleife läuft ⌊√n⌋-mal: für n = 1 000 000 genau 1000 Durchläufe, für n = 10¹² genau 1 000 000 Durchläufe. Die Anzahl wächst also nur mit der Wurzel von n — eine Million einfache Rechenschritte schafft ein Rechner in Bruchteilen einer Sekunde. Deutlich schlechter wäre ein Verfahren, das alle Zahlen bis n durchprobiert (10¹² Durchläufe). Für sehr große Zahlen (z. B. mit 40 Stellen) wäre aber auch √n zu groß; dann bräuchte man schnellere Verfahren.