MINT lernen

Übungen: Rekursion auf Zeichenketten

Zehn Übungen zu rekursiven Methoden auf Zeichenketten — vom Zerlegen bis zum Palindrom-Test.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt dir sofort Rückmeldung; wenn du nicht weiterkommst, helfen die gestuften Tipps.

A1
Stimmt's? — Zeichenketten zerlegen
AFB I

Gegeben ist String s = "HAUS";. Gib zu jeder Aussage an, ob sie stimmt.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Aussage 1 von 5

Bei substring(a, b) gehört Position b nicht mehr dazu. "A".substring(1) ist erlaubt und leer, "".substring(1) dagegen ein Laufzeitfehler.
Ansatz: Positionen beginnen bei 0.
Weiter: substring(a, b) endet vor b.
A2
Ausdrücke zu "KANU"
AFB I

Gegeben ist String s = "KANU";. Ordne jedem Ausdruck seinen Wert zu, indem du Paare aufdeckst.

Decke zwei Karten auf, die zusammengehören. Mit der Tastatur: Tab zur Karte, Enter aufdecken, Pfeiltasten zum Wandern.

s.substring(4) ist bei Länge 4 die leere Zeichenkette — genau der einfachste Fall, in dem rekursive Methoden auf Zeichenketten ankommen.
Ansatz: Die letzte Position ist s.length() - 1.
Weiter: Bei substring(a, b) endet der Teil vor b.
A3
Brauchbare Abbruchbedingungen
AFB I

Eine rekursive Methode ruft sich mit s.substring(1) selbst auf. Nenne alle Abbruchbedingungen, die für sie geeignet sind.

Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Auswahl prüfen“.
Drei Schreibweisen prüfen dasselbe: Ist die Zeichenkette leer? null bedeutet „keine Zeichenkette“ und entsteht durch substring nie; eine Länge unter 0 gibt es nicht; charAt(0) scheitert gerade bei der leeren Zeichenkette.
Ansatz: Welcher Rest entsteht nach dem letzten Abtrennen?
Weiter: Die leere Zeichenkette hat die Länge 0.
A4
Zeichen entfernen
AFB II

Wende die Methode ohne an.

static String ohne(String s, char c) {
    if (s.length() == 0) return "";
    String rest = ohne(s.substring(1), c);
    if (s.charAt(0) == c) return rest;
    return s.charAt(0) + rest;
}
Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. ohne("BANANE", 'A') =
  2. ohne("KAKAO", 'K') =
  3. ohne("OTTO", 'T') =
  4. Aufrufe von ohne bei ohne("BANANE", 'A'): Aufrufe
Das erste Zeichen wird nur dann vor den Rest gesetzt, wenn es nicht c ist. Sechs Zeichen, also sechs Aufrufe mit Zeichen und einer mit der leeren Zeichenkette.
Ansatz: Gehe Zeichen für Zeichen: Bleibt es stehen oder fällt es weg?
Weiter: Zähle den Aufruf mit der leeren Zeichenkette mit.
A5
Palindrom-Test verfolgen
AFB II

Stelle den Ablauf von istPalindrom("RADEAR") (Methode von der Inhaltsseite) in einer Tracetabelle dar.

Fülle alle Felder aus und prüfe dann. Enter in einem Feld prüft ebenfalls. Wahrheitswerte als wahr oder falsch.
Aufrufserstes Zeichenletztes ZeichenRückgabe
1"RADEAR"RR
2
3
Im dritten Aufruf sind D und E verschieden — er liefert sofort false, und dieser Wert wird unverändert durchgereicht. Ein vierter Aufruf findet nicht statt.
Ansatz: Jeder Aufruf entfernt das erste und das letzte Zeichen.
Weiter: Der erste Unterschied beendet die Rekursion.
A6
Methoden auf "Abi 2027"
AFB II Mix

Alle Methoden arbeiten rekursiv mit s.charAt(0) und s.substring(1); zaehleZiffern prüft wie in Kapitel 1 mit c >= '0' && c <= '9'. Ermittle die Ergebnisse für s = "Abi 2027".

Klicke links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Das Leerzeichen zählt als Zeichen (Länge 8). Ziffern erkennt man am ASCII-Bereich '0' bis '9'; das große A hat den Code 65.
Ansatz: Zähle auch das Leerzeichen.
Weiter: ASCII: 'A' = 65, '0' = 48.
A7
Zählen mit Fehlern
AFB II

Die Methode soll zählen, wie oft c in s vorkommt. Überprüfe sie.

In diesem Quelltext stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.
Mit Länge 1 als Abbruch fehlt das letzte Zeichen. Die zweite Rückgabe zählt jedes Zeichen — die Methode würde dann die Länge minus 1 liefern.
Ansatz: Teste im Kopf mit "A" und c = 'A'.
Weiter: Zwei Zeilen sind falsch.
A8
Doppelte Nachbarn entfernen
AFB III

Die Methode ohneDoppelte soll aufeinanderfolgende gleiche Zeichen zu einem zusammenfassen: "AABBBCA" wird zu "ABCA". Implementiere sie, indem du die Zeilen ordnest.

Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1static String ohneDoppelte(String s) {
2 if (s.length() <= 1) return s;
3 if (s.charAt(0) == s.charAt(1)) return ohneDoppelte(s.substring(1));
4 return s.charAt(0) + ohneDoppelte(s.substring(1));
5}
Die Reihenfolge der beiden Bedingungen ist nicht egal: s.charAt(1) gibt es erst ab Länge 2 — deshalb muss der einfachste Fall zuerst stehen.
Ansatz: Welche Zeile greift auf s.charAt(1) zu, und wann existiert dieses Zeichen?
Weiter: Ist das erste Zeichen gleich dem zweiten, fällt es weg.
A9
Doppelt gemoppelt
AFB III Trick

Bestimme den Rückgabewert von doppel("AB").

static String doppel(String s) {
    if (s.length() == 0) return "";
    return s.charAt(0) + s.charAt(0) + doppel(s.substring(1));
}
Überlege selbst und trage das Ergebnis ein — Enter prüft direkt.
s.charAt(0) + s.charAt(0) addiert zwei char — das rechnet Java mit den Codes: 65 + 65 = 130. Erst danach wird mit der Zeichenkette verkettet. Aus "B" wird 66 + 66 = 132. Ergebnis "130132" statt „AABB“. Abhilfe: "" + s.charAt(0) + s.charAt(0) + …
Ansatz: Welchen Typ hat s.charAt(0), und was bedeutet + zwischen zwei Werten dieses Typs?
Weiter: ASCII: 'A' = 65, 'B' = 66.
A10
Was passiert bei "OTTO"?
AFB III

Beurteile für jede Methode, wie der Aufruf mit "OTTO" ausgeht.

Ziehe jede Karte in den passenden Korb — oder wähle sie mit Enter aus und drücke dann die Ziffer des Korbs (0 legt sie zurück).
1liefert ein Ergebnis
2Laufzeitfehler (Exception)
3endet nie (StackOverflowError)
Ohne Abbruchbedingung scheitert "".substring(1) mit einer Exception, charAt(4) greift bei Länge 4 daneben. f(s) und s.substring(0) verkleinern das Problem nicht — Endlosrekursion. Die Methode mit Länge 1 als Abbruch funktioniert für "OTTO", scheitert aber an "".
Ansatz: Verfolge die Aufrufe bis zur leeren Zeichenkette.
Weiter: s.substring(0) ist die ganze Zeichenkette.