Hur man skriver ut Pascals triangel i Python

Denna handledning kommer att lära dig hur du skriver ut Pascals triangel i Python för ett givet antal rader.

Du börjar med att lära dig att konstruera Pascals triangel. Du kommer sedan att fortsätta med att skriva en Python-funktion och lära dig att optimera den ytterligare.

▶️ Låt oss börja!

Innehållsförteckning

Vad är Pascals triangel och hur man konstruerar den?

Att skriva ut Pascals triangel för ett givet antal rader är en populär intervjufråga.

I Pascals triangel med n rader har radnummer i i-element.

Så den första raden har ett element, och det är 1. Och varje element i efterföljande rader är summan av de två talen direkt ovanför det.

Följande figur förklarar hur man konstruerar Pascals triangel med fem rader.

Pascals triangel för numRows = 5 (Bild av författaren)

Lägg märke till hur du kan sätta nollor när du bara har ett nummer över ett visst nummer.

📝Som en snabb övning, följ proceduren ovan för att konstruera Pascals triangel för n = 6 och n = 7.

Låt oss sedan fortsätta att skriva lite kod. Du kan välja att köra kodavsnitten på adminvista.com’s Python IDE direkt från din webbläsare – när du arbetar dig igenom handledningen.

Python-funktion för att skriva ut Pascals triangel

Låt oss i det här avsnittet skriva en Python-funktion för att skriva ut Pascals triangel för ett givet antal rader.

Det finns två nyckelfrågor att överväga:

Hur uttrycker man posterna i Pascals triangel?
Hur skriver man ut Pascals triangel med lämpligt mellanrum och formatering?

Låt oss svara på dem nu.

#1. Vad är uttrycket för varje post i Pascals triangel?

Det råkar vara så att posterna i Pascals triangel kan erhållas med formeln för nCr. Om du kommer ihåg matematiken från din skola, anger nCr antalet sätt du kan välja r objekt från en uppsättning av n objekt.

Formeln för nCr ges nedan:

nCr-formel (Bild av författaren)

Låt oss nu fortsätta att uttrycka posterna i Pascals triangel med nCr-formeln.

Pascals triangelposter med nCr (Bild av författaren)

Vi har nu hittat ett sätt att uttrycka posterna i matrisen.

#2. Hur justerar man avståndet när man skriver ut mönstret?

I Pascals triangel med numRows har rad #1 en post, rad #2 har två poster, och så vidare. För att skriva ut mönstret som en triangel behöver du numRows – i mellanslag i rad #i. Och du kan använda Pythons räckviddsfunktion tillsammans med for loop för att göra detta.

Eftersom intervallfunktionen exkluderar slutpunkten som standard, se till att lägga till +1 för att få det nödvändiga antalet inledande blanksteg.

Nu när du har lärt dig att representera poster och även att justera utrymmet medan du skriver ut Pascals triangel, låt oss gå vidare och definiera funktionen pascal_tri.

Analysera funktionsdefinitionen

Så vad vill du att funktionen pascal_tri ska göra?

Funktionen pascal_tri bör acceptera antalet rader (numRows) som argument.
Den ska skriva ut Pascals triangel med numRows.

För att beräkna faktorialen, låt oss använda faktorialfunktionen från Pythons inbyggda matematikmodul.

▶️ Kör följande kodcell för att importera factorial och använd den i din nuvarande modul.

from math import factorial

Kodavsnittet nedan innehåller funktionsdefinitionen.

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

Funktionen fungerar enligt följande:

Funktionen pascal_tri har en obligatorisk parameter numRows: antalet rader.
Det finns numRows rader totalt. För varje rad i lägger vi till numRows – i ledande mellanslag före den första posten i raden.
Vi använder sedan nCr-formeln för att beräkna de individuella posterna. För rad i är posterna iCj där j = {0,1,2,..,i}.
Observera att vi använder // som utför heltalsdelning, eftersom vi vill att posterna ska vara heltal.
Efter att ha beräknat alla poster i en rad, skriv ut nästa rad på en ny rad.

🔗 Som vi har lagt till en docstring, kan du använda Pythons inbyggda hjälpfunktion, eller attributet __doc__ för att komma åt funktionens docstring. Kodavsnittet nedan visar hur man gör.

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.

Låt oss nu gå vidare och anropa funktionen med antalet rader som argument.

pascal_tri(3)

# Output
     1
    1 1
   1 2 1

De första 3 raderna av Pascals triangel skrivs ut som förväntat.

Skriv ut Pascals triangel med hjälp av rekursion

I föregående avsnitt identifierade vi det matematiska uttrycket för varje post i Pascaltriangeln. Däremot använde vi inte förhållandet mellan poster i två på varandra följande rader.

Faktum är att vi använde föregående rad för att beräkna posterna i den efterföljande raden. Kan vi inte använda detta och komma på en rekursiv implementering av funktionen pascal_tri?

Ja, låt oss göra det!

I en rekursiv implementering anropar en funktion sig själv upprepade gånger tills basfallet är uppfyllt. I konstruktionen av Pascals triangel börjar vi med den första raden med en post 1 och bygger sedan de efterföljande raderna.

Så funktionsanropet till pascal_tri(antalRows) anropar i sin tur pascal_tri(antalRows-1) och så vidare, tills basfallet pascal_tri(1) nås.

Tänk på exemplet där du behöver skriva ut de första 3 raderna av Pascals triangel. Följande bild förklarar hur de rekursiva anropen skjuts till stacken. Och hur de rekursiva funktionen anrop returnerar raderna i Pascals triangel.

Samtalsstack under rekursiva samtal (Bild av författaren)

▶️ Kör kodavsnittet nedan för att generera raderna i Pascals triangel rekursivt.

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

Här är några punkter värda att notera:

Vi har använt en kapslad lista som datastruktur, där varje rad i Pascals triangel är en lista i sig, så här: [[row 1], [row 2],…,[row n]].
Funktionsanropet pascal_tri(numRows) utlöser en serie rekursiva anrop med numRows – 1, numRows – 2 hela vägen upp till 1 som argument. Dessa samtal skjuts upp på en stack.
När numRows == 1 har vi nått basfallet och funktionen returnerar [[1]].
Nu används den returnerade listan av de efterföljande funktionerna i anropsstacken – för att beräkna nästa rad.
Om cur_row är den aktuella raden, cur_row[i] = prev_row[i] + prev_row[i+1]— summan av 2 element direkt ovanför det aktuella indexet.

Eftersom den returnerade arrayen är en kapslad lista (lista med listor), måste vi justera avståndet och skriva ut posterna, som visas i kodcellen nedan.

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

Utgången är korrekt, som ses nedan!

Python-funktion för att skriva ut Pascals triangel för antal rader ≤ 5

Båda metoderna som du har lärt dig kommer att fungera för att skriva ut Pascals triangel för ett godtyckligt antal rader numRows.

Det finns dock tillfällen då du behöver skriva ut Pascals triangel för ett mindre antal rader. Och när antalet rader du behöver skriva ut är högst 5—du kan använda en enkel teknik.

Gå igenom figuren nedan. Och observera hur potenserna av 11 är identiska med posterna i Pascals triangel. Observera också att detta bara fungerar upp till 4:e potensen av 11. Det vill säga, 11 upphöjd till potenserna {0, 1, 2, 3, 4} ger posterna i raderna 1 till 5 i Pascals triangel.

Låt oss skriva om funktionsdefinitionen, som visas nedan:

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

Så här fungerar funktionen pascal_tri:

Som med de tidigare exemplen justerar vi avståndet.
Och sedan använder vi Pythons exponentieringsoperator (**) för att beräkna potenserna 11.
Eftersom potenserna 11 är heltal som standard, konvertera dem till en sträng med str(). Du har nu potenserna 11 som strängar.
Strängar i Python är itererbara – så att du kan gå igenom dem och komma åt ett tecken åt gången.
Därefter kan du använda metoden join() med syntaxen: .join() för att sammanfoga element i med som separator.
Här behöver du ett enda mellanslag mellan tecknen, så blir ’ ’, är sträng: potens av 11.

Låt oss kolla om funktionen fungerar som den ska.

pascal_tri(5)

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

Som ett annat exempel, anrop funktionen pascal_tri med 4 som argument.

pascal_tri(4)

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

Jag hoppas att du förstår hur du enkelt kan skriva ut Pascal-triangeln för numRows i intervallet 1 till 5.

Slutsats

Här är vad vi har lärt oss:

Hur man konstruerar Pascals triangel med det givna antalet rader. Varje tal i varje rad är summan av de två talen direkt ovanför den.
Skriv en Python-funktion med formeln nCr = n!/(nr)!.r! för att beräkna posterna i Pascals triangel.
Du lärde dig sedan en rekursiv implementering av funktionen.
Slutligen lärde du dig den mest optimala metoden för att konstruera Pascals triangel för antal rader upp till 5 – med hjälp av potenserna 11.

Om du vill höja Python-färdigheterna, lär dig att multiplicera matriser, kontrollera om ett tal är primtal och lös problem med strängoperationer. Glad kodning!