Einführung
Bei dem tollen Wetter freust du dich nicht gerade darauf, eine Stunde im Klassenzimmer zu verbringen.
Genervt betrittst du den Raum und bemerkst eine seltsam zufriedenstellende Dreiecksform an der Tafel.
Während du auf deinen Mathelehrer wartest, fallen dir einige Muster in dem Dreieck auf: Die äußeren Werte sind alle Einsen, jede folgende Zeile hat einen Wert mehr als die vorherige, und das Dreieck ist symmetrisch.
Seltsam!
Kurz nachdem du dich gesetzt hast, betritt dein Lehrer den Raum und erklärt, dass dieses Dreieck das berühmte Pascalsche Dreieck ist.
In der nächsten Stunde zeigt dir dein Lehrer einige erstaunliche Dinge, die in diesem Dreieck stecken:
- Man kann damit berechnen, auf wie viele Arten du K Elemente aus N Werten auswählen kannst.
- Es enthält die Fibonacci-Folge.
- Wenn du ungerade und gerade Zahlen unterschiedlich einfärbst, erhältst du ein wunderschönes Muster, das Sierpiński-Dreieck genannt wird.
Dein Lehrer bittet dich und deine Mitschüler eindringlich, nach weiteren Anwendungen zu suchen, und versichert dir, dass es noch viel mehr gibt!
In dem Moment klingelt die Schulglocke.
Dir wird klar, dass du die letzte Stunde völlig in das Lernen über das Pascalsche Dreieck vertieft warst.
Du schnappst dir schnell deinen Laptop aus der Tasche und gehst nach draußen, bereit, sowohl den Sonnenschein als auch die Wunder des Pascalschen Dreiecks zu genießen.
Anleitung
Deine Aufgabe ist es, die ersten N Zeilen des Pascalschen Dreiecks auszugeben.
Das Pascalsche Dreieck ist eine dreieckige Anordnung positiver Ganzzahlen.
Im Pascalschen Dreieck ist die Anzahl der Werte in einer Zeile gleich ihrer Zeilennummer (die bei eins beginnt).
Die erste Zeile hat also einen Wert, die zweite Zeile zwei Werte, und so weiter.
Die erste (oberste) Zeile hat einen einzigen Wert: 1.
Die Werte der nachfolgenden Zeilen ergeben sich, indem du die Zahlen direkt rechts und links der aktuellen Position in der vorherigen Zeile addierst.
Wenn die vorherige Zeile keinen Wert links oder rechts der aktuellen Position hat (was nur bei der äußersten linken und rechten Position vorkommt), behandle den Wert dieser Position als null (du „ignorierst“ ihn bei der Summierung).
Beispiel
Schauen wir uns die ersten 5 Zeilen des Pascalschen Dreiecks an:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Die oberste Zeile hat einen Wert, nämlich 1.
Die äußersten linken und rechten Werte haben nur eine vorangehende Position, die sie berücksichtigen müssen, nämlich die Position rechts bzw. links von ihnen.
Da der oberste Wert 1 ist, folgt daraus, dass alle äußersten linken und rechten Werte ebenfalls 1 sind.
Alle anderen Werte haben zwei Positionen, die sie berücksichtigen müssen.
In der fünften Zeile (1 4 6 4 1) ist der mittlere Wert zum Beispiel 6, denn die Werte links und rechts davon in der vorherigen Zeile sind 3 und 3:
Wie diese Übung in Python umgesetzt wird: Rekursion
Diese Übung ist so angelegt, dass du sie mit recursion löst, statt mit Schleifen.
Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft. Das ist nützlich, wenn du Probleme löst, die durch sich selbst definiert sind.
Um eine unendliche Rekursion zu vermeiden (genauer gesagt, um ein Überlaufen des Stacks zu vermeiden), verwendet man etwas, das man „Basisfall“ nennt.
Wenn der Basisfall erreicht wird, gibt die Funktion einen nicht-rekursiven Wert zurück. Das erlaubt es dem vorherigen Funktionsaufruf, abzuschließen und seinen Wert zurückzugeben, und so weiter, Schritt für Schritt den Stack hinunter, bis der erste Funktionsaufruf die Antwort zurückgibt.
Wir könnten eine rekursive Funktion schreiben, um die Antwort auf 5! (also 5 * 4 * 3 * 2 * 1) zu finden, und zwar so:
def factorial(number):
if number <= 1: # base case
return 1
return number * factorial(number - 1) # recursive case
print(factorial(5)) # returns 120
Zum Schluss sei angemerkt, dass Python die Anzahl der möglichen rekursiven Aufrufe begrenzt (standardmäßig 1000) und Endrekursion nicht optimiert.
Ausnahmemeldungen
Manchmal ist es notwendig, eine Ausnahme auszulösen.
Dabei solltest du immer eine aussagekräftige Fehlermeldung angeben, die zeigt, woher der Fehler kommt.
Das macht deinen Code lesbarer und erleichtert das Debugging erheblich.
Wenn du weißt, dass die Fehlerquelle von einem bestimmten Typ ist, kannst du eine der eingebauten Fehlertypen auslösen, solltest aber trotzdem eine aussagekräftige Meldung angeben.
Diese Übung verlangt, dass du die raise-Anweisung verwendest, um mehrere ValueErrors zu „werfen“, wenn der Funktion rows() eine negative Zahl übergeben wird.
Die Tests sind nur erfolgreich, wenn du die exception mit raise auslöst und eine Meldung mitgibst.
Um einen ValueError mit einer Meldung auszulösen, gib die Meldung als Argument an den exception-Typ an:
# if the rows function is passed a negative number.
raise ValueError("number of rows is negative")
