Jak wydrukować trójkąt Pascala w Pythonie?

W tym przewodniku krok po kroku dowiesz się, jak za pomocą języka Python wygenerować i wyświetlić trójkąt Pascala dla zadanej liczby wierszy.

Na początku zgłębisz tajniki konstrukcji trójkąta Pascala. Następnie przejdziesz do praktycznego tworzenia funkcji w Pythonie, a na koniec poznasz sposoby jej optymalizacji.

▶️ Rozpocznijmy!

Czym jest trójkąt Pascala i jak go zbudować?

Jednym z popularnych zadań na rozmowach kwalifikacyjnych jest napisanie programu, który wypisze trójkąt Pascala dla określonej liczby rzędów.

W trójkącie Pascala, składającym się z n wierszy, w wierszu o numerze i znajduje się dokładnie i elementów.

Pierwszy wiersz zawiera pojedynczy element, który jest liczbą 1. Każdy kolejny element w następnych wierszach jest sumą dwóch liczb znajdujących się bezpośrednio nad nim.

Poniższa ilustracja przedstawia sposób konstruowania trójkąta Pascala składającego się z pięciu wierszy.

Trójkąt Pascala dla liczby wierszy = 5 (źródło: autor)

Zauważ, że w miejscach, gdzie nad daną liczbą znajduje się tylko jedna, uzupełniamy ją, dodając umowne zera.

📝 Dla utrwalenia, spróbuj samodzielnie zbudować trójkąt Pascala dla n = 6 oraz n = 7.

Teraz przejdźmy do pisania kodu. W trakcie lektury samouczka możesz testować fragmenty kodu bezpośrednio w przeglądarce, korzystając ze środowiska IDE Pythona dostępnego na newsblog.pl.

Funkcja w Pythonie do wyświetlania trójkąta Pascala

W tej części stworzymy funkcję w języku Python, która będzie generować trójkąt Pascala dla dowolnej ilości wierszy.

Musimy odpowiedzieć sobie na dwa kluczowe pytania:

Jak matematycznie wyrazić elementy trójkąta Pascala?
Jak poprawnie wyświetlić trójkąt Pascala, zachowując odpowiednie odstępy i formatowanie?

Spróbujmy znaleźć odpowiedzi.

#1. Jak wyrazić każdy element trójkąta Pascala za pomocą matematycznego wzoru?

Okazuje się, że wartości w trójkącie Pascala są zbieżne z wartościami otrzymywanymi za pomocą wzoru na nCr. Przypomnij sobie z lekcji matematyki, że nCr określa na ile sposobów można wybrać r elementów ze zbioru n elementów.

Wzór na nCr prezentuje się następująco:

Wzór na nCr (źródło: autor)

Przeanalizujmy teraz, jak wykorzystać wzór nCr do wyrażenia elementów trójkąta Pascala.

Elementy trójkąta Pascala z wykorzystaniem nCr (źródło: autor)

Znaleźliśmy sposób na matematyczne wyrażenie elementów w trójkącie Pascala.

#2. Jak ustawić odpowiednie odstępy podczas drukowania wzoru?

W trójkącie Pascala, składającym się z liczby wierszy numRows, w wierszu #1 znajduje się jeden element, w wierszu #2 dwa elementy, i tak dalej. Aby poprawnie wyświetlić trójkąt, potrzebujemy numRows - i spacji na początku wiersza #i. Można to osiągnąć przy użyciu funkcji range z języka Python w połączeniu z pętlą for.

Ponieważ funkcja range domyślnie wyklucza punkt końcowy, należy dodać + 1, aby otrzymać wymaganą liczbę spacji na początku wiersza.

Teraz, gdy wiemy, jak reprezentować elementy trójkąta oraz jak dostosować odstępy, możemy zdefiniować funkcję pascal_tri.

Analiza definicji funkcji

Jakie zadania ma realizować funkcja pascal_tri?

Funkcja pascal_tri powinna przyjmować jako argument liczbę wierszy (numRows).
Powinna wyświetlić trójkąt Pascala o podanej liczbie wierszy.

Do obliczenia silni wykorzystamy funkcję factorial z wbudowanego modułu matematycznego Pythona.

▶️ Uruchom poniższy kod, aby zaimportować funkcję factorial i wykorzystać ją w module.

from math import factorial

Poniższy fragment kodu prezentuje definicję funkcji.

def pascal_tri(numRows):
  '''Wyświetla trójkąt Pascala o zadanej liczbie wierszy.'''
  for i in range(numRows):
    # pętla dodająca spacje na początku wiersza
    for j in range(numRows-i+1):
      print(end=" ")
    
    # pętla generująca elementy w wierszu i
    for j in range(i+1):
      # nCr = n!/((n-r)!*r!)
      print(factorial(i)//(factorial(j)*factorial(i-j)), end=" ")

    # każdy wiersz w nowej linii
    print("n")

Oto jak działa funkcja:

Funkcja pascal_tri przyjmuje jeden wymagany parametr, numRows, określający liczbę wierszy.
Generujemy pętlę, która przechodzi przez wszystkie wiersze, od 0 do numRows. Dla każdego i-tego wiersza dodajemy numRows – i spacji przed pierwszym elementem w wierszu.
Następnie stosujemy wzór nCr, aby wyznaczyć wartości poszczególnych elementów. W i-tym wierszu wartości to iCj, gdzie j = {0,1,2,…,i}.
Używamy // do wykonania dzielenia całkowitego, ponieważ potrzebujemy wartości całkowitych.
Po wyliczeniu wszystkich elementów w wierszu przechodzimy do kolejnego wiersza.

🔗 Zgodnie ze dokumentacją, możemy korzystać z wbudowanej funkcji help Pythona lub atrybutu __doc__, by uzyskać dostęp do dokumentacji funkcji. Poniższy fragment kodu pokazuje, jak to zrobić.

help(pascal_tri)

# Wynik
Help on function pascal_tri in module __main__:

pascal_tri(numRows)
    Wyświetla trójkąt Pascala o zadanej liczbie wierszy.

pascal_tri.__doc__

# Wynik
Wyświetla trójkąt Pascala o zadanej liczbie wierszy.

Przejdźmy dalej i wywołajmy funkcję, podając liczbę wierszy jako argument.

pascal_tri(3)

# Wynik
     1
    1 1
   1 2 1

Zgodnie z oczekiwaniami, wyświetlone zostały pierwsze 3 wiersze trójkąta Pascala.

Wyświetlanie trójkąta Pascala przy użyciu rekurencji

W poprzedniej sekcji znaleźliśmy wzór matematyczny na każdy element trójkąta Pascala. Nie wykorzystaliśmy jednak relacji między elementami w dwóch kolejnych wierszach.

W istocie, do obliczenia elementów w następnym wierszu wykorzystaliśmy elementy z wiersza poprzedniego. Czy można by to wykorzystać do opracowania rekurencyjnej implementacji funkcji pascal_tri?

Tak, zróbmy to!

W implementacji rekurencyjnej funkcja wielokrotnie wywołuje samą siebie, aż do osiągnięcia przypadku podstawowego. W przypadku trójkąta Pascala zaczynamy od pierwszego wiersza z jednym elementem równym 1, a następnie budujemy kolejne wiersze.

Zatem wywołanie funkcji pascal_tri(numRows) będzie z kolei wywoływać pascal_tri(numRows-1) i tak dalej, aż do osiągnięcia przypadku podstawowego, czyli pascal_tri(1).

Spójrzmy na przykład, w którym chcemy wyświetlić pierwsze 3 wiersze trójkąta Pascala. Poniższy diagram wyjaśnia, w jaki sposób wywołania rekurencyjne są dodawane do stosu oraz jak rekurencyjne wywołania funkcji zwracają wiersze trójkąta Pascala.

Stos wywołań podczas wywołań rekurencyjnych (źródło: autor)

▶️ Uruchom poniższy kod, aby rekurencyjnie wygenerować wiersze trójkąta Pascala.

def pascal_tri(numRows):
    '''Wyświetla trójkąt Pascala o zadanej liczbie wierszy.'''
    if numRows == 1:
        return [[1]] # osiągnięto przypadek podstawowy!
    else:
        res_arr = pascal_tri(numRows-1) # rekurencyjne wywołanie funkcji pascal_tri
        # wykorzystaj poprzedni wiersz do obliczenia bieżącego
        cur_row = [1] # każdy wiersz zaczyna się od 1
        prev_row = res_arr[-1] 
        for i in range(len(prev_row)-1):
            # suma 2 elementów bezpośrednio nad
            cur_row.append(prev_row[i] + prev_row[i+1]) 
        cur_row += [1] # każdy wiersz kończy się 1
        res_arr.append(cur_row)
        return res_arr

Oto kilka ważnych kwestii:

Używamy zagnieżdżonej listy jako struktury danych, gdzie każdy wiersz w trójkącie Pascala jest oddzielną listą, tak jak poniżej: [[wiersz 1], [wiersz 2],…,[wiersz n]].
Wywołanie funkcji pascal_tri(numRows) inicjuje serię rekurencyjnych wywołań z argumentami numRows – 1, numRows – 2, aż do 1. Te wywołania są dodawane do stosu.
Gdy numRows == 1, osiągamy przypadek bazowy, a funkcja zwraca [[1]].
Teraz zwrócona lista jest wykorzystywana przez kolejne funkcje na stosie wywołań do obliczenia kolejnego wiersza.
Jeśli cur_row to bieżący wiersz, to cur_row[i] = poprzedni_wiersz[i] + poprzedni_wiersz[i+1] – suma dwóch elementów znajdujących się bezpośrednio nad bieżącym indeksem.

Ponieważ zwrócona tablica to lista zagnieżdżona (lista list), musimy odpowiednio dostosować odstępy i wyświetlić elementy, jak pokazano w poniższym fragmencie kodu.

tri_array = pascal_tri(5)

for i,row in enumerate(tri_array):
  for j in range(len(tri_array) - i + 1):
    print(end=" ") # dodaj spacje na początku
  for j in row:
    print(j, end=" ") # wyświetl elementy
  print("n")  # nowy wiersz

Wynik jest prawidłowy, jak pokazano poniżej!

Funkcja w Pythonie do wyświetlania trójkąta Pascala dla numRows ≤ 5

Obie zaprezentowane metody działają poprawnie przy wyświetlaniu trójkąta Pascala dla dowolnej liczby wierszy numRows.

Jednak czasami potrzebujemy trójkąta Pascala o mniejszej liczbie wierszy. Gdy liczba wierszy, które musimy wygenerować, nie przekracza 5, można zastosować prostą technikę.

Przeanalizujmy poniższą ilustrację. Zwróć uwagę, że potęgi liczby 11 są identyczne z elementami w trójkącie Pascala. Należy jednak pamiętać, że działa to tylko do czwartej potęgi liczby 11. Oznacza to, że 11 podniesione do potęg {0, 1, 2, 3, 4} daje wartości w wierszach od 1 do 5 trójkąta Pascala.

Przekształćmy definicję funkcji w następujący sposób:

def pascal_tri(numRows):
  '''Wyświetla trójkąt Pascala o zadanej liczbie wierszy.'''
  for i in range(numRows):
    print(' '*(numRows-i), end='')
    # oblicz potęgę 11
    print(' '.join(str(11**i)))

Tak działa funkcja pascal_tri:

Podobnie jak w poprzednich przykładach, dostosowujemy odstępy.
Następnie wykorzystujemy operator potęgowania Pythona (**), aby obliczyć potęgi liczby 11.
Ponieważ potęgi 11 są domyślnie liczbami całkowitymi, konwertujemy je na ciągi znaków przy użyciu funkcji str(). Otrzymujemy potęgę liczby 11 jako ciągi znaków.
Ciągi znaków w Pythonie są iterowalne, co oznacza, że możemy po nich przechodzić i pobierać pojedyncze znaki.
Następnie możemy wykorzystać metodę join() ze składnią: .join(), by połączyć elementy w używając jako separatora.
W tym przypadku potrzebujemy pojedynczej spacji między znakami, więc będzie równe ' ', a to ciąg znaków: potęga 11.

Sprawdźmy, czy funkcja działa zgodnie z przeznaczeniem.

pascal_tri(5)

# Wynik
     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

Dla innego przykładu, wywołajmy funkcję pascal_tri z argumentem 4.

pascal_tri(4)

# Wynik
     1
    1 1
   1 2 1
  1 3 3 1

Mam nadzieję, że teraz rozumiesz, jak łatwo można wyświetlić trójkąt Pascala dla numRows od 1 do 5.

Podsumowanie

Oto czego się nauczyliśmy:

Jak zbudować trójkąt Pascala dla podanej liczby wierszy. Każda liczba w wierszu jest sumą dwóch liczb znajdujących się bezpośrednio nad nią.
Jak napisać funkcję w Pythonie, która wykorzystuje wzór nCr = n!/(nr)!.r! do obliczania elementów trójkąta Pascala.
Następnie poznaliśmy rekurencyjną implementację funkcji.
Na koniec omówiliśmy najbardziej optymalną metodę konstruowania trójkąta Pascala dla numRows do 5, wykorzystującą potęgę liczby 11.

Jeśli chcesz rozwinąć swoje umiejętności w Pythonie, zapoznaj się z mnożeniem macierzy, sprawdzaniem, czy liczba jest liczbą pierwszą oraz rozwiązywaniem problemów związanych z operacjami na ciągach. Życzę udanego kodowania!