Hvordan skrive ut Pascals trekant i Python

Denne opplæringen vil lære deg hvordan du skriver ut Pascals trekant i Python for et gitt antall rader.

Du vil begynne med å lære hvordan du konstruerer Pascals trekant. Du vil deretter fortsette å skrive en Python-funksjon og lære å optimalisere den videre.

▶️ La oss begynne!

Hva er Pascals trekant og hvordan konstrueres det?

Å skrive ut Pascals trekant for et gitt antall rader er et populært intervjuspørsmål.

I Pascals trekant med n rader har rad nummer i i-elementer.

Så den første raden har ett element, og det er 1. Og hvert element i påfølgende rader er summen av de to tallene rett over det.

Den følgende figuren forklarer hvordan man konstruerer Pascals trekant med fem rader.

Pascals trekant for numRows = 5 (Bilde av forfatteren)

Legg merke til hvordan du kan fylle nuller når du bare har ett tall over et bestemt tall.

📝Som en rask øvelse, følg prosedyren ovenfor for å konstruere Pascals trekant for n = 6 og n = 7.

Deretter fortsetter vi med å skrive litt kode. Du kan velge å kjøre kodebitene på tipsbilk.net’s Python IDE rett fra nettleseren din – mens du jobber deg gjennom veiledningen.

Python-funksjon for å skrive ut Pascals trekant

I denne delen, la oss skrive en Python-funksjon for å skrive ut Pascals trekant for et gitt antall rader.

Det er to hovedspørsmål å vurdere:

• Hvordan uttrykke oppføringene i Pascals trekant?
• Hvordan skrive ut Pascals trekant med passende mellomrom og formatering?

La oss svare på dem nå.

#1. Hva er uttrykket for hver oppføring i Pascals trekant?

Det har seg slik at oppføringene i Pascals trekant kan fås ved å bruke formelen for nCr. Hvis du husker fra skolens matematikk, angir nCr antall måter du kan velge r elementer fra et sett med n elementer.

Formelen for nCr er gitt nedenfor:

nCr formel (Bilde av forfatteren)

La oss nå fortsette å uttrykke oppføringene i Pascals trekant ved å bruke nCr-formelen.

Pascals trekantoppføringer ved hjelp av nCr (Bilde av forfatteren)

Vi har nå funnet en måte å uttrykke oppføringene i matrisen på.

#2. Hvordan justere avstanden når du skriver ut mønsteret?

I Pascals trekant med numRows har rad #1 én oppføring, rad #2 har to oppføringer, og så videre. For å skrive ut mønsteret som en trekant, trenger du numRows – i mellomrom i rad #i. Og du kan bruke Pythons rekkeviddefunksjon sammen med for loop for å gjøre dette.

Siden områdefunksjonen ekskluderer endepunktet som standard, sørg for å legge til + 1 for å få det nødvendige antallet innledende mellomrom.

Nå som du har lært hvordan du representerer oppføringer og også justere mellomrom mens du skriver ut Pascals trekant, la oss gå videre og definere funksjonen pascal_tri.

Parsing av funksjonsdefinisjonen

Så hva vil du at funksjonen pascal_tri skal gjøre?

• Funksjonen pascal_tri skal akseptere antall rader (antallRows) som argument.
• Den skal skrive ut Pascals trekant med numRows.

For å beregne faktoren, la oss bruke faktoriell funksjon fra Pythons innebygde matematikkmodul.

▶️ Kjør følgende kodecelle for å importere faktorial og bruk den i din nåværende modul.

from math import factorial

Kodebiten nedenfor inneholder funksjonsdefinisjonen.

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

Funksjonen fungerer som følger:

• Funksjonen pascal_tri har én nødvendig parameter numRows: antall rader.
• Det er numRows rader i alt. For hver rad i legger vi til numRows – i ledende mellomrom før den første oppføringen i raden.
• Vi bruker deretter nCr-formelen for å beregne de individuelle oppføringene. For rad i er oppføringene iCj hvor j = {0,1,2,..,i}.
• Legg merke til at vi bruker // som utfører heltallsdivisjon, siden vi vil at oppføringene skal være heltall.
• Etter å ha beregnet alle oppføringer i en rad, skriv ut neste rad på en ny linje.

🔗 Som vi har lagt til en docstring, kan du bruke Pythons innebygde hjelpefunksjon, eller __doc__-attributtet for å få tilgang til funksjonens docstring. Kodebiten nedenfor viser hvordan du gjø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.

La oss nå gå videre og kalle funksjonen med antall rader som argument.

pascal_tri(3)

# Output
     1
    1 1
   1 2 1

De første 3 radene av Pascals trekant skrives ut som forventet.

Skriv ut Pascals trekant ved hjelp av rekursjon

I forrige avsnitt identifiserte vi det matematiske uttrykket for hver oppføring i Pascal-trekanten. Vi brukte imidlertid ikke forholdet mellom oppføringer i to påfølgende rader.

Faktisk brukte vi forrige rad til å beregne oppføringene i den påfølgende raden. Kan vi ikke bruke dette og komme med en rekursiv implementering av funksjonen pascal_tri?

Ja, la oss gjøre det!

I en rekursiv implementering kaller en funksjon seg selv gjentatte ganger til grunntilfellet er oppfylt. I konstruksjonen av Pascals trekant starter vi med den første raden med en oppføring 1, og bygger deretter de påfølgende radene.

Så funksjonskallet til pascal_tri(antallRows) kaller i sin tur pascal_tri(antallRows-1) og så videre, inntil basistilfellet pascal_tri(1) er nådd.

Tenk på eksempelet der du må skrive ut de første 3 radene av Pascals trekant. Følgende bilde forklarer hvordan de rekursive samtalene skyves til stabelen. Og hvordan de rekursive funksjonskallene returnerer radene i Pascals trekant.

Anropsstabel under rekursive samtaler (Bilde av forfatteren)

▶️ Kjør kodebiten nedenfor for å generere radene i 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 noen punkter det er verdt å merke seg:

• Vi har brukt en nestet liste som datastruktur, der hver rad i Pascals trekant er en liste i seg selv, slik: [[row 1], [row 2],…,[row n]].
• Funksjonskallet pascal_tri(numRows) utløser en serie rekursive anrop med numRows – 1, numRows – 2 helt opp til 1 som argumenter. Disse samtalene skyves på en stabel.
• Når numRows == 1, har vi nådd grunntallet, og funksjonen returnerer [[1]].
• Nå brukes den returnerte listen av de påfølgende funksjonene i anropsstakken – for å beregne neste rad.
• Hvis cur_row er gjeldende rad, cur_row[i] = forrige_rad[i] + prev_row[i+1]— summen av 2 elementer rett over gjeldende indeks.

Siden den returnerte matrisen er en nestet liste (liste over lister), må vi justere mellomrom og skrive ut oppføringene, 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

Utgangen er korrekt, som vist nedenfor!

# Output

       1

      1 1

     1 2 1

    1 3 3 1

   1 4 6 4 1

Python-funksjon for å skrive ut Pascals trekant for antall rader ≤ 5

Begge metodene du har lært vil fungere for å skrive ut Pascals trekant for et vilkårlig antall rader numRows.

Det er imidlertid tider når du trenger å skrive ut Pascals trekant for et mindre antall rader. Og når antallet rader du trenger å skrive ut på høyst 5 – kan du bruke en enkel teknikk.

Gå gjennom figuren nedenfor. Og observer hvordan potensene til 11 er identiske med oppføringene i Pascals trekant. Legg også merke til at dette fungerer bare opp til 4. potens av 11. Det vil si at 11 hevet til potensene {0, 1, 2, 3, 4} gir oppføringene i rad 1 til 5 i Pascals trekant.

La oss omskrive funksjonsdefinisjonen, 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)))

Slik fungerer funksjonen pascal_tri:

• Som med de forrige eksemplene, justerer vi avstanden.
• Og så bruker vi Pythons eksponentieringsoperator (**) for å beregne potensene til 11.
• Siden potensene til 11 er heltall som standard, konverter dem til en streng ved å bruke str(). Du har nå potensene 11 som strenger.
• Strenger i Python er iterable – slik at du kan gå gjennom dem og få tilgang til ett tegn om gangen.
• Deretter kan du bruke join()-metoden med syntaksen: .join() for å kombinere elementer i ved å bruke som skilletegn.
• Her trenger du et enkelt mellomrom mellom tegnene, så vil være « «, er streng: potens av 11.

La oss sjekke om funksjonen fungerer etter hensikten.

pascal_tri(5)

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

Som et annet eksempel, kall funksjonen pascal_tri med 4 som argument.

pascal_tri(4)

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

Jeg håper du forstår hvordan du enkelt kan skrive ut Pascal-trekanten for antall rader i området 1 til 5.

Konklusjon

Her er hva vi har lært:

• Hvordan konstruere Pascals trekant med gitt antall rader. Hvert tall i hver rad er summen av de to tallene rett over den.
• Skriv en Python-funksjon ved å bruke formelen nCr = n!/(nr)!.r! å beregne oppføringene til Pascals trekant.
• Du lærte da en rekursiv implementering av funksjonen.
• Til slutt lærte du den mest optimale metoden for å konstruere Pascals trekant for antall rader opp til 5 – ved å bruke potensene 11.

Hvis du ønsker å øke Python-ferdighetene, lær å multiplisere matriser, sjekk om et tall er primtall, og løs problemer med strengoperasjoner. Lykke til med koding!