Jak vytisknout Pascalův trojúhelník v Pythonu

Obsah

Tento návod vás provede procesem, jak v jazyce Python vygenerovat a zobrazit Pascalův trojúhelník pro zadaný počet řádků.

Nejprve si objasníme, jak se Pascalův trojúhelník konstruuje. Poté se podíváme na implementaci funkce v Pythonu a následně prozkoumáme možnosti její optimalizace.

🚀 Začněme!

Co je Pascalův trojúhelník a jak se tvoří?

Zobrazení Pascalova trojúhelníku pro konkrétní počet řádků je oblíbenou úlohou při programovacích pohovorech.

V Pascalově trojúhelníku s počtem řádků n obsahuje řádek číslo i právě i prvků.

První řádek tedy obsahuje jediný prvek, a to číslo 1. Každý prvek v dalších řádcích se získá jako součet dvou čísel, která se nacházejí přímo nad ním.

Následující obrázek ilustruje, jak se vytváří Pascalův trojúhelník s pěti řádky.

Pascalův trojúhelník pro numRows = 5 (zdroj: autor)

Všimněte si, že prázdná místa nad čísly lze pro výpočet považovat za nuly.

📝Pro procvičení si zkuste sami sestrojit Pascalův trojúhelník pro n = 6 a n = 7 podle výše uvedeného postupu.

Nyní se podívejme na kód. Úryvky kódu můžete zkoušet přímo ve vašem prohlížeči s pomocí Wdzwdz Python IDE.

Python funkce pro výpis Pascalova trojúhelníku

V této části vytvoříme funkci v Pythonu, která zobrazí Pascalův trojúhelník pro libovolný počet řádků.

Zamyslíme se nad dvěma klíčovými body:

Jak matematicky vyjádřit prvky v Pascalově trojúhelníku?
Jak efektivně zobrazit Pascalův trojúhelník s ohledem na správné mezery a formátování?

Podívejme se na ně detailněji.

#1. Jaký je matematický vzorec pro každý prvek v Pascalově trojúhelníku?

Ukazuje se, že hodnoty v Pascalově trojúhelníku lze vypočítat pomocí vzorce pro kombinace, známého jako nCr. Jak si možná vzpomínáte ze středoškolské matematiky, nCr vyjadřuje, kolika způsoby můžeme vybrat r prvků z celkového počtu n prvků.

Vzorec pro nCr je následující:

Vzorec nCr (zdroj: autor)

Nyní si ukážeme, jak pomocí vzorce nCr vyjádříme prvky v Pascalově trojúhelníku.

Pascalův trojúhelník s využitím nCr (zdroj: autor)

Tímto způsobem jsme našli matematické vyjádření prvků v matici.

#2. Jak upravit mezery při vypisování struktury?

V Pascalově trojúhelníku s počtem řádků `numRows` má řádek číslo 1 jeden prvek, řádek číslo 2 dva prvky, a tak dále. Aby se struktura vypsala jako trojúhelník, potřebujeme `numRows – i` mezer na začátku řádku číslo `i`. K tomu můžeme použít funkci `range` v Pythonu spolu s cyklem `for`.

Protože funkce `range` ve výchozím nastavení vylučuje koncový bod, musíme přidat + 1, abychom dosáhli požadovaného počtu úvodních mezer.

Nyní, když už umíme vyjádřit prvky a upravovat mezery při výpisu Pascalova trojúhelníku, můžeme definovat funkci `pascal_tri`.

Analýza definice funkce

Jaké vlastnosti by měla mít funkce `pascal_tri`?

Funkce `pascal_tri` by měla přijímat jako parametr počet řádků (`numRows`).
Měla by zobrazit Pascalův trojúhelník s počtem řádků `numRows`.

Pro výpočet faktoriálu použijeme funkci faktoriálu z vestavěného matematického modulu v Pythonu.

▶️ Spusťte následující kód pro import funkce faktoriálu a její využití.

from math import factorial

Následující úryvek kódu obsahuje definici funkce.

def pascal_tri(numRows):
  '''Zobrazí Pascalův trojúhelník s daným počtem řádků.'''
  for i in range(numRows):
    # Cyklus pro získání mezer na začátku řádku
	  for j in range(numRows-i+1):
		  print(end=" ")
    
    # Cyklus pro získání prvků řádku i
	  for j in range(i+1):
		  # nCr = n!/((n-r)!*r!)
		  print(factorial(i)//(factorial(j)*factorial(i-j)), end=" ")

	 # Každý řádek se zobrazí na novém řádku
	  print("\n")

Funkce funguje takto:

Funkce `pascal_tri` má jeden povinný parametr `numRows`, který udává počet řádků.
Celkem bude vytištěno `numRows` řádků. Pro každý řádek `i` přidáme `numRows – i` úvodních mezer před první prvek na řádku.
K výpočtu jednotlivých prvků používáme vzorec nCr. Pro řádek `i` jsou prvky `iCj`, kde `j = {0,1,2,..,i}`.
Všimněte si, že používáme operátor `//`, který provádí celočíselné dělení, protože chceme, aby byly všechny prvky celá čísla.
Po výpočtu všech prvků v řádku se přejde na nový řádek.

🔗 Jelikož jsme přidali dokumentační řetězec, můžete použít vestavěnou funkci `help()` v Pythonu, nebo atribut `__doc__` pro přístup k dokumentačnímu řetězci funkce. Následující úryvek ukazuje, jak se to dělá.

help(pascal_tri)

# Výstup
Help on function pascal_tri in module __main__:

pascal_tri(numRows)
    Zobrazí Pascalův trojúhelník s daným počtem řádků.

pascal_tri.__doc__

# Výstup
Zobrazí Pascalův trojúhelník s daným počtem řádků.

Nyní zkusme funkci zavolat s počtem řádků jako argumentem.

pascal_tri(3)

# Výstup
     1
    1 1
   1 2 1

První 3 řádky Pascalova trojúhelníku se zobrazí podle očekávání.

Výpis Pascalova trojúhelníku s využitím rekurze

V předchozí části jsme definovali matematické vyjádření každého prvku v Pascalově trojúhelníku. Nevyužili jsme však vztahu mezi prvky ve dvou po sobě jdoucích řádcích.

Ve skutečnosti se předchozí řádek využívá k výpočtu prvků v následujícím řádku. Nemůžeme toho využít k rekurzivní implementaci funkce `pascal_tri`?

Ano, můžeme!

Při rekurzivní implementaci funkce opakovaně volá sama sebe, dokud není dosaženo základního případu. Při vytváření Pascalova trojúhelníku začínáme prvním řádkem s jedním prvkem 1 a poté vytváříme další řádky.

Volání funkce `pascal_tri(numRows)` tedy volá `pascal_tri(numRows-1)` a tak dále, dokud není dosaženo základního případu `pascal_tri(1)`.

Vezměme si příklad, kdy potřebujete zobrazit první 3 řádky Pascalova trojúhelníku. Následující obrázek ilustruje, jak se rekurzivní volání ukládají do zásobníku a jak se z volání rekurzivní funkce vrací řádky Pascalova trojúhelníku.

Zásobník volání během rekurzivních volání (zdroj: autor)

▶️ Spusťte následující úryvek kódu pro rekurzivní generování řádků Pascalova trojúhelníku.

def pascal_tri(numRows):
    '''Zobrazí Pascalův trojúhelník s daným počtem řádků.'''
    if numRows == 1:
        return [[1]] # dosaženo základního případu!
    else:
        res_arr = pascal_tri(numRows-1) # rekurzivní volání pascal_tri
        # Použije předchozí řádek k výpočtu aktuálního řádku
        cur_row = [1] # každý řádek začíná 1
        prev_row = res_arr[-1]
        for i in range(len(prev_row)-1):
            # součet 2 prvků přímo nad
            cur_row.append(prev_row[i] + prev_row[i+1])
        cur_row += [1] # každý řádek končí 1
        res_arr.append(cur_row)
        return res_arr

Několik poznámek:

Jako datovou strukturu jsme použili vnořený seznam, kde každý řádek v Pascalově trojúhelníku je seznam sám o sobě: `[[řádek 1], [řádek 2],…,[řádek n]]`.
Volání funkce `pascal_tri(numRows)` vyvolává řadu rekurzivních volání s argumenty `numRows – 1`, `numRows – 2` až po 1. Tato volání jsou vkládána do zásobníku.
Když `numRows == 1`, dosáhli jsme základního případu a funkce vrací `[[1]]`.
Nyní se vrácený seznam využívá u funkcí v zásobníku volání k výpočtu dalšího řádku.
Pokud je aktuální řádek `cur_row`, pak `cur_row[i] = předchozí_řádek[i] + předchozí_řádek[i+1]` – součet 2 prvků přímo nad aktuálním indexem.

Jelikož je vrácené pole vnořený seznam (seznam seznamů), musíme upravit mezery a zobrazit prvky, jak je to znázorněno v následujícím úryvku kódu.

tri_array = pascal_tri(5)

for i,row in enumerate(tri_array):
  for j in range(len(tri_array) - i + 1):
    print(end=" ") # mezery na začátku
  for j in row:
    print(j, end=" ") # zobrazení prvků
  print("\n")  # nový řádek

Výstup je správný, jak můžeme vidět níže!

Python funkce pro zobrazení Pascalova trojúhelníku pro numRows ≤ 5

Obě metody, které jsme se naučili, fungují pro výpis Pascalova trojúhelníku pro libovolný počet řádků `numRows`.

Existují ale situace, kdy potřebujeme zobrazit Pascalův trojúhelník s menším počtem řádků. Pokud je počet řádků, které potřebujeme zobrazit maximálně 5, můžeme použít přímou metodu.

Podívejte se na obrázek níže. Všimněte si, jak se mocniny čísla 11 shodují s prvky v Pascalově trojúhelníku. Důležité je, že to funguje pouze do 4. mocniny čísla 11. To znamená, že 11 umocněné na {0, 1, 2, 3, 4} dá prvky v řádcích 1 až 5 Pascalova trojúhelníku.

Pojďme přepsat definici funkce tak, jak je uvedeno níže:

def pascal_tri(numRows):
  '''Zobrazí Pascalův trojúhelník s daným počtem řádků.'''
  for i in range(numRows):
    print(' '*(numRows-i), end='')
    # výpočet mocniny 11
    print(' '.join(str(11**i)))

Funkce `pascal_tri` pracuje takto:

Stejně jako v předchozích příkladech upravíme mezery.
Pak použijeme operátor umocňování (**) v Pythonu k výpočtu mocnin čísla 11.
Protože mocniny 11 jsou ve výchozím nastavení celá čísla, převedeme je na řetězec pomocí `str()`. Nyní máme mocniny 11 jako řetězce.
Řetězce v Pythonu jsou iterovatelné, takže jimi můžeme procházet a přistupovat k jednotlivým znakům.
Dále můžeme použít metodu `join()` se syntaxí: `.join()` ke spojení prvků v `` s použitím `` jako oddělovače.
Zde potřebujeme jednu mezeru mezi znaky, takže `` bude ‚ ‚, a `` je řetězec: mocnina 11.

Ověřme, že funkce funguje správně.

pascal_tri(5)

# Výstup
     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

Jako další příklad zavoláme funkci `pascal_tri` s argumentem 4.

pascal_tri(4)

# Výstup
     1
    1 1
   1 2 1
  1 3 3 1

Doufám, že nyní rozumíte tomu, jak snadno zobrazit Pascalův trojúhelník pro `numRows` v rozsahu 1 až 5.

Závěr

Co jsme se naučili:

Jak sestrojit Pascalův trojúhelník pro zadaný počet řádků. Každé číslo v daném řádku je součtem dvou čísel, která se nacházejí přímo nad ním.
Jak vytvořit funkci v Pythonu pomocí vzorce nCr = n!/(n-r)!.r! pro výpočet prvků Pascalova trojúhelníku.
Pak jsme se naučili rekurzivní implementaci funkce.
A nakonec jsme se naučili nejefektivnější metodu pro konstrukci Pascalova trojúhelníku pro počet řádků do 5 – pomocí mocnin čísla 11.

Pokud chcete vylepšit své dovednosti v Pythonu, podívejte se na násobení matic, ověření, zda je číslo prvočíslo a řešení problémů s řetězcovými operacemi. Přeji vám šťastné kódování!