MINT lernen

Abituraufgaben: Zeichenketten verarbeiten

Zwei Abituraufgaben zu Zeichenketten — mit Hinweisen und Erwartungshorizont.

Dein Fortschritt:
0 / 0 Aufgaben
1

Benutzernamen für das Schulnetz

AFB I–II

Das Schulnetz erzeugt Benutzernamen automatisch aus den ersten drei Buchstaben des Nachnamens, den ersten zwei Buchstaben des Vornamens und den letzten zwei Ziffern des Geburtsjahrs; das Jahr liegt als Zeichenkette vor. Aus Lina Schneider, geboren 2009, wird so „SchLi09“. Ist ein Name bereits vergeben, wird eine Zahl angehängt: zuerst 2, dann 3 usw., bis ein freier Name gefunden ist.

Im Pseudocode liefert teil(s, a, b) die Teilzeichenkette von Position a bis vor Position b; die Operation vergeben(name) liefert wahr, wenn der Name schon existiert.

  1. Wenden Sie die Regel auf Tom Wagner (2008) und Marie Hoffmann (2010) an. Dabei seien „WagTo08“ und „WagTo082“ bereits vergeben.
  2. Stellen Sie den Algorithmus zur Erzeugung eines freien Benutzernamens als Struktogramm dar.
  3. Untersuchen Sie, was bei einem Nachnamen mit weniger als drei Buchstaben wie „Wu“ in Java und in Python geschieht, und geben Sie eine Korrektur an.

Hinweise

Hinweis zu Aufgabe a)
Zerlege jeden Namen einzeln und zähle die Positionen ab 0. Beim Jahr brauchst du die Positionen 2 und 3.
Hinweis zu Aufgabe b)
Welche Schritte stehen einmal am Anfang, welcher Schritt wird wiederholt — und unter welcher Bedingung?
Hinweis zu Aufgabe c)
Vergleiche "Wu".substring(0, 3) in Java mit "Wu"[0:3] in Python.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Tom Wagner: „Wag“ + „To“ + „08“ = „WagTo08“ ist vergeben, „WagTo082“ auch, also „WagTo083“. Marie Hoffmann: „Hof“ + „Ma“ + „10“ = „HofMa10“.

Erwartungshorizont zu Aufgabe b)

Die Zahl wird immer an basis angehängt, nicht an den vorigen Namen — sonst entstünde „WagTo0823“.

Erwartungshorizont zu Aufgabe c)

Java: "Wu".substring(0, 3) löst eine StringIndexOutOfBoundsException aus, das Programm bricht ab. Python: "Wu"[0:3] liefert einfach „Wu“, weil Slices an der Grenze abgeschnitten werden — es entsteht „WuLi09“. Korrektur für Java (und Pseudocode): nur so viele Zeichen nehmen, wie vorhanden sind.

Java
int n = Math.min(3, nachname.length());
String teil1 = nachname.substring(0, n);

Gleichwertig: wenn länge(nachname) < 3 dann teil1 ← nachname sonst teil1 ← teil(nachname, 0, 3). Dasselbe gilt für Vornamen mit nur einem Buchstaben.

2

Lauflängenkodierung

AFB II–III

Einfache Bildformate speichern lange Folgen gleicher Pixel platzsparend: Statt „WWWW“ wird „4W“ gespeichert. Die folgende Operation kodiert eine Zeichenkette auf diese Weise. Dabei wird die Zahl anzahl beim Verketten als Ziffernfolge angehängt.

Pseudocode
Operation kodiere(s)
  ergebnis ← ""
  i ← 0
  solange i < länge(s) wiederhole
    zeichen ← s[i]
    anzahl ← 1
    solange i + anzahl < länge(s) und s[i + anzahl] = zeichen wiederhole
      anzahl ← anzahl + 1
    ende solange
    ergebnis ← ergebnis + anzahl + zeichen
    i ← i + anzahl
  ende solange
  zurück ergebnis
  1. Analysieren Sie die Operation für den Aufruf kodiere("WWWSSOOOOO"): Geben Sie das Ergebnis an und erklären Sie die Rolle von i ← i + anzahl.
  2. Erweitern Sie die Operation so, dass die Anzahl nur dann geschrieben wird, wenn sie größer als 1 ist. Aus „WWWSOO“ soll „3WS2O“ werden.
  3. Vergleichen Sie die Längen von Original und Kodierung für „ABCDEF“ und für zwölfmal „A“. Beurteilen Sie außerdem, ob sich Zeichenketten mit Ziffern wie „112“ eindeutig kodieren lassen.

Hinweise

Hinweis zu Aufgabe a)
Lege eine Tracetabelle mit i, zeichen, anzahl und ergebnis an — die äußere Schleife läuft einmal pro Block gleicher Zeichen.
Hinweis zu Aufgabe b)
Die Änderung betrifft nur die Zeile, in der ergebnis verlängert wird.
Hinweis zu Aufgabe c)
Kodiere beide Beispiele und zähle. Bei „112“: Wie würde jemand das Ergebnis wieder entschlüsseln?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
izeichenanzahlergebnis
0W33W
3S23W2S
5O53W2S5O

Ergebnis: „3W2S5O“. Die äußere Schleife läuft dreimal, einmal pro Block. i ← i + anzahl springt über den gerade gezählten Block hinweg zum ersten Zeichen des nächsten Blocks; mit i ← i + 1 würde jeder Block mehrfach gezählt (z. B. „3W2W1W…“).

Erwartungshorizont zu Aufgabe b)
Pseudocode
wenn anzahl > 1 dann
  ergebnis ← ergebnis + anzahl + zeichen
sonst
  ergebnis ← ergebnis + zeichen
ende wenn
Python
if anzahl > 1:
    ergebnis = ergebnis + str(anzahl) + zeichen
else:
    ergebnis = ergebnis + zeichen

Diese Verzweigung ersetzt die Zeile ergebnis ← ergebnis + anzahl + zeichen; alles andere bleibt gleich.

Erwartungshorizont zu Aufgabe c)

„ABCDEF“ (6 Zeichen) wird zu „1A1B1C1D1E1F“ (12 Zeichen) — doppelt so lang. Zwölfmal „A“ wird zu „12A“ (3 statt 12 Zeichen). Die Kodierung lohnt sich also nur bei langen Wiederholungen, wie sie in Grafiken mit großen einfarbigen Flächen vorkommen; bei abwechslungsreichem Text vergrößert sie die Daten.

„112“ wird zu „2112“. Beim Entschlüsseln ist aber unklar, wo eine Anzahl endet: „2112“ kann „2 × 1, 1 × 2“ = „112“ bedeuten, aber auch „211 × 2“. Mit Ziffern im Text ist die Kodierung also nicht eindeutig; man bräuchte ein Trennzeichen oder eine feste Stellenzahl für die Anzahl.