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

przez

Ten samouczek nauczy Cię, jak wydrukować trójkąt Pascala w Pythonie dla określonej liczby wierszy.

Zaczniesz od nauki budowy trójkąta Pascala. Następnie przejdziesz do napisania funkcji Pythona i nauczysz się ją dalej optymalizować.

▶️ Zacznijmy!

Co to jest trójkąt Pascala i jak go skonstruować?

Popularnym pytaniem podczas rozmowy kwalifikacyjnej jest wydrukowanie trójkąta Pascala dla określonej liczby wierszy.

W trójkącie Pascala z n wierszami, wiersz numer i ma i elementów.

Tak więc pierwszy wiersz ma jeden element i to 1. Każdy element w kolejnych wierszach to suma dwóch liczb bezpośrednio nad nim.

Poniższy rysunek wyjaśnia, jak skonstruować trójkąt Pascala z pięcioma rzędami.

Trójkąt Pascala dla numRows = 5 (zdjęcie autora)

Zwróć uwagę, jak możesz uzupełnić zera, gdy masz tylko jedną liczbę powyżej pewnej liczby.

📝Jako szybkie ćwiczenie, wykonaj powyższą procedurę, aby skonstruować trójkąt Pascala dla n = 6 i n = 7.

Następnie przejdźmy do napisania kodu. Możesz uruchomić fragmenty kodu w środowisku IDE Pythona newsblog.pl bezpośrednio z przeglądarki — podczas przechodzenia przez samouczek.

Funkcja Pythona do drukowania trójkąta Pascala

W tej sekcji napiszemy funkcję Pythona wyświetlającą trójkąt Pascala dla dowolnej liczby wierszy.

Należy rozważyć dwa kluczowe pytania:

  • Jak wyrazić wpisy w trójkącie Pascala?
  • Jak wydrukować trójkąt Pascala z odpowiednimi odstępami i formatowaniem?

Odpowiedzmy na nie teraz.

#1. Jakie jest wyrażenie dla każdego wpisu w trójkącie Pascala?

Tak się składa, że ​​wpisy w trójkącie Pascala można otrzymać ze wzoru na nCr. Jeśli przypomnisz sobie ze szkolnej matematyki, nCr oznacza liczbę sposobów, w jakie możesz wybrać r elementów ze zbioru n elementów.

Wzór na nCr podano poniżej:

formuła nCr (zdjęcie autora)

Przejdźmy teraz do wyrażenia wpisów w trójkącie Pascala za pomocą wzoru nCr.

Wpisy trójkąta Pascala za pomocą nCr (zdjęcie autora)

Znaleźliśmy teraz sposób na wyrażenie wpisów w macierzy.

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

W trójkącie Pascala z numRows wiersz #1 ma jeden wpis, wiersz #2 ma dwa wpisy i tak dalej. Aby wydrukować wzór jako trójkąt, potrzebujesz numRows – i spacji w wierszu #i. Aby to zrobić, możesz użyć funkcji zakresu Pythona w połączeniu z pętlą for.

Ponieważ funkcja zakresu domyślnie wyklucza punkt końcowy, należy dodać + 1, aby uzyskać wymaganą liczbę spacji wiodących.

Teraz, gdy nauczyłeś się, jak reprezentować wpisy, a także dostosowywać odstępy podczas drukowania trójkąta Pascala, przejdźmy dalej i zdefiniujmy funkcję pascal_tri.

Analiza definicji funkcji

Więc co chcesz, aby funkcja pascal_tri zrobiła?

  • Funkcja pascal_tri powinna przyjąć jako argument liczbę wierszy (numRows).
  • Powinien wydrukować trójkąt Pascala z numRows.

Aby obliczyć silnię, użyjmy funkcji silni z wbudowanego modułu matematycznego Pythona.

▶️ Uruchom następującą komórkę kodu, aby zaimportować silnię i użyć jej w bieżącym module.

from math import factorial

Poniższy fragment kodu zawiera definicję funkcji.

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")

Funkcja działa w następujący sposób:

  • Funkcja pascal_tri ma jeden wymagany parametr numRows: liczbę wierszy.
  • W sumie są wiersze numRows. Dla każdego i wiersza dodajemy numRows – i wiodące spacje przed pierwszym wpisem w wierszu.
  • Następnie używamy formuły nCr do obliczenia poszczególnych wpisów. W wierszu i wpisy to iCj, gdzie j = {0,1,2,…,i}.
  • Zauważ, że używamy //, który wykonuje dzielenie liczb całkowitych, ponieważ chcielibyśmy, aby wpisy były liczbami całkowitymi.
  • Po obliczeniu wszystkich wpisów w wierszu, wypisz następny wiersz w nowej linii.

🔗 Jak dodaliśmy dokumentacja, możesz użyć wbudowanej funkcji pomocy Pythona lub atrybutu __doc__, aby uzyskać dostęp do ciągu dokumentacyjnego funkcji. Poniższy fragment kodu pokazuje, jak to zrobić.

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.

Teraz przejdźmy dalej i wywołajmy funkcję z liczbą wierszy jako argumentem.

pascal_tri(3)

# Output
     1
    1 1
   1 2 1

Zgodnie z oczekiwaniami drukowane są pierwsze 3 rzędy trójkąta Pascala.

Wydrukuj trójkąt Pascala za pomocą rekurencji

W poprzedniej sekcji zidentyfikowaliśmy matematyczne wyrażenie każdego wpisu w trójkącie Pascala. Nie wykorzystaliśmy jednak relacji między wpisami w dwóch kolejnych wierszach.

W rzeczywistości użyliśmy poprzedniego wiersza do obliczenia wpisów w kolejnym wierszu. Czy nie możemy tego użyć i wymyślić rekurencyjną implementację funkcji pascal_tri?

Tak, zróbmy to!

W implementacji rekurencyjnej funkcja wielokrotnie wywołuje samą siebie, dopóki nie zostanie spełniony przypadek podstawowy. W konstrukcji trójkąta Pascala zaczynamy od pierwszego rzędu z jednym wpisem 1, a następnie budujemy kolejne rzędy.

Tak więc wywołanie funkcji pascal_tri(numRows) z kolei wywołuje pascal_tri(numRows-1) i tak dalej, aż do osiągnięcia bazowego przypadku pascal_tri(1).

Rozważ przykład, w którym musisz wydrukować pierwsze 3 rzędy trójkąta Pascala. Poniższy obraz wyjaśnia, w jaki sposób wywołania cykliczne są wypychane na stos. I jak rekurencyjne wywołania funkcji zwracają wiersze trójkąta Pascala.

Stos wywołań podczas wywołań rekurencyjnych (zdjęcie autora)

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

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

Oto kilka punktów, na które warto zwrócić uwagę:

  • Użyliśmy listy zagnieżdżonej jako struktury danych, gdzie każdy wiersz w trójkącie Pascala jest listą samą w sobie, tak jak poniżej: [[row 1], [row 2],…,[row n]].
  • Wywołanie funkcji pascal_tri(numRows) wyzwala serię rekurencyjnych wywołań z argumentami numRows – 1, numRows – 2 aż do 1. Te wywołania są umieszczane na stosie.
  • Gdy numRows == 1, dotarliśmy do przypadku podstawowego i funkcja zwraca [[1]].
  • Teraz zwrócona lista jest używana przez kolejne funkcje na stosie wywołań — do obliczenia następnego wiersza.
  • Jeśli cur_row jest bieżącym wierszem, cur_row[i] = poprzedni_wiersz[i] + poprzedni_wiersz[i+1]—suma 2 elementów bezpośrednio nad bieżącym indeksem.

Ponieważ zwrócona tablica jest listą zagnieżdżoną (listą list), musimy dostosować odstępy i wydrukować wpisy, jak pokazano w komórce kodu poniżej.

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

Wynik jest prawidłowy, jak widać poniżej!

# Output

       1

      1 1

     1 2 1

    1 3 3 1

   1 4 6 4 1

Funkcja Pythona do drukowania trójkąta Pascala dla numRows ≤ 5

Obie metody, których się nauczyłeś, będą działać przy wyświetlaniu trójkąta Pascala dla dowolnej liczby wierszy numRows.

Jednak są chwile, kiedy trzeba wydrukować trójkąt Pascala dla mniejszej liczby wierszy. A gdy liczba wierszy, które musisz wydrukować, wynosi najwyżej 5 – możesz użyć prostej techniki.

Przejdź przez poniższy rysunek. I obserwuj, jak potęgi 11 są identyczne z wpisami w trójkącie Pascala. Zauważ też, że działa to tylko do czwartej potęgi liczby 11. To znaczy, że 11 podniesione do potęg {0, 1, 2, 3, 4} daje wpisy w rzędach od 1 do 5 trójkąta Pascala.

Przepiszmy definicję funkcji, jak pokazano poniżej:

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)))

Oto jak działa funkcja pascal_tri:

  • Podobnie jak w poprzednich przykładach, dostosowujemy odstępy.
  • Następnie używamy operatora potęgowania Pythona (**), aby obliczyć potęgi liczby 11.
  • Ponieważ potęgi 11 są domyślnie liczbami całkowitymi, przekonwertuj je na łańcuch za pomocą str(). Masz teraz moc 11 jako ciągi.
  • Łańcuchy w Pythonie są iterowalne — możesz więc przechodzić przez nie i uzyskiwać dostęp do jednego znaku na raz.
  • Następnie możesz użyć metody join() ze składnią: .join(), aby połączyć elementy w używając jako separatora.
  • Tutaj potrzebujesz pojedynczej spacji między znakami, więc będzie ’ ’, to ciąg znaków: potęga 11.

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

pascal_tri(5)

# Output
     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

Jako inny przykład, wywołaj funkcję pascal_tri z 4 jako argumentem.

pascal_tri(4)

# Output
     1
    1 1
   1 2 1
  1 3 3 1

Mam nadzieję, że wiesz, jak łatwo wydrukować trójkąt Pascala dla numRows w zakresie od 1 do 5.

Wniosek

Oto, czego się nauczyliśmy:

  • Jak skonstruować trójkąt Pascala z podaną liczbą rzędów. Każda liczba w każdym rzędzie jest sumą dwóch liczb bezpośrednio nad nią.
  • Napisz funkcję Pythona używając formuły nCr = n!/(nr)!.r! aby obliczyć wpisy trójkąta Pascala.
  • Następnie nauczyłeś się rekurencyjnej implementacji funkcji.
  • Wreszcie poznałeś najbardziej optymalną metodę konstruowania trójkąta Pascala dla numRows do 5 — przy użyciu potęgi 11.

Jeśli chcesz podnieść poziom umiejętności Pythona, naucz się mnożyć macierze, sprawdzać, czy liczba jest liczbą pierwszą i rozwiązywać problemy związane z operacjami na ciągach. Udanego kodowania!