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!
# Wynik
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
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!
newsblog.pl