Pascalův trojúhelník – druhý způsob
Na cvičení jsme počítali každý člen zvlášť pomocí kombinačních čísel. Další způsob – víme,
že seznam čísel na 1. řádku je [1], spočítáme seznam čísel v každém dalším řádku ze
známého seznamu čísel v předchozím řádku.
Kód (z přednáškových slidů):
def get_next_row(row):
next_row = [1]
for i in range(len(row)-1):
next_row.append(row[i]+row[i+1])
next_row.append(1)
return next_row
def pascal_triangle(n):
row = [1]
for i in range(n):
print(row)
row = get_next_row(row)
Komentář ke kódu: funkce pascal_triangle(n) vypisuje prvních n řádků Pascalova
trojúhelníku. Průběžně si v proměnné row udržuje seznam čísel v aktuálním řádku, na
začátku je to jednoprvkový seznam [1]. Následuje for cyklus, který se provede pro každé i
od 0 do (n-1), tedy celkem nkrát. (To je význam range(n), známe z dřívejška).
V těle for cyklu se vypíše na obrazovku aktuální řádek a potom se do proměnné row uloží
nová hodnota řádku, kterou vrátí pomocná funkce get_next_row s parametrem row
(=řádek =seznam čísel).
Funkce get_next_row(row) bere jako argument seznam čísel, který je řádkem v
Pascalově trojúhelníku, a spočítá další řádek.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
…
Jak? následující řádek bude mít o jedno číslo víc než předchozí řádek. Délka předchozího
řádku je len(row). Délka nového řádku bude len(row)+1. Na začátku nového řádku (0.
pozice) a na konci nového řádku (len(row). pozice) budou jedničky. Proto do seznamu
next_row na začátku funkce uložíme jednoprvkový seznam [1], ke kterému budeme
postupně připojovat další čísla a nakonec připojíme poslední jedničku pomocí
next_row.append(1).
Jak se vypočítají další čísla uvnitř řádku? Ve for cyklu, který proběhne (len(row)-1) krát si v
každém průběhu cyklu uložíme další číslo do nového řádku. Získáme ho jako součet i. a
(i+1). čísla z předchozího řádku.
Nakonec funkce get_next_row(row)vrací seznam next_row, který použijeme ve funkci
pascal_triangle.
Kontrolní otázky (nejdříve se zamyslete sami, pak si můžete přečíst odpověď. Pokud
odpověď není jasná, ptejte se v diskuzi a na cvičení):
• Kolik tedy nakonec je prvků v next_row na konci funkce get_next_row?
1 + počet provedení cyklu + 1 = 1 + len(row)-1 +1 = len(row) + 1
• Jak vypadá seznam next_row po provedení první iterace for cyklu v
get_next_row([1,3,3,1])?
Před cyklem jsme uložili [1], v první iteraci je i rovno 0 a přidáváme do next_row na
konec prvek row[i]+row[i+1], tedy row[0]+row[1], tedy 1+3. Celkově v next_row po první
iteraci for cyklu je zatím tento seznam: [1,4] Víme, že for cyklus bude ještě mít další
iterace a konečný seznam by měl odpovídat řádku, který následuje po 1 3 3 1 v
Pascalově trojúhelníku.
• Kolik iterací for cyklu proběhne při výpočtu get_next_row([1,3,3,1])?
range(len(row)-1) odpovídá len(row)-1 iteracím
• Proč uvnitř cyklu provádíme next_row.append(row[i]+row[i+1]) a ne
next_row.append(i+i+1)?
Protože potřebujeme spočítat součet čísel v řádku, nikoliv jejich indexů (pozic) v
seznamu. Na jednotlivá čísla v seznamu row se dostaneme pomocí indexování
row[0], row[1], ...
• Proč na konci funkce get_next_row provádíme příkaz next_row.append(1) a
ne next_row.append(row[1])?
Na konci seznamu chceme přidat jedničku a ne prvek row[1].
• Co přesně vypíše pascal_triangle(3)?
[1]
[1, 1]
[1, 2, 1]
• Můžeme si zkrátit tělo for cyklu v pascal_triangle místo
print(row)
row = get_next_row(row)
na
print(get_next_row(row))
?
Uvedená změna by vypsala příští řádek, ale nikam by si tuto hodnotu neuložila, ani by
nebyla aktualizována hodnota v proměnné row. Výpis programu by pak vypadal takto:
[1,1]
[1,1]
[1,1]
...
Takže ne, toto zkrácení nedává smysl.
• Změnil by se nějak výstup pascal_triangle, kdybychom ve for cyklu vyměnili
pořadí řádků z
print(row)
row = get_next_row(row)
na
row = get_next_row(row)
print(row)
?
Nové pořadí by způsobilo, že se nejdříve aktualizuje hodnota row a potom se teprve
vypíše. Takže by ve výpisu chyběl první řádek. Výpis pro n=3:
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]