Der Pfandautomat
AFB I–IIEin Pfandautomat im Supermarkt nimmt Flaschen nacheinander an. Für eine Mehrwegflasche schreibt er 8 Cent gut, für eine Einwegflasche 25 Cent. Zu Beginn tippt die Kundin die Anzahl ihrer Flaschen ein; für jede Flasche erkennt ein Sensor, ob es eine Mehrwegflasche ist (mehrweg ist dann wahr). Der Automat arbeitet nach folgendem Algorithmus (Beträge in Cent):
Eingabe: anzahl betrag ← 0 i ← 1 solange i ≤ anzahl wiederhole Eingabe: mehrweg wenn mehrweg dann betrag ← betrag + 8 sonst betrag ← betrag + 25 ende wenn i ← i + 1 ende solange Ausgabe: betrag
- Erstellen Sie eine Tracetabelle für die Eingabe
anzahl = 3mit den Flaschen Mehrweg, Einweg, Mehrweg. - Bestimmen Sie für
anzahl = 6den kleinsten und den größten möglichen Pfandbetrag sowie einen allgemeinen Term für den Betrag bei m Mehrweg- und k Einwegflaschen. - Erklären Sie, welche Folgen es hätte, wenn die Anweisung
i ← i + 1versehentlich in den dann-Zweig der Verzweigung verschoben würde.
Hinweise
Hinweis zu Aufgabe a)
mehrweg und die Ausgabe an. Vergiss die letzte Prüfung nicht.Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
i dann noch erhöht — und was passiert mit der Schleifenbedingung, wenn nur Einwegflaschen kommen?Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| anzahl | betrag | i | i ≤ anzahl | mehrweg | Ausgabe |
|---|---|---|---|---|---|
| 3 | |||||
| 0 | |||||
| 1 | |||||
| wahr | |||||
| wahr | |||||
| 8 | |||||
| 2 | |||||
| wahr | |||||
| falsch | |||||
| 33 | |||||
| 3 | |||||
| wahr | |||||
| wahr | |||||
| 41 | |||||
| 4 | |||||
| falsch | |||||
| 41 |
Ausgabe: 41 Cent (8 + 25 + 8).
Erwartungshorizont zu Aufgabe b)
Kleinster Betrag: sechs Mehrwegflaschen, 6 · 8 = 48 Cent. Größter Betrag: sechs Einwegflaschen, 6 · 25 = 150 Cent. Allgemein ist die Ausgabe 8 · m + 25 · k mit m + k = anzahl, unabhängig von der Reihenfolge der Flaschen.
Erwartungshorizont zu Aufgabe c)
Dann würde i nur noch bei Mehrwegflaschen erhöht. Einwegflaschen würden zwar gutgeschrieben, aber nicht mitgezählt: Der Automat verlangt weitere Flaschen, obwohl die angegebene Anzahl schon erreicht ist. Kommen nur noch Einwegflaschen, bleibt i ≤ anzahl immer wahr — die Schleife terminiert nicht. Die Zählvariable muss deshalb unabhängig von der Verzweigung in jedem Durchlauf erhöht werden; in der Tracetabelle würde man sehen, dass die Spalte i nach einer Einwegflasche unverändert bleibt.
Die Frostwarnung
AFB II–IIIEine Wetterstation soll aus n nacheinander eingegebenen Temperaturmessungen (in °C) die tiefste Temperatur bestimmen. Liegt sie unter 0 °C, wird später eine Frostwarnung ausgelöst. Ein Praktikant hat folgenden Algorithmus entworfen:
Eingabe: n tief ← 0 i ← 1 solange i < n wiederhole Eingabe: t wenn t < tief dann tief ← t ende wenn i ← i + 1 ende solange Ausgabe: tief
- Untersuchen Sie den Algorithmus mithilfe einer Tracetabelle für
n = 3und die Messwerte 4, 2 und 7. - Überprüfen Sie die Korrektheit des Algorithmus. Benennen Sie alle Fehler und belegen Sie jeden mit Ihrer Tracetabelle oder einem eigenen Gegenbeispiel.
- Entwickeln Sie eine korrigierte Fassung und geben Sie zwei Testfälle an, von denen jeder genau einen der gefundenen Fehler im ursprünglichen Algorithmus aufdeckt.
Hinweise
Hinweis zu Aufgabe a)
t und die Bedingung der Verzweigung. Wie viele Messwerte werden überhaupt gelesen?Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
tief starten, wenn noch nichts gemessen ist? Ein Testfall für den Schleifenfehler muss so gewählt sein, dass der Startwert-Fehler das Ergebnis nicht überdeckt.Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| n | tief | i | i < n | t | t < tief | Ausgabe |
|---|---|---|---|---|---|---|
| 3 | ||||||
| 0 | ||||||
| 1 | ||||||
| wahr | ||||||
| 4 | ||||||
| falsch | ||||||
| 2 | ||||||
| wahr | ||||||
| 2 | ||||||
| falsch | ||||||
| 3 | ||||||
| falsch | ||||||
| 0 |
Ausgabe: 0. Gelesen werden nur die Werte 4 und 2; die dritte Messung 7 wird nie eingegeben.
Erwartungshorizont zu Aufgabe b)
Der Algorithmus ist nicht korrekt; erwartet wäre 2. Fehler 1 (Startwert): tief ← 0 ist kein Messwert. Sind alle Messungen positiv, ist keine kleiner als 0 und die Ausgabe 0 ist falsch — so in der Tabelle: 4 < 0 und 2 < 0 sind falsch. Das ist besonders ärgerlich, weil 0 °C fälschlich nach Frost klingt. Fehler 2 (Schleifenbedingung): Mit i < n und Start bei 1 läuft die Schleife nur n − 1-mal; der letzte Messwert wird nie gelesen (in der Tabelle: nach i = 3 ist 3 < 3 falsch, die 7 fehlt). Gegenbeispiel: n = 3 mit 5, −1, −4 liefert −1 statt −4.
Erwartungshorizont zu Aufgabe c)
Eingabe: n Eingabe: t tief ← t i ← 2 solange i ≤ n wiederhole Eingabe: t wenn t < tief dann tief ← t ende wenn i ← i + 1 ende solange Ausgabe: tief
Der erste Messwert initialisiert tief; danach werden die übrigen n − 1 Werte mit i von 2 bis n gelesen. Testfall für Fehler 1: n = 3 mit 4, 2, 7 — erwartet 2, ursprünglich 0. Testfall für Fehler 2: n = 3 mit 5, −1, −4 — erwartet −4, ursprünglich −1 (hier stört der Startwert 0 nicht, weil negative Werte vorkommen).