Level 7: Wo soll das enden? #
Mehrere Basisfälle #
Auf zur paktischen Anwendung! Hier wirst du ein Problem kennenlernen, das manche Mathematikstudent:innen zur Verzweiflung gebracht hat. (Das hat vielleicht damit zu tun, dass das Problem eigentlich kein mathematisches ist… ;) Du wirst lernen, wie sich dieses Problem Schritt für Schritt und rekursiv lösen lässt. Auf geht’s!
Look and say #
Du hast sicher schon einmal etwas von »Folgen« gehört. Zum Beispiel wirst du sicher wissen, wie du diese Zahlenfolge fortsetzen musst:
1
3
5
7
Oder diese hier:
2
4
8
16
Hier kommt nun das angekündigte Problem… Kannst du dir denken, wie diese Folge weitergeht? Bevor du weiterliest, knobel doch mal ein wenig daran herum:
1
11
21
1211
111221
312211
Das nächste Element
13112221
Das nächste Element
1113213211
Das nächste Element
31131211131221
Hast Du die nächsten Elemente herausbekommen? Dann hast du vermutlich das Prinzip hinter dieser Folge verstanden.
Die Folge wird »Look and say« genannt, und das verrät eigentlich alles. In der ersten Zeile siehst du eine »1«. In die nächste Zeile schreiben wir also einmal die »1«, weil wir ein gleichartiges Zeichen erkennen, und noch eine »1«, weil dies das Zeichen ist. Daraus ergeben sich zwei Einsen hintereinander: »11« (sprich: »eine Eins«). Das gleiche Prinzip erzeugt die nächste Zeile. Jetzt sehen wir zweimal das Zeichen »1«, schreiben also eine »2« (weil wir zwei gleichartige Zeichen sehen) und eine »1«, weil dieses Zeichen das Zeichen ist, das wir gesehen haben (sprich: »zwei Einsen«). Auf diese Weise lässt sich aus jeder Zeile eindeutig die nächste Zeile ableiten.
Nach den gleichen Regeln ließen sich – mit anderem Start – auch andere Folgen aufschreiben:
333
33
23
1213
11121113
31123113
…
Oder diese hier, die sich von Zeile zu Zeile nicht verändert:
22
22
22
…
Jetzt wollen wir diese Regeln in einem kleinen Programm umsetzen, und zwar strikt rekursiv!
Beginne wieder mit den einfachen Problemen #
Auch hier versuchen wir, ein einfaches Problem zu bestimmen.
Was musst du als erstes herausfinden, um das nächste Folgenglied zu bestimmen? Offensichtlich die Anzahl an gleichen Zeichen, die am Beginn einer Zeichenkette zu finden sind. Für die Zeichenkette »111« wäre das z.B. 3, für »1112« ebenfalls, für »1121« 2, für »1« 1 und für eine leere Zeichenkette 0.
Diese Überlegung hilft uns, die richtigen Basisfälle zu finden. Oft gibt es genau einen Basisfall (wie bei unserem Buchstabenzähler), manchmal aber auch mehrere.
In diesem Fall ist das allereinfachste Teilproblem (wieder) eine leere Zeichenkette. Bekommen wir eine leere Zeichenkette vorgelegt, können wir sofort beantworten, wie viele gleiche Zeichen hintereinander vorkommen: nämlich 0. (Schreibe den Code in die gleiche Datei wie unsere Funktion laenge – die werden wir jetzt wieder verwenden!) In Python-Code sieht das dann so aus:
def zaehle_gleiche_hintereinander(wort):
laenge_wort = laenge(wort)
if laenge_wort < 1:
return 0
Wenn du den Code um die Anweisungen
z1 = ''
print(zaehle_gleiche_hintereinander(z1))
erweiterst, wird auch genau das richtige Ergebnis herauskommen. (Übergibst du andere Zeichenketten, erhalten wir überhaupt kein Ergebnis.)
Ein anderer Fall ist genauso leicht zu entscheiden: Zeichenketten, die genau ein Zeichen lang sind, haben mit Sicherheit auch genau ein gleiches Zeichen hintereinander. Daher können wir unseren Code um einen zweiten Basisfall erweitern:
def zaehle_gleiche_hintereinander(wort):
laenge_wort = laenge(wort)
if laenge_wort < 1:
return 0
elif laenge_wort < 2:
return 1
Ein dritter Basisfall ergibt sich aus der Überlegung heraus, dass wir auch nicht mehr weiterzählen müssen, wenn das zweite Zeichen anders als das erste ist. Da dann die Anzahl der gleichen Zeichen ebenfalls 1 ist, können wir schreiben:
def zaehle_gleiche_hintereinander(wort):
laenge_wort = laenge(wort)
if laenge_wort < 1:
return 0
elif laenge_wort < 2:
return 1
elif wort[0] != wort[1]:
return 1
Wir dürfen auch unbesorgt auf wort[1] zugreifen, und müssen nicht befürchten, dass die Zeichenkette zu kurz ist. Das haben wir ja zuvor mit `laenge_z < 2’ überrüft!
Nun haben wir also drei Basisfälle gefunden, die sich sehr einfach lösen lassen. Doch was geschieht mit einer Zeichenkette wie z.B »112«? Wie kann für diese Zeichenkette das richtige Ergebnis (nämlich 2) ausgegeben werden?
Dafür benötigen wir nun wieder den Rekursionsfall. Wir überlegen also, wie sich die Sache verhält, wenn die Basisfälle nicht vorliegen. Dann handelt es sich um eine Zeichenkette, die zwei oder mehr Zeichen hat, und die ersten beiden müssen gleich sein. Das könnte z.B. »112« sein. Wie ließe sich dieses Problem auf unsere Basisfälle zurückführen?
Über das erste Zeichen wissen wir bereits, dass es das gleiche ist wie das zweite – wir könnten es also einfach weglassen und uns dafür 1 merken, und dann mit dem zweiten Zeichen weitermachen. Dann bliebe die Zeichenkette »12« übrig, und diesen Fall haben wir schon geklärt. (Ein Zeichen, anders als das zweite, gibt 1 zurück.) So geht es! Damit können wir else schreiben, und haben unseren Rekursionsfall:
def zaehle_gleiche_hintereinander(wort):
laenge_wort = laenge(wort)
if laenge_wort < 1:
return 0
elif laenge_wort < 2:
return 1
elif wort[0] != wort[1]:
return 1
else:
return 1 + zaehle_gleiche_hintereinander(wort[1:])
Jetzt kannst du die Funktion testen. Ergänze doch die Datei um folgende Zeilen, und überprüfe, ob alles richtig funktioniert:
print(zaehle_gleiche_hintereinander('1234'))
# hier sollte 1 herauskommen
print(zaehle_gleiche_hintereinander('1112'))
# hier sollte 3 herauskommen
Damit ist das erste Teilproblem gelöst, und zwar rekursiv! Wir können jetzt die Anzahl an gleichen Zeichen am Beginn einer Zeichenkette bestimmen.
Wir zerlegen längere Eingaben… #
…und sehen und sagen, und wenn wir fertig sind: haben wir das nächste Element der Folge.
Rekursion ist erst auf den zweiten Blick einfach und auch einfach elegant. Nun haben wir das erste Problem gelöst – wir können die Anzahl gleicher Zeichen zu Beginn einer Zeichenkette bestimmen.
Doch wie hilft uns das, das schwierigere Problem zu lösen? Nämlich das nächste Element der Folge, wenn eines gegeben ist?
Wieder suchen wir den einfachsten Fall. Bei einer leeren Zeichenkette wissen wir sofort das nächste Element der Folge – dies ist wieder leer. Also bemühen wir noch einmal unsere Funktion laenge, und schreiben unseren Basisfall:
def look_and_say(wort):
if laenge(wort) < 1:
return ''
Wenn das nicht der Fall ist – unsere Funktion also tatsächlich ein »Wort« (das könnte z.B. die Zeichenkette »112« sein) zu sehen bekommt, wird es ein wenig komplizierter. Wir können aber das Ergebnis nach und nach zusammensetzen. Als erstes brauchen wir die Anzahl gleicher Zeichen am Anfang der Kette – doch dieses Problem haben wir bereits gelöst! Wir können also für den Rekursionsfall einfach damit beginnen: (Tippe sie noch nicht ab – erst wollen wir die fertige Funktion entwickeln.)
anzahl_gleiche = zaehle_gleiche_hintereinander(wort)
return str(anzahl_gleiche)
Das Ergebnis wandeln wir mit der Funktion str in eine Zeichenkette um – mit einer solchen soll ja weitergearbeitet werden. Als nächstes interessiert uns, welches Zeichen denn überhaupt vorkam – das finden wir an der ersten Position:
gleich = zaehle_gleiche_hintereinander(wort)
return str(gleich) + wort[0]
Wo müssen wir nun weitermachen? Wir haben die Anzahl gleicher Zeichen gezählt und verarbeitet, daher müssen wir also beim ersten anderen Zeichen weitermachen. Die Position dieses Zeichens haben wir bereits ausgerechnet! Es ist die Position mit der Nummer gleicher Zeichen! (Sehen wir z.B. bei der Zeichenkette »1121« zwei gleiche Zeichen, finden wir das nächste andere Zeichen an der Position zwei. Hier nur zur Erinnerung:
| Position | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Wort | 1 | 1 | 2 | 1 |
Das heißt, wir können einfach den Teil der Zeichenkette, die wir brauchen, ganz leicht ansprechen, und zwar mit wort[gleich:]. (Wie das Aufteilen von Listen und Zeichenkette funktioniert, hast du ja in Level 5 gelernt.) Diesen Teil der Zeichenkette werden wir erneut in unsere Funktion füttern – diese nennen wir passenderweise look_and_say. Sollte die Zeichenkette nach den zuletzt festgestellten Zeichen aufhören, wird eine leere Zeichenkette übergeben, und um eine solche haben wir uns ja bereits im Basisfall gekümmert. Damit sieht unser zusammengebasteltes nächstes Folgenelement nun so aus:
gleich = zaehle_gleiche_hintereinander(wort)
return str(gleich) + wort[0] + look_and_say(wort[gleich:])
Jetzt ist der Rekursionsfall und damit die ganze Funktion fertig, die nun so aussieht: (Jetzt kannst du die Funktion übernehmen!)
def look_and_say(wort):
if laenge(wort) < 1:
return ''
else:
gleich = zaehle_gleiche_hintereinander(wort)
return str(gleich) + wort[0] + look_and_say(wort[gleich:])
Probiere sie gleich aus! Wenn du die Datei mit den Funktionen ausführst, kannst du sie aus dem REPL heraus aufrufen:
>>> look_and_say('1')
'11'
>>> look_and_say('11')
'21'
>>> look_and_say('21')
'1211'
>>> look_and_say('1211')
'111221'