Geheimschrift
AFB I–IIFür eine Schnitzeljagd werden Botschaften aus Großbuchstaben verschlüsselt, indem jeder Buchstabe um k Stellen im Alphabet verschoben wird; nach Z geht es mit A weiter. Die abgebildete Methode verwendet dazu die Zeichencodes aus Kapitel 1.
static String verschiebe(String s, int k) {
if (s.length() == 0) {
return "";
}
char c = s.charAt(0);
char neu = (char) ('A' + (c - 'A' + k) % 26);
return neu + verschiebe(s.substring(1), k);
}- Beschreiben Sie, wie die Methode eine Zeichenkette rekursiv verarbeitet, und erläutern Sie die Zeile, in der
neuberechnet wird. 4 BE - Wenden Sie die Methode auf
verschiebe("ZEBRA", 3)an. Geben Sie die Aufrufe und das Ergebnis an. 4 BE - Erweitern Sie die Methode so, dass Leerzeichen unverändert übernommen werden. 4 BE
- Schätzen Sie ab, wie viele Zeichen durch
substringinsgesamt kopiert werden, wenn eine Botschaft mit 1000 Buchstaben verschlüsselt wird, und nennen Sie eine Möglichkeit, das zu vermeiden. 3 BE
Insgesamt 15 BE
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Ist die Zeichenkette leer, wird "" zurückgegeben. Sonst wird das erste Zeichen verschlüsselt und vor die rekursiv verschlüsselte Restzeichenkette gesetzt. c - 'A' ist die Position des Buchstabens im Alphabet (0 bis 25), dazu kommt k; % 26 sorgt dafür, dass nach Z wieder A kommt. 'A' + … liefert den Zeichencode des neuen Buchstabens, die Typumwandlung (char) macht daraus ein Zeichen. Beispiel: Z hat Position 25, (25 + 3) % 26 = 2, also C.
Erwartungshorizont zu Aufgabe b)
Aufrufe: verschiebe("ZEBRA", 3), verschiebe("EBRA", 3), verschiebe("BRA", 3), verschiebe("RA", 3), verschiebe("A", 3), verschiebe("", 3). Rückgaben von hinten: "", "D", "UD", "EUD", "HEUD", "CHEUD".
Erwartungshorizont zu Aufgabe c)
static String verschiebe(String s, int k) {
if (s.length() == 0) {
return "";
}
char c = s.charAt(0);
String rest = verschiebe(s.substring(1), k);
if (c == ' ') {
return " " + rest;
}
char neu = (char) ('A' + (c - 'A' + k) % 26);
return neu + rest;
}Test: verschiebe("ZEBRA ZOO", 3) liefert "CHEUD CRR". Das Leerzeichen muss vor der Berechnung abgefangen werden, sonst entstünde ein falsches Zeichen.
Erwartungshorizont zu Aufgabe d)
Die Reste haben 999, 998, …, 1, 0 Zeichen; zusammen \(\frac{999 \cdot 1000}{2} \approx 500\,000\) kopierte Zeichen, der Aufwand wächst quadratisch mit der Länge. Abhilfe: statt substring einen Indexparameter i übergeben und s.charAt(i) verwenden (oder iterativ arbeiten); dann wird jedes Zeichen nur einmal gelesen.
Klammern im Formeleditor
AFB II–IIIEin Formeleditor prüft, ob in einer Eingabe jede öffnende runde Klammer genau einmal geschlossen wird. Andere Zeichen werden übergangen. Die Methode wird mit ausgeglichen(s, 0) aufgerufen.
static boolean ausgeglichen(String s, int offen) {
if (offen < 0) {
return false;
}
if (s.length() == 0) {
return offen == 0;
}
char c = s.charAt(0);
if (c == '(') {
return ausgeglichen(s.substring(1), offen + 1);
}
if (c == ')') {
return ausgeglichen(s.substring(1), offen - 1);
}
return ausgeglichen(s.substring(1), offen);
}- Analysieren Sie den Aufruf
ausgeglichen("(a)(b", 0)mit einer Tabelle der Aufrufe und Parameterwerte. 4 BE - Erläutern Sie die Bedeutung des Parameters
offenund die Notwendigkeit der Abbruchbedingungoffen < 0am Beispiel")(". 4 BE - Entwerfen Sie eine rekursive Methode
tiefe(String s, int offen, int max), die für eine ausgeglichene Eingabe die größte Verschachtelungstiefe liefert, z. B. 3 für"(()(()))". Gestartet wird mittiefe(s, 0, 0). 5 BE - Beurteilen Sie den Vorschlag, den Parameter
offendurch eine globale Variable zu ersetzen. 3 BE
Insgesamt 16 BE
Hinweise
Hinweis zu Aufgabe a)
s und den Wert von offen.Hinweis zu Aufgabe b)
offen? Was bedeutet ein negativer Wert?Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| Aufruf | s | offen | Aktion |
|---|---|---|---|
| 1 | "(a)(b" | 0 | ( → offen + 1 |
| 2 | "a)(b" | 1 | anderes Zeichen |
| 3 | ")(b" | 1 | ) → offen − 1 |
| 4 | "(b" | 0 | ( → offen + 1 |
| 5 | "b" | 1 | anderes Zeichen |
| 6 | "" | 1 | leer: offen == 0 ist falsch |
Rückgabe false, durchgereicht bis zum ersten Aufruf: Eine Klammer bleibt offen.
Erwartungshorizont zu Aufgabe b)
offen zählt die bisher geöffneten, noch nicht geschlossenen Klammern. Ein negativer Wert heißt: Es wurde eine Klammer geschlossen, die nie geöffnet war. Bei ")(" wird offen nach dem ersten Zeichen −1. Ohne die Prüfung ginge es weiter, das ( brächte den Zähler wieder auf 0 und die Methode meldete fälschlich true. Mit der Prüfung liefert sie sofort false.
Erwartungshorizont zu Aufgabe c)
static int tiefe(String s, int offen, int max) {
if (s.length() == 0) {
return max;
}
char c = s.charAt(0);
if (c == '(') {
offen++;
if (offen > max) {
max = offen;
}
} else if (c == ')') {
offen--;
}
return tiefe(s.substring(1), offen, max);
}tiefe("(()(()))", 0, 0) liefert 3. max wird wie offen als Parameter weitergereicht, sodass jeder Aufruf den bisher größten Wert kennt.
Erwartungshorizont zu Aufgabe d)
Der Vorschlag ist ungünstig. Eine globale Variable müsste vor jedem neuen Aufruf von außen auf 0 zurückgesetzt werden; wer das vergisst, erhält falsche Ergebnisse, sobald die Methode ein zweites Mal verwendet wird. Außerdem wäre die Methode nicht mehr allein aus ihren Parametern verständlich. Als Parameter gehört der Zählerstand zu jedem Aufruf und kann nicht versehentlich von anderen Programmteilen verändert werden. Der Speicherbedarf ist in beiden Fällen ähnlich.