In diesem Tutorial lernen Sie, wie Sie das Pascal-Dreieck in Python für eine bestimmte Anzahl von Zeilen drucken.
Sie beginnen damit, zu lernen, wie man das Pascalsche Dreieck konstruiert. Anschließend schreiben Sie eine Python-Funktion und lernen, sie weiter zu optimieren.
▶️ Fangen wir an!
Inhaltsverzeichnis
Was ist Pascals Dreieck und wie konstruiert man es?
Das Drucken des Pascal-Dreiecks für eine bestimmte Anzahl von Zeilen ist eine beliebte Interviewfrage.
In Pascals Dreieck mit n Zeilen hat Zeile Nummer i i Elemente.
Die erste Zeile hat also ein Element, und es ist 1. Und jedes Element in den nachfolgenden Zeilen ist die Summe der beiden Zahlen direkt darüber.
Die folgende Abbildung erklärt, wie man ein Pascalsches Dreieck mit fünf Reihen konstruiert.
Pascalsches Dreieck für numRows = 5 (Bild vom Autor)
Beachten Sie, wie Sie Nullen auffüllen können, wenn Sie nur eine Zahl über einer bestimmten Zahl haben.
📝Befolgen Sie als schnelle Übung das obige Verfahren, um das Pascalsche Dreieck für n = 6 und n = 7 zu konstruieren.
Lassen Sie uns als Nächstes mit dem Schreiben von Code fortfahren. Sie können die Codeausschnitte direkt in Ihrem Browser in der Python-IDE von wdzwdz ausführen, während Sie sich durch das Tutorial arbeiten.
Python-Funktion zum Drucken des Pascal-Dreiecks
Lassen Sie uns in diesem Abschnitt eine Python-Funktion schreiben, um das Pascalsche Dreieck für eine beliebige Anzahl von Zeilen auszugeben.
Es gibt zwei zentrale Fragen, die es zu beachten gilt:
- Wie drückt man die Einträge im Pascalschen Dreieck aus?
- Wie drucke ich das Pascalsche Dreieck mit angemessenem Abstand und Formatierung?
Lassen Sie uns sie jetzt beantworten.
#1. Wie lautet der Ausdruck für jeden Eintrag in Pascals Dreieck?
Die Einträge im Pascalschen Dreieck lassen sich nämlich mit der Formel für nCr ermitteln. Wenn Sie sich an Ihre Schulmathematik erinnern, bezeichnet nCr die Anzahl der Möglichkeiten, wie Sie r Elemente aus einem Satz von n Elementen auswählen können.
Die Formel für nCr ist unten angegeben:
nCr-Formel (Bild vom Autor)
Lassen Sie uns nun fortfahren, die Einträge im Pascalschen Dreieck mit der nCr-Formel auszudrücken.
Pascalsche Dreieckseinträge mit nCr (Bild vom Autor)
Wir haben jetzt einen Weg gefunden, die Einträge in der Matrix auszudrücken.
#2. Wie wird der Abstand beim Drucken des Musters angepasst?
In Pascals Dreieck mit numRows hat Zeile #1 einen Eintrag, Zeile #2 hat zwei Einträge und so weiter. Um das Muster als Dreieck zu drucken, benötigen Sie numRows – i Leerzeichen in Zeile #i. Dazu können Sie die Range-Funktion von Python in Verbindung mit der for-Schleife verwenden.
Da die Bereichsfunktion den Endpunkt standardmäßig ausschließt, stellen Sie sicher, dass Sie + 1 hinzufügen, um die erforderliche Anzahl führender Leerzeichen zu erhalten.
Nachdem Sie nun gelernt haben, wie Sie Einträge darstellen und auch den Abstand anpassen, während Sie das Pascal-Dreieck drucken, lassen Sie uns fortfahren und die Funktion pascal_tri definieren.
Analysieren der Funktionsdefinition
Was soll also die Funktion pascal_tri tun?
- Die Funktion pascal_tri sollte die Anzahl der Zeilen (numRows) als Argument akzeptieren.
- Es sollte Pascals Dreieck mit numRows drucken.
Um die Fakultät zu berechnen, verwenden wir die Fakultätsfunktion aus dem integrierten Mathematikmodul von Python.
▶️ Führen Sie die folgende Codezelle aus, um die Fakultät zu importieren und in Ihrem aktuellen Modul zu verwenden.
from math import factorial
Das folgende Code-Snippet enthält die Funktionsdefinition.
def pascal_tri(numRows):
'''Print Pascal's triangle with numRows.'''
for i in range(numRows):
# loop to get leading spaces
for j in range(numRows-i+1):
print(end=" ")
# loop to get elements of row i
for j in range(i+1):
# nCr = n!/((n-r)!*r!)
print(factorial(i)//(factorial(j)*factorial(i-j)), end=" ")
# print each row in a new line
print("n")
Die Funktion funktioniert wie folgt:
- Die Funktion pascal_tri hat einen erforderlichen Parameter numRows: die Anzahl der Zeilen.
- Es gibt insgesamt numRows Zeilen. Für jede Zeile i fügen wir numRows – i führende Leerzeichen vor dem ersten Eintrag in der Zeile hinzu.
- Wir verwenden dann die nCr-Formel, um die einzelnen Einträge zu berechnen. Für Zeile i lauten die Einträge iCj, wobei j = {0,1,2,..,i}.
- Beachten Sie, dass wir // verwenden, das eine ganzzahlige Division durchführt, da wir möchten, dass die Einträge ganze Zahlen sind.
- Nachdem Sie alle Einträge in einer Reihe berechnet haben, drucken Sie die nächste Reihe in einer neuen Zeile.
🔗 Da wir eine hinzugefügt haben Dokumentzeichenfolge, können Sie die integrierte Hilfefunktion von Python oder das Attribut __doc__ verwenden, um auf den Docstring der Funktion zuzugreifen. Das folgende Code-Snippet zeigt, wie es geht.
help(pascal_tri)
# Output
Help on function pascal_tri in module __main__:
pascal_tri(numRows)
Print Pascal's triangle with numRows.
pascal_tri.__doc__
# Output
Print Pascal's triangle with numRows.
Lassen Sie uns nun fortfahren und die Funktion mit der Anzahl der Zeilen als Argument aufrufen.
pascal_tri(3)
# Output
1
1 1
1 2 1
Die ersten 3 Reihen von Pascals Dreieck werden wie erwartet gedruckt.
Drucken Sie das Pascalsche Dreieck mit Rekursion
Im vorherigen Abschnitt haben wir den mathematischen Ausdruck jedes Eintrags im Pascal-Dreieck identifiziert. Wir haben jedoch die Beziehung zwischen Einträgen in zwei aufeinanderfolgenden Zeilen nicht verwendet.
Tatsächlich haben wir die vorherige Zeile verwendet, um die Einträge in der nachfolgenden Zeile zu berechnen. Können wir das nicht verwenden und uns eine rekursive Implementierung der Funktion pascal_tri einfallen lassen?
Ja, lass uns das machen!
Bei einer rekursiven Implementierung ruft sich eine Funktion wiederholt selbst auf, bis der Basisfall erfüllt ist. Bei der Konstruktion des Pascalschen Dreiecks beginnen wir mit der ersten Zeile mit einem Eintrag 1 und bauen dann die folgenden Zeilen auf.
Der Funktionsaufruf von pascal_tri(numRows) ruft also wiederum pascal_tri(numRows-1) auf und so weiter, bis der Basisfall pascal_tri(1) erreicht ist.
Betrachten Sie das Beispiel, in dem Sie die ersten 3 Zeilen des Pascal-Dreiecks drucken müssen. Die folgende Abbildung erläutert, wie die rekursiven Aufrufe auf den Stack übertragen werden. Und wie die rekursiven Funktionsaufrufe die Zeilen des Pascalschen Dreiecks zurückgeben.
Aufrufliste bei rekursiven Aufrufen (Bild vom Autor)
▶️ Führen Sie das folgende Code-Snippet aus, um die Zeilen von Pascals Dreieck rekursiv zu generieren.
def pascal_tri(numRows):
'''Print Pascal's triangle with numRows.'''
if numRows == 1:
return [[1]] # base case is reached!
else:
res_arr = pascal_tri(numRows-1) # recursive call to pascal_tri
# use previous row to calculate current row
cur_row = [1] # every row starts with 1
prev_row = res_arr[-1]
for i in range(len(prev_row)-1):
# sum of 2 entries directly above
cur_row.append(prev_row[i] + prev_row[i+1])
cur_row += [1] # every row ends with 1
res_arr.append(cur_row)
return res_arr
Hier sind einige Punkte, die es wert sind, beachtet zu werden:
- Wir haben eine verschachtelte Liste als Datenstruktur verwendet, wobei jede Zeile in Pascals Dreieck eine eigene Liste ist, wie hier: [[row 1], [row 2],…,[row n]].
- Der Funktionsaufruf pascal_tri(numRows) löst eine Reihe rekursiver Aufrufe mit numRows – 1, numRows – 2 bis hin zu 1 als Argumente aus. Diese Aufrufe werden auf einen Stapel geschoben.
- Wenn numRows == 1 ist, haben wir den Basisfall erreicht und die Funktion kehrt zurück [[1]].
- Jetzt wird die zurückgegebene Liste von den nachfolgenden Funktionen in der Aufrufliste verwendet, um die nächste Zeile zu berechnen.
- Wenn cur_row die aktuelle Zeile ist, wird cur_row[i] = vorherige_zeile[i] + vorherige_zeile[i+1]— die Summe von 2 Elementen direkt über dem aktuellen Index.
Da das zurückgegebene Array eine verschachtelte Liste (Liste von Listen) ist, müssen wir die Abstände anpassen und die Einträge ausdrucken, wie in der Codezelle unten gezeigt.
tri_array = pascal_tri(5)
for i,row in enumerate(tri_array):
for j in range(len(tri_array) - i + 1):
print(end=" ") # leading spaces
for j in row:
print(j, end=" ") # print entries
print("n") # print new line
Die Ausgabe ist korrekt, wie unten zu sehen ist!
# Output
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Python-Funktion zum Drucken des Pascal-Dreiecks für numRows ≤ 5
Beide Methoden, die Sie gelernt haben, funktionieren, um Pascals Dreieck für eine beliebige Anzahl von Zeilen numRows zu drucken.
Es gibt jedoch Zeiten, in denen Sie das Pascalsche Dreieck für eine kleinere Anzahl von Zeilen drucken müssen. Und wenn die Anzahl der Zeilen, die Sie drucken müssen, höchstens 5 beträgt, können Sie eine einfache Technik anwenden.
Gehen Sie die folgende Abbildung durch. Und beobachten Sie, wie die Potenzen von 11 mit den Einträgen in Pascals Dreieck identisch sind. Beachten Sie auch, dass dies nur bis zur 4. Potenz von 11 funktioniert. Das heißt, 11 potenziert mit {0, 1, 2, 3, 4} ergibt die Einträge in den Zeilen 1 bis 5 des Pascalschen Dreiecks.
Lassen Sie uns die Funktionsdefinition umschreiben, wie unten gezeigt:
def pascal_tri(numRows):
'''Print Pascal's triangle with numRows.'''
for i in range(numRows):
print(' '*(numRows-i), end='')
# compute power of 11
print(' '.join(str(11**i)))
So funktioniert die Funktion pascal_tri:
- Wie bei den vorherigen Beispielen passen wir den Abstand an.
- Und dann verwenden wir Pythons Exponentiationsoperator (**), um die Potenzen von 11 zu berechnen.
- Da die Potenzen von 11 standardmäßig ganze Zahlen sind, konvertieren Sie sie mit str() in einen String. Sie haben jetzt die Potenzen von 11 als Saiten.
- Strings in Python sind Iterables – Sie können sie also durchlaufen und auf jeweils ein Zeichen zugreifen.
- Als Nächstes können Sie die Methode join() mit der folgenden Syntax verwenden:
.join( ), um Elemente in mit als Trennzeichen zu verbinden. - Hier brauchen Sie ein einzelnes Leerzeichen zwischen den Zeichen, also ist
‚ ‚, ist string: Potenz von 11.
Lassen Sie uns überprüfen, ob die Funktion wie beabsichtigt funktioniert.
pascal_tri(5)
# Output
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Rufen Sie als weiteres Beispiel die Funktion pascal_tri mit 4 als Argument auf.
pascal_tri(4)
# Output
1
1 1
1 2 1
1 3 3 1
Ich hoffe, Sie wissen, wie Sie das Pascal-Dreieck für numRows im Bereich 1 bis 5 einfach drucken können.
Fazit
Folgendes haben wir gelernt:
- Wie konstruiere ich das Pascalsche Dreieck mit der gegebenen Zeilenzahl? Jede Zahl in jeder Reihe ist die Summe der beiden Zahlen direkt darüber.
- Schreiben Sie eine Python-Funktion mit der Formel nCr = n!/(nr)!.r! um die Einträge des Pascalschen Dreiecks zu berechnen.
- Anschließend haben Sie eine rekursive Implementierung der Funktion kennengelernt.
- Schließlich haben Sie die optimale Methode zum Konstruieren des Pascalschen Dreiecks für numRows bis zu 5 gelernt – unter Verwendung der Potenzen von 11.
Wenn Sie Python-Fähigkeiten verbessern möchten, lernen Sie, Matrizen zu multiplizieren, zu prüfen, ob eine Zahl eine Primzahl ist, und Probleme mit Zeichenfolgenoperationen zu lösen. Viel Spaß beim Codieren!