V minulém díle jste viděli...

Rekurzivní funkce je taková funkce, která volá sama sebe, a to buď přímo (f → f) nebo nepřímo (f → g → h → f). Použití rekurze může v určitých případech zjednodušit řešení dané úlohy.

Obecná struktura rekurzivní funkce se skládá z následujících částí:

1. základní případ: nejjednodušší úloha, kterou lze vyřešit přímo bez použití rekurze
2. rekurzivní volání: rozdělení velké úlohy na menší části a použití stejné funkce pro vyřešení těchto menších úloh
3. rekombinace: spojení výsledků menších úloh pro vyřešení původní velké úlohy

Rekurzivní funkce pro výpočet Fibonacciho čísel (je velmi neefektivní):

def fib(n):
    if n == 0:
        # ověření první počáteční podmínky
        return 0
    elif n == 1:
        # ověření druhé počáteční podmínky
        return 1
    else:
        # rekurzivní volání pro vyřešení menších úloh
        # rekombinace a vrácení finálního výsledku
        return fib(n - 2) + fib(n - 1)

print(fib(8))

21

Efektivnější implementaci s lineární složitostí můžeme dostat pomocí iteračního přístupu:

def fib_iterative(n):
    # nastavení počátečních hodnot
    term1 = 0
    term2 = 1

    # iterační výpočet
    while n > 0:
        new = term1 + term2
        term1 = term2
        term2 = new
        n -= 1

    return term1

print(fib_iterative(8))

21

Kontejnery

Kontejner je libovolný objekt, který představuje datovou strukturu obsahující libovolný počet jiných objektů. Kontejnery poskytují způsob uchování několika objektů a přístup k nim.

Python obsahuje několik vestavěných kontejnerů, které jsou rozděleny do několika kategorií podle jejich vlastností:

Číselné typy a hodnotu None jsme viděli v minulých dílech. Poté v diagramu následují posloupnosti, zejména seznamy (list), n-tice (tuple) a stringy (str). V samostatných kategoriích jsou množinové typy (set a frozenset) a zobrazení neboli slovníky (dict). Pro úplnost jsou v diagramu kategorizace objektů i volatelné objekty (sem patří např. funkce) a moduly.

Zápis a vytváření základních kontejnerů

Základní kontejnery mají následující význam:

• string neboli textový řetězec je posloupnost znaků, v Pythonu reprezentovaná třídou str. Stringy zapisujeme typicky mezi dvojici uvozovek ("string" nebo 'string'). Podrobnosti týkající se zápisu stringů si ukážeme na příštím cvičení.
• seznam je modifikovatelná (mutable) posloupnost libovolných objektů, v Pythonu reprezentovaná třídou list.
• n-tice je nemodifikovatelná (immutable) posloupnost libovolných objektů, v Pythonu reprezentovaná třídou tuple.
• množina (třída set) je datová struktura obsahující objekty, pro které není určené jejich vzájemné pořadí.
• slovník (třída dict) je datová struktura, která představuje zobrazení z množiny klíčů (keys) na libovolné hodnoty (values).

# seznam prvků ... datový typ list
seznam_cisel = [1, 6, 56, 0, -1, 1, 6]
seznam_jmen = ["Anna","Bob","Cilka"]
prazdny_seznam = []
prazdny_seznam = list()

# objekty v seznamu nemusejí mít stejný datový typ:
seznam_ruznych_prvku = [True, 1, 3.3, 1+2j, "Tomáš", [1]]

type(seznam_cisel)

list

# výpis:
print(seznam_cisel)
print(seznam_jmen)
print(prazdny_seznam)
print(seznam_ruznych_prvku)

[1, 6, 56, 0, -1, 1, 6]
['Anna', 'Bob', 'Cilka']
[]
[True, 1, 3.3, (1+2j), 'Tomáš', [1]]

a = 0
b = "A"
seznam = [a, 1, b, "hello"]
a = 2  # změní se hodnota proměnné `a`, ale v seznamu zůstane původní hodnota
print(seznam)

[0, 1, 'A', 'hello']

# další typy kontejnerů:
a = 0
b = "A"
seznam  = [a, 1, b, 2]
ntice   = (a, b, 1, 2)
množina = {a, b, 1, 2}
string = "ahoj lidi :)  "

print("seznam: ", seznam,  type(seznam))
print("ntice:  ", ntice,   type(ntice))
print("množina:", množina, type(množina))
print("string: ", string,  type(string))

seznam:  [0, 1, 'A', 2] <class 'list'>
ntice:   (0, 'A', 1, 2) <class 'tuple'>
množina: {0, 1, 2, 'A'} <class 'set'>
string:  ahoj lidi :)   <class 'str'>

Kromě slovníků můžeme ostatní kontejnery mezi sebou jednoduše převádět pomocí příslušných funkcí (str, list, tuple, set):

seznam  = [a, 1, b, 2]
ntice   = tuple(seznam)
množina = set(seznam)
seznam1  = list(množina)
seznam2 = list(seznam)
seznam[0] = 8
print(seznam)
print(seznam2)

print("seznam: ", seznam2,  type(seznam))
print("ntice:  ", ntice,   type(ntice))
print("množina:", množina, type(množina))

[8, 1, 'A', 2]
[0, 1, 'A', 2]
seznam:  [0, 1, 'A', 2] <class 'list'>
ntice:   (0, 1, 'A', 2) <class 'tuple'>
množina: {0, 1, 2, 'A'} <class 'set'>

# konverze z textového řetězce: 

string  = "Hello, world!"

seznam  = list(string)
ntice   = tuple(string)
množina = set(string)

print("string: ", string)
print("seznam: ", seznam)
print("ntice:  ", ntice)
print("množina :", množina)

# pozor!
str1 = str(seznam)
print("string: ", str1)

string:  Hello, world!
seznam:  ['H', 'e', 'l', 'l', 'o', ',', ' ', 'w', 'o', 'r', 'l', 'd', '!']
ntice:   ('H', 'e', 'l', 'l', 'o', ',', ' ', 'w', 'o', 'r', 'l', 'd', '!')
množina : {'o', ',', ' ', '!', 'H', 'd', 'e', 'l', 'r', 'w'}
string:  ['H', 'e', 'l', 'l', 'o', ',', ' ', 'w', 'o', 'r', 'l', 'd', '!']

Předchozí výstup nám napovídá, jakým způsobem lze zapsat určitý kontejner přímo v kódu.

Poznámka: V tomto cvičení se budeme soustředit na posloupnosti, tedy seznamy a n-tice. Množiny a slovníky probereme podrobně na příštím cvičení.

Základní operace s kontejnery

Všechny kontejnery poskytují dvě základní operace:

1. Testování, jestli kontejner obsahuje danou hodnotu. Testovací výraz obsahuje operátor in, případně not in, a vrací vždy hodnotu True nebo False:

numbers = [3, 5, 7, 2, 2, 4]

print(1 in numbers)

print(1 not in  numbers)

a = 5
# podminka:
if (a in numbers):
    print("ano, je tam")
else:
    print("není tam")

False
True
ano, je tam

2. Iterování: každý kontejner lze použít jako zdroj dat v příkazu for. Zde opět vystupuje klíčové slovo in, ale v jiném významu: for hodnota in kontejner. Podle typu kontejneru mají iterované prvky buď určité nebo nespecifikované pořadí.

for x in numbers:
    print(x, end= " ")

3 5 7 2 2 4 

3. Počet prvků v kontejneru: funkce: len(kontejner).

len(numbers)

6

Kromě těchto základních operací má každý typ kontejneru své vlastní rozhraní, které jej odlišuje od ostatních. Proto si postupně probereme všechny zmíněné kontejnery.

Indexování posloupností

Předpokládejme, že máme seznam my_list definovaný následovně:

my_list = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
print(my_list[5])

60

Pro přístup k jednotlivým prvkům seznamu můžeme použít operátor [], např. my_list[i], kde i je celočíselná hodnota určující pořadí daného prvku. Přípustné hodnoty indexu i jsou znázorněny na tomto obrázku:

my_list = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

l = len(my_list)

# prvni prvek:
x = my_list[0]
print(x)

x = my_list[-10]
print(x)

x = my_list[-l]
print(x)

# pátý prvek
x = my_list[4]
print(x)


# posledni prvek:
l = len(my_list)

x = my_list[9]
print(x)

x = my_list[l-1]
print(x)

x = my_list[-1]
print(x)

# prostredni prvky (pro seznam sudé délky):
y = my_list[l//2-1]
x = my_list[l//2]
print(y,x)

10
10
10
50
100
100
50 60

my_list = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

# dvě možnosti průchodu:
for x in my_list:
    print(x, end = " ")
print(" ")

for i in range(len(my_list)):
    print(my_list[i], end = " ")    
print(" ")    

# výpis pozpátku:
for i in range(len(my_list)-1, -1, -1):
    print(my_list[i], end = " ")
print(" ")

10 20 30 40 50 60 70 80 90 100  
10 20 30 40 50 60 70 80 90 100  
100 90 80 70 60 50 40 30 20 10  
[15, 25, 35, 45, 55, 65, 75, 85, 95, 105]

# změna hodnoty:
my_list = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
my_list[5] = "ahoj"
print(my_list)
my_list[5] = 60
print(my_list)

# změna hodnoty v cyklu:
for i in range(len(my_list)):
    my_list[i] += 5

print(my_list)

# n-tice:
ntice = (1,3,5,2)
print(ntice[0])
# ntice[0] = "ahoj"  # chyba!

[10, 20, 30, 40, 50, 'ahoj', 70, 80, 90, 100]
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
[15, 25, 35, 45, 55, 65, 75, 85, 95, 105]

Tento způsob indexování funguje stejně pro všechny typy posloupností (list, tuple, str, atd). Navíc pro všechny posloupnosti můžeme použít funkci len, která vrací aktuální počet prvků v daném kontejneru. Např. pokud máme L = len(my_list), ve výrazu my_list[i] můžeme za i dosadit libovolnou hodnotu z -L, -L+1, -L+2, ..., 0, 1, 2, ..., L-2, L-1.

Známe již dva způsoby iterování přes prvky seznamu:

1. for value in my_list: – my_list slouží přímo jako zdroj dat pro příkaz for, v proměnné value dostáváme postupně hodnoty uložené v seznamu.
2. for i in range(len(my_list)): – funkce len zjistí počet prvků v seznamu a funkce range představuje posloupnost všech nezáporných hodnot, které můžeme použít pro indexování seznamu my_list. Všimněte si, že funkce range příhodně vynechává koncovou hodnotu len(my_list).

První způsob iterování je snadněji pochopitelný a vhodný pro případy, kdy potřebujeme zpracovat všechny hodnoty z určitého seznamu stejným způsobem. Druhý způsob je hůře čitelný, ale hodí se v případech, kdy potřebujeme modifikovat hodnoty uložené v modifikovatelné (mutable) posloupnosti, což není možné prvním způsobem. Např. pokud bychom chtěli všechny hodnoty v seznamu my_list zmenšit o 1:

my_list = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
# změna všech prvků seznamu:
for i in range(len(my_list)):
    my_list[i] = my_list[i] - 1

print(my_list)

[9, 19, 29, 39, 49, 59, 69, 79, 89, 99]

Slicing (výřez)

Velmi příjemným syntaktickým rozšířením indexování jednotlivých prvků posloupnosti je slicing (česky vykrajování nebo výřez). Při něm se v hranatých závorkách za názvem posloupnosti zadají dva indexy oddělené dvojtečkou, např. my_list[i:j], a výsledkem výrazu je podposloupnost daná těmito indexy:

• index i představuje počáteční index podposloupnosti
• index j představuje index „po-posledního“ prvku podposloupnosti

Není-li zadán první index, dosadí se nula, a není-li zadán druhý index, dosadí se délka posloupnosti. Bude-li proto v indexových závorkách pouze dvojtečka, výsledná podposloupnost bude celá posloupnost.

Slicing je názorně ukázán v následujícím příkladu, kde jako vstupní posloupnost používáme proměnnou python (zde string, ale stejný princip je možné aplikovat pro všechny posloupnosti):

# indexy:   0   1   2   3   4   5   6   7   8   9
#          -10 -9  -8  -7  -6  -5  -4  -3  -2  -1 
my_list = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
# výřezy: 0  1   2   3   4   5   6   7   8   9   10  
#       -10 -9  -8  -7  -6  -5  -4  -3  -2  -1   

x = my_list[3:5]
print(x)

x = my_list[ :5]
print(x)

x = my_list[ 5: ]
print(x)

x = my_list[-10:-1]
print(x)

x = my_list[-5:]
print(x)

x = my_list[: -5]
print(x)

x = my_list[ : ]   # kopie seznamu
print(x)

x = my_list[1:8:2]
print(x)

x = my_list[: :-1] # otočení seznamu
print(x)

[40, 50]
[10, 20, 30, 40, 50]
[60, 70, 80, 90, 100]
[10, 20, 30, 40, 50, 60, 70, 80, 90]
[60, 70, 80, 90, 100]
[10, 20, 30, 40, 50]
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
[20, 40, 60, 80]
[100, 90, 80, 70, 60, 50, 40, 30, 20, 10]

# vstupní posloupnost
python = "Python"

# ukázky operace slicing (mezery uvnitř hranatých závorek nehrají roli)
print(python[ 2: 5])  # "tho"
print(python[ 2:  ])  # "thon"
print(python[  : 2])  # "Py"
print(python[ 2:-1])  # "tho"
print(python[-4:-1])  # "tho"
print(python[  :-2])  # "Pyth"
print(python[-2:  ])  # "on"
print(python[  :  ])  # "Python"

tho
thon
Py
tho
tho
Pyth
on
Python

Tip: V případě operace slicing je vhodné si představit, že indexy nepředstavují pozice jednotlivých prvků posloupnosti, ale pozice mezer mezi nimi. Viz následující tabulku:

   0   1   2   3   4   5    <-- Indexování od počátku
  -6  -5  -4  -3  -2  -1    <-- Indexování od konce
 +---+---+---+---+---+---+
 | P | y | t | h | o | n |
 +---+---+---+---+---+---+
 0   1   2   3   4   5   6  <-- Slicing od počátku
-6  -5  -4  -3  -2  -1      <-- Slicing od konce

Dále si podrobněji ukážeme práci se seznamy a n-ticemi. Stringům se budeme podrobně věnovat na příštím cvičení, protože mají velmi odlišné rozhraní.

Seznamy a n-tice

Seznam (list) a n-tice (tuple) jsou datové struktury představující posloupnosti, které se ale zásadním způsobem liší:

• seznam je modifikovatelná (mutable) datová struktura – do seznamu můžeme přidávat nové objekty a nebo z něj objekty odebírat
• n-tice je nemodifikovatelná (immutable) datová struktura – nelze přidat nebo odebrat objekt v existující n-tici (jediný způsob jak změnit n-tici je vytvořit nový objekt)

Seznam se často používá v algoritmech, kde je potřeba si průběžně ukládat nějaké hodnoty a později se k nim vracet. Často začínáme s prázdným seznamem, do kterého postupně přidáváme prvky pomocí metod append (přidání na konec) nebo insert (vložení na zadanou pozici):

# prázdný seznam
seznam = []

# výpočet prvků
for i in range(10):
    if i % 2 == 0:
        # sudé číslo vložíme na konec
        seznam.append(i)
    else:
        # liché číslo vložíme na začátek
        seznam.insert(0, i)

# výpis seznamu
print(seznam)

[9, 7, 5, 3, 1, 0, 2, 4, 6, 8]

seznam_zvirat = []

# vytvořím seznam ... pridavam hodnoty na konec:
while True:
    zvire = input("zadej zvíře:")
    if (zvire == ""):
        break
    seznam_zvirat.append(zvire)
print(seznam_zvirat)    

['lev', 'tigr', 'levhart', 'orangutan']

# přidávám hodnoty na začátek:
while True:
    zvire = input("zadej zvíře:")
    if (zvire == ""):
        break
    seznam_zvirat.insert(0,zvire)

Další operace se seznamy

seznam_zvirat1 = ['zebra','žirafa','lev']
seznam_zvirat2 = ['tigr','levhart','orangutan']

# operátor + ... zřetězení seznamů
s = seznam_zvirat1 + seznam_zvirat2
print(s)

# metoda extend
s.extend(seznam_zvirat1)
print(s)

['zebra', 'žirafa', 'lev', 'tigr', 'levhart', 'orangutan']
['zebra', 'žirafa', 'lev', 'tigr', 'levhart', 'orangutan', 'zebra', 'žirafa', 'lev']

# operátor *
s = seznam_zvirat1 * 3
print(s)  

s = [0] * 10
print(s)

['zebra', 'žirafa', 'lev', 'zebra', 'žirafa', 'lev', 'zebra', 'žirafa', 'lev']
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

seznam_zvirat = ['zebra','žirafa','lev','tigr','levhart','orangutan']

# smazani prvku na indexu
del seznam_zvirat[1]
print(seznam_zvirat)

# smazání prvku podle hodnoty
if "orangutan" in seznam_zvirat:
    seznam_zvirat.remove("orangutan")
print(seznam_zvirat)

# naopak .. vložení prvku
seznam_zvirat.insert(1,"ptakopysk")
print(seznam_zvirat)

# změna prvku
seznam_zvirat[1] = "Žirafa"
print(seznam_zvirat)

['zebra', 'lev', 'tigr', 'levhart', 'orangutan']
['zebra', 'lev', 'tigr', 'levhart']
['zebra', 'ptakopysk', 'lev', 'tigr', 'levhart']
['zebra', 'Žirafa', 'lev', 'tigr', 'levhart']

# setřídění seznamu:
# vytvořím nový, setříděný seznam:
s = sorted(seznam_zvirat)
print(s)

# setřídím původní seznam:
seznam_zvirat.sort()
print(seznam_zvirat)

seznam_zvirat = ['zebra','žirafa','lev']

# kopirovani seznamu 
s = list(seznam_zvirat)
t = seznam_zvirat [ : ]
u = seznam_zvirat.copy()

# vytvoření nového odkazu na seznam
v = seznam_zvirat

print(s,t,u,v)

seznam_zvirat[2] = "myš"
del seznam_zvirat[1]

print(s,t,u,v) # s, t, u zůstanou beze změny

['zebra', 'žirafa', 'lev'] ['zebra', 'žirafa', 'lev'] ['zebra', 'žirafa', 'lev'] ['zebra', 'žirafa', 'lev']
['zebra', 'žirafa', 'lev'] ['zebra', 'žirafa', 'lev'] ['zebra', 'žirafa', 'lev'] ['zebra', 'myš']

Úplný přehled metod použitelných pro seznam (resp. každou modifikovatelnou posloupnost) je možné najít v dokumentaci.

N-tice

Naopak n-tice (tuple) se běžně používá tam, kde modifikace posloupnosti není potřeba. Jeden z typických případů jsou funkce, které vrací více než jednu hodnotu, např. funkce divmod, která vrací dvojici (tuple o dvou prvcích) hodnot, z nichž první je celočíselný podíl a druhá je zbytek po celočíselném dělení:

dvojice = divmod(11, 3)
print(dvojice)
x = dvojice[0]
y = dvojice[1]
print(x, y)

x, y = divmod(13,3)
print(x, y)

(3, 2)
3 2
4 1

K jednotlivým prvkům dvojice se dostaneme pomocí indexovacího operátoru: dvojice[0] je první prvek a dvojice[1] je druhý prvek. Protože počet prvků v n-tici nelze změnit a jednotlivé prvky je často vhodné pojmenovat pro větší přehlednost kódu, umožňuje syntaxe jazyka Python tzv. rozbalování (unpacking):

# definice trojice
point = (1, 2, 3)

print(point[2])

#point[2]=6            # chyba

# rozbalení
x, y, z = point
print(x,y,z)

3
1 2 3

# ukazka vlastni funkce:
def real_imag(z):
    return (z.real, z.imag)
    
x, y = real_imag(1+2j)

print(x,y)

1.0 2.0

Při rozbalování je potřeba zajistit, že počet proměnných definovaných na levé straně odpovídá počtu prvků v n-tici, jinak dojde k chybě ValueError. Rozbalování je možné provést obecně pro libovolnou posloupnost, ale právě kvůli zajištění odpovídajícího počtu prvků je toto použití nejtypičtější pro n-tice.

A jak vrátit více hodnot z námi definované funkce? Stačí v příkazu return zadat tuple, např. return (a, b, c) nebo ekvivalentně return a, b, c.

Příklady

1. Napište funkci, která vezme vstupní posloupnost a vrátí seznam, ve kterém jsou všechny prvky posloupnosti uspořádané pozpátku.

def pozpatku(posloupnost):
     vysledny_seznam = []
     for x in posloupnost:
         #vysledny_seznam.append(x) ... seznam by nebyl otočený
         vysledny_seznam.insert(0,x)
     return vysledny_seznam

seznam = [1, 2, 3, 3, 4, 10]
vysledek = pozpatku(seznam)
print(vysledek)
assert vysledek == [10, 4, 3, 3, 2, 1]

[10, 4, 3, 3, 2, 1]

# jiné řešení ... pomocí indexů
def pozpatku(posloupnost):
     vysledny_seznam = []
     for i in range(len(posloupnost)):
         vysledny_seznam.insert(0,posloupnost[i])
     return vysledny_seznam

seznam = [1, 2, 3, 3, 4, 10]
vysledek = pozpatku(seznam)
print(vysledek)
assert vysledek == [10, 4, 3, 3, 2, 1]

[10, 4, 3, 3, 2, 1]

# jiné řešení ... pomocí indexů
def pozpatku(posloupnost):
     vysledny_seznam = []
     for i in range(len(posloupnost)-1,-1,-1):
         vysledny_seznam.append(posloupnost[i])
     return vysledny_seznam

seznam = [1, 2, 3, 3, 4, 10]
vysledek = pozpatku(seznam)
print(vysledek)
assert vysledek == [10, 4, 3, 3, 2, 1]

[10, 4, 3, 3, 2, 1]

# jiné řešení ... pomocí výřezu
def pozpatku(posloupnost):
     vysledny_seznam = list(posloupnost[ : :-1])
     return vysledny_seznam

seznam = (1, 2, 3, 3, 4, 10)
vysledek = pozpatku(seznam)
print(vysledek)
assert vysledek == [10, 4, 3, 3, 2, 1]

[10, 4, 3, 3, 2, 1]

# jiné řešení ... pomocí metody reverse
def pozpatku(posloupnost):
     vysledny_seznam = list(posloupnost)
     vysledny_seznam.reverse()
     return vysledny_seznam

seznam = [1, 2, 3, 3, 4, 10]
vysledek = pozpatku(seznam)
print(vysledek)
assert vysledek == [10, 4, 3, 3, 2, 1]

[10, 4, 3, 3, 2, 1]

2. Napište funkci, která vrátí medián vstupní posloupnosti čísel.

def median(posloupnost):

    # nejprve posloupnost setřídím:
    s = sorted(posloupnost)
    
    l = len(s)
    if (l % 2 == 0):
        return (s[l//2] + s[l//2-1])/2
    else:
        return s[l//2]

seznam = [1, 2, 3, 4, 5]
print(median(seznam))

assert median([1, 2, 3]) == 2
assert median([1, 2]) == 1.5

3

3. Napište funkci, která přečte vstupní posloupnost přirozených čísel a vrátí seznam obsahující všechna čísla, která nejsou dělitelná 2 ani 3, v pořadí odpovídajícím vstupu.

def vyber_cisla(posloupnost):
    s = []
    for cislo in posloupnost:
        if cislo % 2 != 0 and cislo % 3 != 0:
            s.append(cislo)
    return s

assert vyber_cisla([1, 2, 3, 4, 5, 7, 4, 3, 2, 1]) == [1, 5, 7, 1]

4. Napište funkci, která vrátí seznam všech dělitelů zadaného přirozeného čísla seřazený od nejmenšího po největší.

# původní funkce, která dělitele vypisovala:
def vypis_delitele(n):
    for d in range(1,n+1):
        if n % d == 0:
            print(d, end = " " )
vypis_delitele(24)

# funkce, která místo toho vrací seznam:
def delitele(n):
    s = []
    for d in range(1,n+1):
        if n % d == 0:
            s.append(d)
    return s        
assert delitele(24) == [1, 2, 3, 4, 6, 8, 12, 24]

1 2 3 4 6 8 12 24 

5. Napište funkci, která vrátí seznam prvočísel seřazený od největšího po nejmenší, jejichž součin se rovná vstupnímu přirozenému číslu.

# původní funkce, která prvočíslený rozklad vypisovala:
def prvociselny_rozklad(n):
    for d in range(2,n+1):
        while n % d == 0:
            n = n // d
            print(d, end = " ")
prvociselny_rozklad(72)

# funkce, která místo toho vrací seznam:
def primes(n):
     s = [] 
     for d in range(2,n+1):
        while n % d == 0:
            n = n // d
            s.insert(0,d)
     return s       
assert primes(72) == [3, 3, 2, 2, 2]

2 2 2 3 3 

# alternativní řešení pomocí jednoho while-cyklu:
def prvociselny_rozklad(n):
    d = 2
    while (n > 1):
        if n % d == 0:
            print(d, end = " ")
            n = n // d
        else:
            d = d + 1
prvociselny_rozklad(72)

2 2 2 3 3 

6. Napište funkci, která pomocí Eratosthenova síta najde všechna prvočísla menší nebo rovna $n$.

def eratosthenes(n):
    ...

assert eratosthenes(11) == [2, 3, 5, 7, 11]

7. Napište funkci, která vypíše $n$ řádků Pascalova trojúhelníku. Vytvořte pomocnou funkci, která spočte nový řádek na základě předchozího.