Cum să imprimați triunghiul lui Pascal în Python

Cuprins

Acest ghid îți va explica cum să afișezi triunghiul lui Pascal în Python, specificând un număr de linii dorit.

Vei începe prin a înțelege cum se construiește triunghiul lui Pascal. Apoi, vei scrie o funcție în Python și vei învăța cum să o optimizezi.

▶️ Să începem aventura!

Ce este triunghiul lui Pascal și cum îl putem construi?

Generarea triunghiului lui Pascal pentru un anumit număr de linii este o problemă frecventă în interviuri.

În triunghiul lui Pascal cu ‘n’ linii, linia cu numărul ‘i’ conține ‘i’ elemente.

Astfel, prima linie are un singur element, care este 1. În liniile următoare, fiecare element este rezultatul adunării celor două numere situate direct deasupra sa.

Imaginea de mai jos ilustrează procesul de construcție al triunghiului lui Pascal, folosind cinci linii.

Triunghiul lui Pascal pentru numărul de linii = 5 (Imaginea autorului)

Observă cum se pot utiliza zerouri în cazurile în care există un singur număr deasupra unui element.

📝Ca un exercițiu rapid, încearcă să construiești triunghiul lui Pascal urmând pașii de mai sus, pentru n = 6 și n = 7.

Acum, să trecem la scrierea codului. Poți testa fragmentele de cod direct în browser, folosind un IDE Python oferit de tipstrick.ro – pe măsură ce avansezi prin acest tutorial.

Funcția Python pentru a genera triunghiul lui Pascal

În această secțiune, vom crea o funcție Python care să afișeze triunghiul lui Pascal pentru orice număr de linii specificat.

Există două aspecte cheie de luat în considerare:

Cum se calculează valorile din triunghiul lui Pascal?
Cum se afișează triunghiul lui Pascal cu spațierea și formatarea potrivită?

Să răspundem acum acestor întrebări.

#1. Cum se calculează fiecare valoare din triunghiul lui Pascal?

Valorile din triunghiul lui Pascal se obțin folosind formula pentru nCr. Dacă îți amintești de la matematică, nCr reprezintă numărul de moduri în care se pot alege r elemente dintr-un set de n elemente.

Formula pentru nCr este prezentată mai jos:

Formula nCr (Imaginea autorului)

Să exprimăm acum valorile din triunghiul lui Pascal folosind formula nCr.

Triunghiul lui Pascal folosind nCr (Imaginea autorului)

Am identificat o metodă pentru a calcula valorile matricei.

#2. Cum se ajustează spațierea în timpul afișării?

În triunghiul lui Pascal cu un număr de linii, linia #1 are o singură valoare, linia #2 are două valori și așa mai departe. Pentru a afișa modelul sub formă de triunghi, vei avea nevoie de un număr de spații egal cu numărul de linii – i, în linia #i. Se poate folosi funcția range din Python împreună cu o buclă for pentru a realiza acest lucru.

Deoarece funcția range nu include implicit punctul final, asigură-te că adaugi + 1 pentru a obține numărul corect de spații inițiale.

Acum, că știi cum să calculezi valorile și să ajustezi spațierea pentru a afișa triunghiul lui Pascal, să definim funcția pascal_tri.

Analiza definiției funcției

Deci, ce ar trebui să facă funcția pascal_tri?

Funcția pascal_tri ar trebui să primească numărul de linii (numRows) ca argument.
Ar trebui să afișeze triunghiul lui Pascal pentru numRows linii.

Pentru a calcula factorialul, vom folosi funcția factorial din modulul math încorporat în Python.

▶️ Execută următorul bloc de cod pentru a importa factorial și a-l folosi în modulul curent.

from math import factorial

Fragmentul de cod de mai jos conține definiția funcției.

def pascal_tri(numRows):
  '''Afișează triunghiul lui Pascal cu numărul de linii specificat.'''
  for i in range(numRows):
    # buclă pentru a adăuga spațiile inițiale
	  for j in range(numRows-i+1):
		  print(end=" ")
    
    # buclă pentru a obține valorile liniei i
	  for j in range(i+1):
		  # nCr = n!/((n-r)!*r!)
		  print(factorial(i)//(factorial(j)*factorial(i-j)), end=" ")

	 # afișează fiecare linie pe un rând nou
	  print("n")

Funcția funcționează astfel:

Funcția pascal_tri are un parametru obligatoriu numRows: numărul de linii.
Există un număr total de numRows linii. Pentru fiecare linie i, adăugăm numRows – i spații inițiale înainte de prima valoare a liniei.
Apoi folosim formula nCr pentru a calcula fiecare valoare. Pentru linia i, valorile sunt iCj, unde j = {0,1,2,..,i}.
Observă că folosim // pentru a efectua împărțirea întreagă, deoarece dorim ca valorile să fie numere întregi.
După calcularea tuturor valorilor într-o linie, afișăm următoarea linie pe un rând nou.

🔗 Deoarece am adăugat un docstring, poți folosi funcția help încorporată în Python sau atributul __doc__ pentru a accesa șirul de documentare al funcției. Fragmentul de cod de mai jos demonstrează cum se face acest lucru.

help(pascal_tri)

# Rezultat
Help on function pascal_tri in module __main__:

pascal_tri(numRows)
    Afișează triunghiul lui Pascal cu numărul de linii specificat.

pascal_tri.__doc__

# Rezultat
Afișează triunghiul lui Pascal cu numărul de linii specificat.

Acum să apelăm funcția cu numărul de linii ca argument.

pascal_tri(3)

# Rezultat
     1
    1 1
   1 2 1

Primele 3 linii ale triunghiului lui Pascal sunt afișate, conform așteptărilor.

Afișarea triunghiului lui Pascal folosind recursivitatea

În secțiunea anterioară, am identificat expresia matematică pentru fiecare valoare din triunghiul lui Pascal. Cu toate acestea, nu am folosit relația dintre valorile din două linii consecutive.

De fapt, am folosit linia anterioară pentru a calcula valorile din linia următoare. Nu putem folosi acest lucru și să creăm o implementare recursivă a funcției pascal_tri?

Da, hai să încercăm!

Într-o implementare recursivă, o funcție se autoapelează în mod repetat, până când este îndeplinit cazul de bază. În construirea triunghiului lui Pascal, începem cu prima linie, care conține valoarea 1, și apoi construim liniile următoare.

Astfel, apelul funcției pascal_tri(numRows) apelează la rândul său pascal_tri(numRows-1) și așa mai departe, până când se atinge cazul de bază pascal_tri(1).

Consideră exemplul în care trebuie să afișezi primele 3 linii ale triunghiului lui Pascal. Următoarea imagine explică modul în care apelurile recursive sunt stocate în stivă. Și cum apelurile funcției recursive returnează liniile triunghiului lui Pascal.

Stiva de apeluri în timpul apelurilor recursive (Imaginea autorului)

▶️ Execută fragmentul de cod de mai jos pentru a genera recursiv liniile triunghiului lui Pascal.

def pascal_tri(numRows):
    '''Afișează triunghiul lui Pascal cu numărul de linii specificat.'''
    if numRows == 1:
        return [[1]] # cazul de bază a fost atins!
    else:
        res_arr = pascal_tri(numRows-1) # apel recursiv la pascal_tri
        # folosește linia anterioară pentru a calcula linia curentă
        cur_row = [1] # fiecare linie începe cu 1
        prev_row = res_arr[-1]
        for i in range(len(prev_row)-1):
            # suma a 2 valori direct deasupra
            cur_row.append(prev_row[i] + prev_row[i+1])
        cur_row += [1] # fiecare linie se termină cu 1
        res_arr.append(cur_row)
        return res_arr

Iată câteva aspecte de reținut:

Am folosit o listă imbricată ca structură de date, unde fiecare linie din triunghiul lui Pascal este o listă în sine, astfel: [[linia 1], [linia 2],…,[linia n]].
Apelul funcției pascal_tri(numRows) declanșează o serie de apeluri recursive cu numRows – 1, numRows – 2 până la 1 ca argumente. Aceste apeluri sunt stocate într-o stivă.
Când numRows == 1, ajungem la cazul de bază, iar funcția returnează [[1]].
Acum, lista returnată este folosită de funcțiile anterioare din stiva de apeluri – pentru a calcula următoarea linie.
Dacă cur_row este linia curentă, cur_row[i] = linia_anterioară[i] + prev_row[i+1] — suma a 2 elemente aflate direct deasupra indexului curent.

Deoarece matricea returnată este o listă imbricată (listă de liste), trebuie să ajustăm spațierea și să afișăm valorile, așa cum se arată în blocul de cod de mai jos.

tri_array = pascal_tri(5)

for i,row in enumerate(tri_array):
  for j in range(len(tri_array) - i + 1):
    print(end=" ") # spații inițiale
  for j in row:
    print(j, end=" ") # afișarea valorilor
  print("n")  # afișarea unei linii noi

Rezultatul este corect, după cum se poate observa mai jos!

Funcția Python pentru a afișa triunghiul lui Pascal pentru numRows ≤ 5

Ambele metode pe care le-ai învățat vor funcționa pentru a afișa triunghiul lui Pascal pentru un număr arbitrar de linii, numRows.

Cu toate acestea, există situații când trebuie să afișezi triunghiul lui Pascal pentru un număr mai mic de linii. Și când numărul de linii pe care trebuie să le afișezi este de cel mult 5, poți folosi o tehnică simplă.

Analizează imaginea de mai jos. Și observă cum puterile lui 11 sunt identice cu valorile din triunghiul lui Pascal. De asemenea, observă că această metodă funcționează doar până la a 4-a putere a lui 11. Adică, 11 ridicat la puterile {0, 1, 2, 3, 4} oferă valorile din liniile 1 până la 5 ale triunghiului lui Pascal.

Să rescriem definiția funcției, după cum se arată mai jos:

def pascal_tri(numRows):
  '''Afișează triunghiul lui Pascal cu numărul de linii specificat.'''
  for i in range(numRows):
    print(' '*(numRows-i), end='')
    # calculează puterea lui 11
    print(' '.join(str(11**i)))

Iată cum funcționează funcția pascal_tri:

Ca și în exemplele anterioare, ajustăm spațierea.
Apoi, folosim operatorul de exponențiere din Python (**) pentru a calcula puterile lui 11.
Deoarece puterile lui 11 sunt implicit numere întregi, le convertim la șir folosind str(). Acum ai puterile lui 11 ca șiruri.
Șirurile în Python sunt iterabile, astfel că le poți parcurge și accesa caracter cu caracter.
Apoi, poți folosi metoda join() cu sintaxa: <sep>.join(<iterabil>) pentru a uni elementele din <iterabil> folosind <sep> ca separator.
Aici, ai nevoie de un singur spațiu între caractere, deci <sep> va fi „ „, iar <iterabil> este șirul: puterea lui 11.

Să verificăm dacă funcția funcționează conform intențiilor.

pascal_tri(5)

# Rezultat
     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

Ca un alt exemplu, apelează funcția pascal_tri cu 4 ca argument.

pascal_tri(4)

# Rezultat
     1
    1 1
   1 2 1
  1 3 3 1

Sper că ai înțeles cum poți afișa cu ușurință triunghiul lui Pascal pentru numRows în intervalul de la 1 la 5.

Concluzie

Iată ce am învățat:

Cum să construiești triunghiul lui Pascal pentru un număr dat de linii. Fiecare număr din fiecare linie este suma celor două numere aflate direct deasupra sa.
Să scrii o funcție Python folosind formula nCr = n!/(n-r)!.r! pentru a calcula valorile triunghiului lui Pascal.
Apoi, ai învățat o implementare recursivă a funcției.
În final, ai învățat metoda cea mai optimă pentru a construi triunghiul lui Pascal pentru un număr de linii de până la 5 – folosind puterile lui 11.

Dacă vrei să îți dezvolți abilitățile în Python, învață cum să înmulțești matrice, cum să verifici dacă un număr este prim și cum să rezolvi probleme cu operații pe șiruri. Spor la codat!