Sådan udskrives Pascals trekant i Python

Denne vejledning vil lære dig, hvordan du udskriver Pascals trekant i Python for et givet antal rækker.

Du vil starte med at lære at konstruere Pascals trekant. Du vil derefter fortsætte med at skrive en Python-funktion og lære at optimere den yderligere.

▶️ Lad os begynde!

Indholdsfortegnelse

Hvad er Pascals trekant og hvordan man konstruerer den?

Udskrivning af Pascals trekant for et givet antal rækker er et populært interviewspørgsmål.

I Pascals trekant med n rækker har rækkenummer i i elementer.

Så den første række har et element, og det er 1. Og hvert element i de efterfølgende rækker er summen af de to tal direkte over det.

Den følgende figur forklarer, hvordan man konstruerer Pascals trekant med fem rækker.

Pascals trekant for numRows = 5 (Billede af forfatteren)

Læg mærke til, hvordan du kan udfylde nuller, når du kun har ét tal over et bestemt tal.

📝Som en hurtig øvelse skal du følge proceduren ovenfor for at konstruere Pascals trekant for n = 6 og n = 7.

Lad os derefter fortsætte med at skrive noget kode. Du kan vælge at køre kodestykkerne på toadmin.dk’s Python IDE direkte fra din browser – mens du arbejder dig igennem selvstudiet.

Python-funktion til at udskrive Pascals trekant

Lad os i dette afsnit skrive en Python-funktion til at udskrive Pascals trekant for et givet antal rækker.

Der er to nøglespørgsmål at overveje:

Hvordan udtrykkes posterne i Pascals trekant?
Hvordan udskriver man Pascals trekant med passende mellemrum og formatering?

Lad os besvare dem nu.

#1. Hvad er udtrykket for hver post i Pascals trekant?

Det sker således, at indtastningerne i Pascals trekant kan fås ved hjælp af formlen for nCr. Hvis du husker fra din skole matematik, angiver nCr antallet af måder, du kan vælge r elementer fra et sæt af n elementer.

Formlen for nCr er givet nedenfor:

nCr formel (Billede af forfatteren)

Lad os nu fortsætte med at udtrykke indtastningerne i Pascals trekant ved hjælp af nCr-formlen.

Pascals trekantindgange ved hjælp af nCr (Billede af forfatteren)

Vi har nu fundet en måde at udtrykke indtastningerne i matrixen på.

Skjul/Vis Spotlight-søgning fra menulinjen i OS X

#2. Hvordan justerer man afstanden, når man udskriver mønsteret?

I Pascals trekant med numRows har række #1 én post, række #2 har to poster, og så videre. For at udskrive mønsteret som en trekant skal du bruge numRows – i mellemrum i række #i. Og du kan bruge Pythons rækkeviddefunktion sammen med for loop til at gøre dette.

Da områdefunktionen udelukker slutpunktet som standard, skal du sørge for at tilføje + 1 for at få det nødvendige antal indledende mellemrum.

Nu hvor du har lært, hvordan du repræsenterer indgange og også at justere mellemrummet, mens du udskriver Pascals trekant, lad os gå videre og definere funktionen pascal_tri.

Parsing af funktionsdefinitionen

Så hvad vil du have funktionen pascal_tri til at gøre?

Funktionen pascal_tri skal acceptere antallet af rækker (numRows) som argument.
Den skal udskrive Pascals trekant med numRows.

For at beregne den faktorielle funktion, lad os bruge den faktorielle funktion fra Pythons indbyggede matematikmodul.

▶️ Kør følgende kodecelle for at importere factorial og brug den i dit nuværende modul.

from math import factorial

Kodestykket nedenfor indeholder 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 fungerer som følger:

Funktionen pascal_tri har en påkrævet parameter numRows: antallet af rækker.
Der er numRows rækker i alt. For hver række i tilføjer vi numRows – i førende mellemrum før den første indtastning i rækken.
Vi bruger derefter nCr-formlen til at beregne de individuelle indtastninger. For række i er indtastningerne iCj hvor j = {0,1,2,..,i}.
Bemærk, at vi bruger //, som udfører heltalsdeling, da vi gerne vil have, at indtastningerne skal være heltal.
Efter at have beregnet alle indtastninger i en række, udskriv den næste række på en ny linje.

🔗 Som vi har tilføjet en docstring, kan du bruge Pythons indbyggede hjælpefunktion eller attributten __doc__ for at få adgang til funktionens docstring. Kodestykket nedenfor viser, hvordan du gør det.

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.

Lad os nu gå videre og kalde funktionen med antallet af rækker som argument.

pascal_tri(3)

# Output
     1
    1 1
   1 2 1

De første 3 rækker af Pascals trekant udskrives som forventet.

Hvad er Hybrid Cloud Computing?

Udskriv Pascals trekant ved hjælp af rekursion

I det foregående afsnit identificerede vi det matematiske udtryk for hver post i Pascal-trekanten. Men vi udnyttede ikke forholdet mellem posteringer i to på hinanden følgende rækker.

Faktisk brugte vi den forrige række til at beregne indtastningerne i den efterfølgende række. Kan vi ikke bruge dette og komme med en rekursiv implementering af funktionen pascal_tri?

Ja, lad os gøre det!

I en rekursiv implementering kalder en funktion sig selv gentagne gange, indtil basissagen er opfyldt. I konstruktionen af Pascals trekant starter vi med den første række med en indtastning 1, og bygger derefter de efterfølgende rækker.

Så funktionskaldet til pascal_tri(antalRows) kalder igen pascal_tri(antalRows-1) og så videre, indtil basistilfældet pascal_tri(1) er nået.

Overvej eksemplet, hvor du skal udskrive de første 3 rækker af Pascals trekant. Følgende billede forklarer, hvordan de rekursive opkald skubbes til stakken. Og hvordan de rekursive funktionskald returnerer rækkerne i Pascals trekant.

Opkaldsstak under rekursive opkald (Billede af forfatteren)

▶️ Kør kodestykket nedenfor for at generere rækkerne af Pascals trekant 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

Her er et par punkter, der er værd at bemærke:

Vi har brugt en indlejret liste som datastrukturen, hvor hver række i Pascals trekant er en liste i sig selv, som denne: [[row 1], [row 2],…,[row n]].
Funktionskaldet pascal_tri(talRows) udløser en række rekursive kald med numRows – 1, numRows – 2 helt op til 1 som argumenter. Disse opkald skubbes på en stak.
Når numRows == 1, har vi nået basiscasen, og funktionen returnerer [[1]].
Nu bruges den returnerede liste af de efterfølgende funktioner i opkaldsstakken – til at beregne den næste række.
Hvis cur_row er den aktuelle række, cur_row[i] = forrige_række[i] + prev_row[i+1]—summen af 2 elementer direkte over det aktuelle indeks.

Da det returnerede array er en indlejret liste (liste over lister), skal vi justere afstanden og udskrive indtastningerne, som vist i kodecellen nedenfor.

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

Outputtet er korrekt, som vist nedenfor!

Python-funktion til at udskrive Pascals trekant for antal rækker ≤ 5

Begge de metoder, du har lært, vil fungere til at udskrive Pascals trekant for et vilkårligt antal rækker numRows.

9 Bedste Azure Ydelsesovervågnings- og fejlfindingsværktøjer

Der er dog tidspunkter, hvor du skal udskrive Pascals trekant for et mindre antal rækker. Og når antallet af rækker, du skal udskrive, højst er 5 — kan du bruge en ligetil teknik.

Gå gennem figuren nedenfor. Og observer, hvordan potenserne af 11 er identiske med indtastningerne i Pascals trekant. Bemærk også, at dette kun virker op til 4. potens af 11. Det vil sige, at 11 hævet til potenserne {0, 1, 2, 3, 4} giver indtastningerne i række 1 til 5 i Pascals trekant.

Lad os omskrive funktionsdefinitionen, som vist nedenfor:

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ådan fungerer funktionen pascal_tri:

Som med de foregående eksempler justerer vi afstanden.
Og så bruger vi Pythons eksponentieringsoperator (**) til at beregne potenserne af 11.
Da potenserne af 11 som standard er heltal, skal du konvertere dem til en streng ved hjælp af str(). Du har nu potenserne 11 som strenge.
Strenge i Python er iterables – så du kan sløjfe gennem dem og få adgang til et tegn ad gangen.
Dernæst kan du bruge join()-metoden med syntaksen: .join() til at forbinde elementer i ved at bruge som separator.
Her skal du bruge et enkelt mellemrum mellem tegnene, så vil være ‘ ‘, er streng: potens af 11.

Lad os tjekke om funktionen virker efter hensigten.

pascal_tri(5)

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

Som et andet eksempel kan du kalde funktionen pascal_tri med 4 som argument.

pascal_tri(4)

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

Jeg håber, du forstår, hvordan du nemt kan udskrive Pascal-trekanten for numRows i området 1 til 5.

Konklusion

Her er, hvad vi har lært:

Hvordan man konstruerer Pascals trekant med det givne antal rækker. Hvert tal i hver række er summen af de to tal direkte over det.
Skriv en Python-funktion ved hjælp af formlen nCr = n!/(nr)!.r! at beregne posterne i Pascals trekant.
Du lærte derefter en rekursiv implementering af funktionen.
Til sidst lærte du den mest optimale metode til at konstruere Pascals trekant for antal rækker op til 5 – ved hjælp af potenserne 11.

Hvis du ønsker at øge Python-færdighederne, skal du lære at multiplicere matricer, kontrollere, om et tal er primtal, og løse problemer med strengoperationer. God kodning!