Aufgabe Vorschlag B3 - Aufgabe 6 · Abitur Hessen Informatik GK 2021
Thema: Sortieren, Suchen und Laufzeit · Aus der Prüfung GK (2021)
Aufgabenstellung
Gutscheincodes
In vielen Online-Shops ist es möglich, durch die Eingabe von Gutscheincodes Rabatte zu erhalten. Um die Gültigkeit leicht überprüfen zu können, sind Gutscheincodes nach bestimmten Mustern aufgebaut. In Material 1 ist das Zustandsdiagramm eines Akzeptors gegeben, der gültige Gutscheincodes des Online-Shops InfoTools erkennt.
Material 1
Endlicher Automat für Gutschein-Codes
Um das Verfahren sicherer gegen Fehleingaben zu machen, wird der Algorithmus aus Material 3 verwendet. Dabei wird ein Gutscheincode ohne die Bindestriche und die Prüfziffer in ein Feld von Zeichen, beginnend beim Index 1, kopiert.
Material 3: Algorithmus zu Aufgabe 6
6.1
Bestimmen Sie die Anzahl der Rechenoperationen, die zur Berechnung der Prüfziffer im Gutscheincode AB-12-7 notwendig sind. [3 BE]
6.2
Begründen Sie, dass der Algorithmus quadratisches Laufzeitverhalten bezüglich der Länge des Feldes hat. [3 BE]
6.3
Erläutern Sie, warum der angegebene Algorithmus nicht alle Fehleingaben, die durch das Vertauschen der ersten beiden Zeichen entstehen, erkennen kann. Geben Sie ein Beispiel an, bei dem diese Vertauschung nicht erkannt wird. [3 BE]
Lösung
Nach den offiziellen Korrekturhinweisen
6.1 Bestimmen Sie die Anzahl der Rechenoperationen, die zur Berechnung der Prüfziffer im Gutscheincode AB-12-7 notwendig sind.
Lösung: 21
6.2 Begründen Sie, dass der Algorithmus quadratisches Laufzeitverhalten bezüglich der Länge n des Feldes hat.
Lösung: Der Algorithmus enthält eine geschachtelte Schleife, bei der die äußere Schleife -mal durchlaufen wird. Die Anzahl der Durchläufe der inneren Schleife hängt auch von ab. Sie beginnt mit und wird bei jedem weiteren Durchlauf der äußeren Schleife um 1 reduziert. Im Schnitt sind dies Durchläufe. Somit hat der Algorithmus eine quadratische Laufzeit in .
6.3 Erläutern Sie, warum der angegebene Algorithmus nicht alle Fehleingaben, die durch das Vertauschen der ersten beiden Zeichen entstehen, erkennen kann. Geben Sie ein Beispiel an, bei dem diese Vertauschung nicht erkannt wird.
Lösung: Bei der Berechnung der Prüfziffer wird der ASCII-Code des ersten Zeichens mit dem Faktor multipliziert, das zweite Zeichen mit dem Faktor . Die Differenz der beiden Gewichtsfaktoren beträgt somit genau 1. Die Prüfsumme unterscheidet sich bei einer Vertauschung also genau um die Differenz der beiden ASCII-Werte der vertauschten Zeichen. Haben diese Zeichen den Abstand 10 in der ASCII-Tabelle, führt dieser Unterschied bei der Berechnung der Prüfziffer (Modulo 10) zum selben Ergebnis. Beispiel: AK-12-8 und KA-12-8.
Die ausführliche Erklärung Schritt für Schritt (mit KI) gibt es mit Premium. Premium
Löse sie direkt hier: automatische Korrektur, Hinweise und Lösung Schritt für Schritt.
‹ Aufgabe Vorschlag B3 - Aufgabe 5 · GK 2021 · Aufgabe Vorschlag AJ - Aufgabe 2 · LK 2021 ›