MINT lernen

Abituraufgaben: ASCII und Zeichenvergleich

Zwei Abituraufgaben zu ASCII-Werten und lexikographischem Vergleich — mit Hinweisen und Erwartungshorizont.

Dein Fortschritt:
0 / 0 Aufgaben
1

Die Klassenliste

AFB I–II

Eine Schulverwaltungssoftware sortiert Namen mit dem lexikographischen Vergleich compareTo nach ASCII-Werten. In einer Kursliste stehen die Nachnamen

Weber, van Dijk, Adams, Ozturk, de Boer, Wagner, Adam.

Die Lehrkraft wundert sich, dass „de Boer“ und „van Dijk“ ganz am Ende der sortierten Liste stehen.

  1. Bestimmen Sie die Reihenfolge, in der die Software die sieben Namen ausgibt.
  2. Begründen Sie mithilfe der ASCII-Werte, warum „Adam“ vor „Adams“, „Wagner“ vor „Weber“ und „Weber“ vor „de Boer“ steht.
  3. Entwickeln Sie eine Operation vorher(a, b), die wahr liefert, wenn a ohne Rücksicht auf Groß- und Kleinschreibung vor b steht. Verwenden Sie dafür nur ASCII-Werte, keine fertigen Umwandlungsfunktionen.

Hinweise

Hinweis zu Aufgabe a)
Großbuchstaben haben die Werte 65 bis 90, Kleinbuchstaben 97 bis 122. Vergleiche zuerst nur die Anfangsbuchstaben.
Hinweis zu Aufgabe b)
Suche jeweils die erste Position, an der sich die beiden Namen unterscheiden — oder stelle fest, dass es keine gibt.
Hinweis zu Aufgabe c)
Schreibe zuerst eine Hilfsoperation, die jeden Großbuchstaben in den passenden Kleinbuchstaben umwandelt, und vergleiche dann die Ergebnisse.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Adam, Adams, Ozturk, Wagner, Weber, de Boer, van Dijk. Alle Namen mit Großbuchstaben am Anfang (65–90) kommen vor denen mit Kleinbuchstaben (97–122).

Erwartungshorizont zu Aufgabe b)

„Adam“ ist Anfang von „Adams“; ist ein Wort Präfix des anderen, steht das kürzere vorn. „Wagner“ und „Weber“ unterscheiden sich zuerst an Position 1: 'a' (97) < 'e' (101). „Weber“ und „de Boer“ unterscheiden sich schon an Position 0: 'W' (87) < 'd' (100) — der Großbuchstabe gewinnt, obwohl d im Alphabet vor W steht.

Erwartungshorizont zu Aufgabe c)
Java
static String klein(String s) {
  String t = "";
  for (int i = 0; i < s.length(); i++) {
    char z = s.charAt(i);
    if (z >= 'A' && z <= 'Z') {
      z = (char) (z + 32);
    }
    t = t + z;
  }
  return t;
}

static boolean vorher(String a, String b) {
  return klein(a).compareTo(klein(b)) < 0;
}
Python
def klein(s):
    t = ""
    for z in s:
        if "A" <= z <= "Z":
            z = chr(ord(z) + 32)
        t = t + z
    return t

def vorher(a, b):
    return klein(a) < klein(b)

Damit ergibt sich die erwartete Reihenfolge Adam, Adams, de Boer, Ozturk, van Dijk, Wagner, Weber.

2

Geheimschrift nach Caesar

AFB II–III

Schon Julius Caesar verschlüsselte Nachrichten, indem er jeden Buchstaben um k Stellen im Alphabet verschob; nach „Z“ geht es bei „A“ weiter. Die folgende Operation verschlüsselt Großbuchstaben und lässt alle anderen Zeichen unverändert. ascii(z) liefert den ASCII-Wert eines Zeichens, zeichen(n) das Zeichen zum Wert n; mod ist der kleinste nichtnegative Rest.

Pseudocode
Operation verschluessele(text, k)
  geheim ← ""
  für i von 0 bis länge(text) − 1 wiederhole
    z ← text[i]
    wenn z ≥ "A" und z ≤ "Z" dann
      nr ← ascii(z) − 65
      nr ← (nr + k) mod 26
      geheim ← geheim + zeichen(nr + 65)
    sonst
      geheim ← geheim + z
    ende wenn
  ende für
  zurück geheim
  1. Erklären Sie die Arbeitsweise der Operation am Aufruf verschluessele("TAXI 7", 5) und geben Sie das Ergebnis an.
  2. Erstellen Sie eine Implementierung in Java oder Python, die zusätzlich Kleinbuchstaben verschiebt; Kleinbuchstaben sollen dabei klein bleiben.
  3. Überprüfen Sie die Behauptung: „In Java entschlüsselt man einen Geheimtext g einfach mit verschluessele(g, −k), wenn man die Operation eins zu eins mit % übersetzt.“

Hinweise

Hinweis zu Aufgabe a)
Verfolge die drei Zeilen im wenn-Zweig für X: Welcher Wert entsteht vor und nach mod?
Hinweis zu Aufgabe b)
Für Kleinbuchstaben braucht es einen zweiten Zweig mit derselben Rechnung, aber einer anderen Verschiebung als 65.
Hinweis zu Aufgabe c)
Probiere k = 5 und den Geheimbuchstaben „C“ aus — und denke daran, welches Vorzeichen Java-% bei negativen Zahlen hat.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Jeder Großbuchstabe wird zunächst auf seine Alphabetnummer 0 bis 25 abgebildet (ascii − 65), dann um k verschoben. mod 26 sorgt für den Umlauf, + 65 führt zurück in den ASCII-Bereich. Leerzeichen und Ziffer gehen in den sonst-Zweig.

zascii(z) − 65+ 5mod 26neu
T192424Y
A055F
X23282C
I81313N
␣, 7sonst-Zweig␣, 7

Ergebnis: „YFCN 7“.

Erwartungshorizont zu Aufgabe b)
Java
static String verschluessele(String text, int k) {
  String geheim = "";
  for (int i = 0; i < text.length(); i++) {
    char z = text.charAt(i);
    if (z >= 'A' && z <= 'Z') {
      z = (char) ((z - 65 + k) % 26 + 65);
    } else if (z >= 'a' && z <= 'z') {
      z = (char) ((z - 97 + k) % 26 + 97);
    }
    geheim = geheim + z;
  }
  return geheim;
}
Python
def verschluessele(text, k):
    geheim = ""
    for z in text:
        if "A" <= z <= "Z":
            z = chr((ord(z) - 65 + k) % 26 + 65)
        elif "a" <= z <= "z":
            z = chr((ord(z) - 97 + k) % 26 + 97)
        geheim = geheim + z
    return geheim

Die Java-Fassung setzt ein k von 0 bis 25 voraus (siehe c).

Erwartungshorizont zu Aufgabe c)

Im Pseudocode stimmt die Behauptung, weil mod immer einen Rest von 0 bis 25 liefert: Verschieben um −k macht die Verschiebung um k rückgängig. In Java ist sie falsch: % übernimmt das Vorzeichen des Dividenden. Beispiel k = 5, Geheimbuchstabe „C“: 2 − 5 = −3, -3 % 26 ergibt −3, und −3 + 65 = 62 ist das Zeichen „>“ statt „X“. Richtig wird es mit verschluessele(g, 26 − k) oder mit ((nr + k) % 26 + 26) % 26. Für Buchstaben ohne Umlauf (etwa „Y“ → „T“) fällt der Fehler nicht auf — deshalb muss man gezielt mit Buchstaben am Alphabetanfang testen.