Cvičení č. 11 rozšířené o poznámky ze cvičení a řešení některých příkladů (ZS 2024/25)¶

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í):

In [4]:
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:

In [18]:
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).

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

In [2]:
# Toto je ukázka navíc:

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

# objekty v seznamu nemusejí mít stejný datový typ:
seznam_ruznych_prvku = [True, 1, 3.3, 1+2j, "Tomáš", [1]]
In [3]:
type(seznam_ruznych_prvku)
Out[3]:
list
In [4]:
isinstance(seznam_ruznych_prvku, list)
Out[4]:
True
In [4]:
# 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]]
In [11]:
# další typy kontejnerů:
a = 0
b = "A"
seznam  = [a, b, 3]
ntice   = (a, b, 3)
množina = {a, b, 3}
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, 'A', 3] <class 'list'>
ntice:   (0, 'A', 3) <class 'tuple'>
množina: {0, 'A', 3} <class 'set'>
string:  ahoj lidi :)   <class 'str'>
In [12]:
# kontejnery můžeme mezi sebou převádět:
seznam  = [a,  b, 3]
ntice   = tuple(seznam)
množina = set(seznam)
seznam  = list(množina)

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

seznam:  [0, 'A', 3] <class 'list'>
ntice:   (0, 'A', 3) <class 'tuple'>
množina: {0, 'A', 3} <class 'set'>
In [5]:
# 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: {'r', 'o', '!', 'H', 'l', ',', 'd', 'w', ' ', 'e'}
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. Objekty v ostatních kontejnerech nemusí být jen znaky a navíc všechny objekty v daném kontejneru nemusí mít stejný typ:

In [9]:
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
ntice = (a, b, 1, 2)
množina = {a, b, 1, 2}

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

seznam: [0, 1, 'A', 'hello']
ntice: (2, 'A', 1, 2)
množina: {'A', 1, 2}

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:
In [8]:
print(1 in [0, 1, 2])
print(1 not in [0, 1])

True
False
In [13]:
# podmínka:
s = (2, 5, 3, 21, 1)
if 38 in s:
    print("je tam")
else:
    print("neni tam")

neni tam
  1. 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í.
In [13]:
print(seznam)
for i in seznam:
    print(i)

[0, 1, 'A', 'hello']
0
1
A
hello
In [7]:
# pozor: prvky nemůžeme takto měnit:
s = [2, 5, 3, 21, 1]
for i in s:
    i += 1
print(s)

[2, 5, 3, 21, 1]

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.

  1. Počet prvků v kontejneru: funkce: len(kontejner).
In [8]:
print(len(seznam))
len(množina)

13
Out[8]:
10

Indexování posloupností¶

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

In [9]:
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)

# posledni prvek:
x = my_list[L-1]
print(x)
x = my_list[9]
print(x)
x = my_list[-1]
print(x)

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

# změním pátý prvek
my_list[4] = 120
print(my_list)

# pro n-tici:
my_tuple = (10, 20, 30, 40, 50, 60, 70, 80, 90, 100)
x = my_tuple[L-1]
print(x)

# chyba:
my_tuple[4] = 120

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

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[9], line 34
     31 print(x)
     33 # chyba:
---> 34 my_tuple[4] = 120

TypeError: 'tuple' object does not support item assignment

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:

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:

In [34]:
# dvě možnosti průchodu:
my_list = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
for x in my_list:
    print(x, end = " ")
print("")

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

10 20 30 40 50 60 70 80 90 100 
10 20 30 40 50 60 70 80 90 100
In [39]:
# výpis pozpátku:
for i in range(1, len(my_list)+1):
    print(my_list[-i], end = " ")
print("")

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

100 90 80 70 60 50 40 30 20 10 
100 90 80 70 60 50 40 30 20 10
In [10]:
# změna hodnoty v cyklu:
my_list = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
print(my_list)
for i in range(len(my_list)):
    my_list[i] -=  1

print(my_list)

[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
[9, 19, 29, 39, 49, 59, 69, 79, 89, 99]
In [12]:
# zde se hodnota nezmění:
my_list = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
print(my_list)
for x in my_list:
    x -= 1
print(my_list)

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

Slicing (výřez)¶

Velmi příjemným syntaktickým rozšířením indexování jednotlivých prvků posloupnosti je slicing (česky vykrajování). 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):

In [16]:
# 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" ... kopie

print(python[ 1 : 6 : 2])  # "yhn"
print(python[ -1 : 1 :-1])  # "noht"
print(python[ : :-1])  # otočení "nohtyP"

tho
thon
Py
tho
tho
Pyth
on
Python
yhn
noht
nohtyP

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

In [48]:
# prázdný seznam
seznam = []

# výpočet prvků
for i in range(10):
        seznam.append(i)
        #seznam.insert(0, i)

# výpis seznamu
print(seznam)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In [50]:
# prázdný seznam
seznam = []

# výpočet prvků
for i in range(10):
        #seznam.append(i)
        seznam.insert(0, i)

# výpis seznamu
print(seznam)

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
In [51]:
# 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]

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

Další operace se seznamy¶

In [18]:
# operace se seznamy: +, * aj.
s = [1, 4, 8, 2]
t = [4, 3, 6, 8]

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

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

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

[1, 4, 8, 2, 4, 3, 6, 8]
[1, 4, 8, 2, 4, 3, 6, 8, 1, 4, 8, 2]
[1, 4, 8, 2, 1, 4, 8, 2, 1, 4, 8, 2]
In [20]:
u = [1, 4, 8, 2, 4, 3, 6, 8]

# smazání prvku podle hodnoty
u.remove(4)
print(u)

# smazani prvku na indexu
del u[ : 2]
print(u)

# vložení prvku na index
u.insert(1, 45)
print(u)

# změna prvku na indexu
u[1]=123
print(u)

[1, 8, 2, 4, 3, 6, 8]
[2, 4, 3, 6, 8]
[2, 45, 4, 3, 6, 8]
[2, 123, 4, 3, 6, 8]
In [21]:
# vytvoření nového odkazu na seznam
s = [1, 5, 6, 7]
t = s
s[0] = 56
print(s)
print(t)

[56, 5, 6, 7]
[56, 5, 6, 7]
In [22]:
# kopirovani seznamu 
s = [1, 5, 6, 7]

# t = s[ : ]
# t = s.copy()
t = list(s)

s[0] = 56
print(s)
print(t)

# vytvoření nového odkazu na seznam
t = s

# otočení seznamu (na místě)
a = t.reverse()
print(t, a)

# setřídění seznamu (na místě)
a=t.sort()
print(t, a)

[56, 5, 6, 7]
[1, 5, 6, 7]
[7, 6, 5, 56] None
[5, 6, 7, 56] None
In [26]:
# setřídění seznamu:
# vytvořím nový, setříděný seznam
t = (6, 3, 9, 1)
s = sorted(t)
print(s, t)

# setřídím původní seznam (na místě):
t = [10, 5, 8]
t.sort()
print(t)

[1, 3, 6, 9] (6, 3, 9, 1)
[5, 8, 10]

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í:

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

(3, 2)
3 2
In [30]:
# zabalení a rozbalení dvojice (kulaté závorky mohu vynechat)
dvojice1 = (x, y)
print(dvojice1)

dvojice1 = x, y
print(dvojice1)

a, b = dvojice
print(a, b)

(a, b) = dvojice
print(a, b)

(3, 2)
(3, 2)
3 2
3 2
In [76]:
 x, y = divmod(11, 3)
print(x, y)

3 2

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

In [5]:
# definice trojice
point = (1, 2, 3)

# rozbalení
x, y, z = point

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.

In [57]:
# ukázka vlastní funkce
def komplexni_cislo(z):
    return z.real, z.imag

z = 1 + 2j
x, y = komplexni_cislo(z)
dvojice = komplexni_cislo(z)

print(x, y)
print(dvojice)

1.0 2.0
(1.0, 2.0)

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.
In [34]:
# řešení pomocí for-cyklu:
def pozpatku(posloupnost):
    obraceny_seznam = []
    
    for prvek in posloupnost:
        obraceny_seznam.insert(0, prvek)
    return obraceny_seznam

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

tu = (1, 2, 3, 3, 4, 10)
vysledek = pozpatku(tu)
print(vysledek)

string = "ahoj lidi"
vysledek = pozpatku(string)
print(vysledek)

[10, 4, 3, 3, 2, 1]
[10, 4, 3, 3, 2, 1]
['i', 'd', 'i', 'l', ' ', 'j', 'o', 'h', 'a']
In [35]:
# řešení pomocí for-cyklu a indexu:
def pozpatku(posloupnost):
    obraceny_seznam = []
    
    for i in range(len(posloupnost)):
        obraceny_seznam.insert(0, posloupnost[i])
    return obraceny_seznam


seznam = [1, 2, 3, 3, 4, 10]
vysledek = pozpatku(seznam)
assert vysledek == [10, 4, 3, 3, 2, 1]
In [38]:
# řešení pomocí slicingu:
def pozpatku(posloupnost):
    return list(posloupnost[ : :-1])
    
s = (1, 2, 3, 3, 4, 10)
vysledek = pozpatku(s)
assert vysledek == [10, 4, 3, 3, 2, 1]
In [43]:
# řešení pomocí knihovních funkcí:
def pozpatku(posloupnost):
    seznam = list(posloupnost)
    seznam.reverse()
    return 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]
  1. Napište funkci, která vrátí medián vstupní posloupnosti čísel.
In [ ]:
# setřídím posloupnost a pak najdu prostředek
def median(posloupnost):
    sorted_lst = sorted(lst)
    
    length = len(sorted_lst)
    
    if length % 2 == 0:
        middle1 = sorted_lst[length // 2 - 1]
        middle2 = sorted_lst[length // 2]
        return (middle1 + middle2) / 2
    else:
        return sorted_lst[length // 2]

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

assert median([1, 2, 3]) == 2
assert median([1, 2]) == 1.5
  1. 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.
In [44]:
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]
  1. 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ší.
In [45]:
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. 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.
In [51]:
def primes(n):
    result = []
    d = 2
    while n > 1:
        while n % d == 0 :
            n = n // d
            result.insert(0, d)
        d += 1
    return result 
print( primes(72))

assert primes(72) == [3, 3, 2, 2, 2]

[3, 3, 2, 2, 2]
In [ ]:
# alternativně: jen jeden cyklus:
def primes(n):
    result = []
    d = 2
    while n > 1:
        if n % d == 0 :
            n  = n // d
            result.insert(0,d)
        else:
            d += 1
    return result 

assert primes(72) == [3, 3, 2, 2, 2]
  1. Napište funkci, která pomocí Eratosthenova síta najde všechna prvočísla menší nebo rovna $n$.
In [53]:
def eratosthenes(n):
    # pocatecni seznam:
    cisla = list(range(2,n+1))
    prvocisla = []
    while cisla != []:
        d = cisla[0]
        prvocisla.append(d)
        for i in range(d, n+1, d):
            if i in cisla:
                cisla.remove(i)
    return prvocisla

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

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
  1. 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.
In [55]:
def get_next_row(row):
    next_row = []
    for i in range(len(row)-1):
        next_row.append(row[i]+row[i+1])
    next_row.insert(0, 1)
    next_row.append(1)
    return next_row

print(get_next_row([1,2,1]))
print(get_next_row([1,3,3,1]))

[1, 3, 3, 1]
[1, 4, 6, 4, 1]
In [56]:
def pascal_triangle(n):
    row = [1]
    for i in range(n):
        print(row)
        row = get_next_row(row)
pascal_triangle(10)

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]