Wie man das Pascalsche Dreieck in Python druckt

In diesem Tutorial lernen Sie, wie Sie das Pascalsche Dreieck in Python für eine bestimmte Anzahl von Zeilen ausgeben können.

Sie lernen zunächst, wie das Pascalsche Dreieck konstruiert wird. Anschließend werden Sie eine Python-Funktion schreiben und lernen, diese weiter zu optimieren.

▶️ Lassen Sie uns beginnen!

Was ist das Pascalsche Dreieck und wie konstruiert man es?

Das Drucken des Pascalschen Dreiecks für eine bestimmte Anzahl von Zeilen ist eine beliebte Interviewfrage.

In einem Pascalschen Dreieck mit n Zeilen hat die Zeile mit der Nummer i i Elemente.

Die erste Zeile hat also ein Element, und zwar die 1. Und jedes Element in den folgenden Zeilen ist die Summe der beiden Zahlen direkt darüber.

Die folgende Abbildung erklärt, wie man das Pascalsche Dreieck mit fünf Zeilen konstruiert.

Beachten Sie, wie Sie Nullen auffüllen können, wenn Sie nur eine Zahl über einer bestimmten Zahl haben.

📝Als schnelle Übung folgen Sie dem obigen Verfahren, um das Pascalsche Dreieck für n = 6 und n = 7 zu konstruieren.

Lassen Sie uns nun etwas Code schreiben. Sie können die Codeschnipsel in der Python IDE von Geekflare direkt in Ihrem Browser ausführen, während Sie sich durch das Tutorial arbeiten.

Python-Funktion zum Drucken des Pascalschen Dreiecks

In diesem Abschnitt schreiben wir eine Python-Funktion, die das Pascal’sche Dreieck für eine beliebige Anzahl von Zeilen ausgibt.

Dabei gibt es zwei wichtige Fragen zu beachten:

• Wie lassen sich die Einträge im Pascalschen Dreieck ausdrücken?
• Wie druckt man das Pascalsche Dreieck mit angemessenen Abständen und Formatierungen?

Lassen Sie uns diese Fragen jetzt beantworten.

#1. Wie lautet der Ausdruck für jeden Eintrag im Pascalschen Dreieck?

Zufälligerweise lassen sich die Einträge im Pascalschen Dreieck mit Hilfe der Formel für nCr ermitteln. Wenn Sie sich noch an Ihre Schulmathematik erinnern, gibt nCr die Anzahl der Möglichkeiten an, wie Sie aus einer Menge von n Gegenständen r auswählen können.

Die Formel für nCr ist unten angegeben:

Lassen Sie uns nun damit fortfahren, die Einträge im Pascalschen Dreieck mit Hilfe der nCr-Formel auszudrücken.

Wir haben nun einen Weg gefunden, um die Einträge in der Matrix auszudrücken.

#2. Wie passt man die Abstände beim Drucken des Musters an?

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 range-Funktion standardmäßig den Endpunkt ausschließt, müssen Sie 1 hinzufügen, um die erforderliche Anzahl von führenden Leerzeichen zu erhalten.

Nun, da Sie gelernt haben, wie Sie Einträge darstellen und auch den Abstand beim Drucken des Pascalschen Dreiecks anpassen können, lassen Sie uns fortfahren und die Funktion pascal_tri definieren.

Parsen der Funktionsdefinition

Was soll die Funktion pascal_tri also tun?

• Die Funktion pascal_tri sollte die Anzahl der Zeilen(numRows) als Argument akzeptieren.
• Sie sollte das Pascalsche Dreieck mit numRows ausgeben.

Um die Fakultät zu berechnen, verwenden wir die Funktion factorial aus dem integrierten Mathematikmodul von Python.

▶️ Führen Sie die folgende Codezelle aus, um factorial zu importieren und in Ihrem aktuellen Modul zu verwenden.

from math import factorial

Der folgende Codeschnipsel enthält die Funktionsdefinition.

def pascal_tri(numRows):
 '''Pascal'sches Dreieck mit numRows ausgeben.'''
 for i in range(numRows):
   # Schleife, um führende Leerzeichen zu erhalten
for j in range(numRows-i 1):
print(end=" ")
    
 # Schleife, um Elemente der Zeile i zu erhalten
for j in range(i 1):
# nCr = n!/((n-r)!*r!)
print(factorial(i)//(factorial(j)*factorial(i-j)), end=" ")

# jede Zeile in einer neuen Zeile drucken
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.
• Anschließend verwenden wir die Formel nCr, 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 ganzzahlig sind.
• Nachdem Sie alle Einträge in einer Zeile berechnet haben, geben Sie die nächste Zeile in einer neuen Zeile aus.

da wir einen Docstring hinzugefügt haben, können Sie die in Python integrierte Hilfefunktion oder das Attribut __doc__ verwenden, um auf den Docstring der Funktion zuzugreifen. Der folgende Codeschnipsel zeigt, wie das geht.

help(pascal_tri)

# Ausgabe
Hilfe zur Funktion pascal_tri im Modul __main__:

pascal_tri(numRows)
 Drucke das Pascalsche Dreieck mit numRows.

pascal_tri.__doc__

# Ausgabe
Drucke das Pascalsche Dreieck mit numRows.

Lassen Sie uns nun fortfahren und die Funktion mit der Anzahl der Zeilen als Argument aufrufen.

pascal_tri(3)

# Ausgabe
 1
 1 1
 1 2 1

Die ersten 3 Zeilen des Pascal’schen Dreiecks werden wie erwartet gedruckt.

Pascalsches Dreieck mit Rekursion drucken

Im vorherigen Abschnitt haben wir den mathematischen Ausdruck jedes Eintrags im Pascalschen Dreieck ermittelt. Allerdings haben wir die Beziehung zwischen den Einträgen in zwei aufeinanderfolgenden Zeilen nicht genutzt.

Vielmehr haben wir die vorherige Zeile verwendet, um die Einträge in der nachfolgenden Zeile zu berechnen. Können wir dies nicht nutzen und eine rekursive Implementierung der Funktion pascal_tri entwickeln?

Ja, lassen Sie uns das tun!

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 nachfolgenden Zeilen auf.

Der Funktionsaufruf von pascal_tri(numRows) ruft also seinerseits 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 Pascalschen Dreiecks ausgeben müssen. Das folgende Bild erklärt, wie die rekursiven Aufrufe auf den Stack geschoben werden. Und wie die rekursiven Funktionsaufrufe die Zeilen von Pascals Dreieck zurückgeben.

▶️ Führen Sie den folgenden Codeschnipsel aus, um die Zeilen des Pascalschen Dreiecks rekursiv zu erzeugen.

def pascal_tri(numRows):
   '''Pascal's Dreieck mit numRows ausgeben.'''
 if numRows == 1:
 return [<x><x><x>[1]</x></x></x>] # Basisfall ist erreicht!
 else:
 res_arr = pascal_tri(numRows-1) # rekursiver Aufruf von pascal_tri
 # vorherige Zeile zur Berechnung der aktuellen Zeile verwenden 
 cur_row = <x><x><x>[1]</x></x></x> # jede Zeile beginnt mit 1
 prev_row = res_arr[-1] 
 for i in range(len(prev_row)-1):
           # Summe der 2 Einträge direkt darüber
 cur_row.append(prev_row<x><x>[i]</x></x> prev_row[i 1]) 
 cur_row = <x><x><x>[1]</x></x></x> # jede Zeile endet mit 1
 res_arr.append(cur_row)
 return res_arr

Hier sind ein paar Punkte, die Sie beachten sollten:

• Wir haben eine verschachtelte Liste als Datenstruktur verwendet, bei der jede Zeile in Pascals Dreieck eine Liste für sich ist, etwa so: [[Zeile 1], [Zeile 2],…,[Zeile n]].
• Der Funktionsaufruf pascal_tri(numRows) löst eine Reihe von rekursiven Aufrufen mit numRows - 1, numRows - 2 bis hin zu 1 als Argumenten aus. Diese Aufrufe werden auf einen Stapel geschoben.
• Wenn numRows == 1 ist, haben wir den Basisfall erreicht, und die Funktion gibt [[1]].
• Nun wird die zurückgegebene Liste von den nachfolgenden Funktionen im Aufrufstapel verwendet, um die nächste Zeile zu berechnen.
• Wenn cur_row die aktuelle Zeile ist, ist cur_row<x><x>[i]</x></x> = prev_row<x><x>[i]</x></x> prev_row[i 1]-die Summe der 2 Elemente direkt über dem aktuellen Index.

Da es sich bei dem zurückgegebenen Array um eine verschachtelte Liste (Liste von Listen) handelt, müssen wir die Abstände anpassen und die Einträge ausdrucken, wie in der folgenden Codezelle gezeigt.

tri_array = pascal_tri(5)

for i,row in enumerate(tri_array):
 for j in range(len(tri_array) - i 1):
 print(end=" ") # führende Leerzeichen
 for j in row:
 print(j, end=" ") # Einträge drucken
 print("\n") # neue Zeile drucken

Die Ausgabe ist korrekt, wie unten zu sehen!

# Ausgabe

 1

 1 1

 1 2 1

 1 3 3 1

 1 4 6 4 1

Python-Funktion zum Drucken des Pascalschen Dreiecks für numRows ≤ 5

Beide Methoden, die Sie gelernt haben, funktionieren, um das Pascalsche Dreieck für eine beliebige Anzahl von Zeilen numRows zu drucken.

Es kann jedoch vorkommen, dass Sie das Pascalsche Dreieck für eine geringere Anzahl von Zeilen drucken müssen. Und wenn die Anzahl der Zeilen, die Sie ausdrucken müssen, höchstens 5 beträgt, können Sie eine unkomplizierte Technik verwenden.

Sehen Sie sich die folgende Abbildung an. Beachten Sie, dass 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, d.h. 11 erhöht auf die Potenzen {0, 1, 2, 3, 4} ergibt die Einträge in den Zeilen 1 bis 5 von Pascals Dreieck.

Schreiben wir die Funktionsdefinition um, wie unten gezeigt:

def pascal_tri(numRows):
 '''Pascalsches Dreieck mit numRows ausgeben.'''
 for i in range(numRows):
 print(' '*(numRows-i), end='')
   # Berechne Potenz von 11
 print(' '.join(str(11**i)))

Hier sehen Sie, wie die Funktion pascal_tri funktioniert:

• Wie bei den vorherigen Beispielen passen wir die Abstände an.
• Und dann verwenden wir den Potenzierungsoperator von Python (**), um die Potenzen von 11 zu berechnen.
• Da die Potenzen von 11 standardmäßig ganze Zahlen sind, wandeln Sie sie mit str() in eine Zeichenkette um. Sie haben nun die Potenzen von 11 als Strings.
• Strings in Python sind Iterables, d.h. Sie können sie in einer Schleife durchlaufen und auf ein Zeichen nach dem anderen zugreifen.
• Als nächstes können Sie die join() -Methode mit der Syntax: <sep>.join(<iterable>) verwenden, um Elemente in <iterable> mit <sep> als Trennzeichen zu verbinden.
• Hier brauchen Sie ein einzelnes Leerzeichen zwischen den Zeichen, also wird <sep> ' ', <iterable> ist String: Potenz von 11.

Lassen Sie uns prüfen, ob die Funktion wie vorgesehen funktioniert.

pascal_tri(5)

# Ausgabe
 1
 1 1
 1 2 1
 1 3 3 1
 1 4 6 4 1

Als weiteres Beispiel rufen Sie die Funktion pascal_tri mit 4 als Argument auf.

pascal_tri(4)

# Ausgabe
 1
 1 1
 1 2 1
 1 3 3 1

Ich hoffe, Sie haben verstanden, wie Sie das Pascal-Dreieck für numRows im Bereich 1 bis 5 einfach ausgeben können.

Schlussfolgerung

Hier ist, was wir gelernt haben:

• Wie man das Pascalsche Dreieck mit der gegebenen Anzahl von Zeilen konstruiert. Jede Zahl in jeder Zeile ist die Summe der beiden Zahlen direkt über ihr.
• Schreiben Sie eine Python-Funktion mit der Formel nCr = n!/(n-r)!.r!, um die Einträge des Pascalschen Dreiecks zu berechnen.
• Sie haben dann eine rekursive Implementierung der Funktion gelernt.
• Schließlich lernten Sie die optimale Methode zur Konstruktion des Pascalschen Dreiecks für numRows bis zu 5 kennen, indem Sie die Potenzen von 11 verwendeten.

Wenn Sie Ihre Python-Kenntnisse vertiefen möchten, lernen Sie, Matrizen zu multiplizieren, zu prüfen, ob eine Zahl eine Primzahl ist, und Probleme mit String-Operationen zu lösen. Viel Spaß beim Programmieren!