====== 4. Složené datové typy ======

Přehled datových typů dostupných v základní instalaci Pythonu

Základní:

  * ''%%int%%'': Celé číslo (integer)
  * ''%%float%%'': Desetinné číslo
  * ''%%str%%'': Textový řetězec (string)
  * ''%%bool%%'': Binární logická hodnota
  * ''%%complex%%'': Komplexní číslo
  * ''%%bytes%%'': Binární hodnota (nereprezentovaná)

Složené:

  * ''%%list%%'': Seznam
  * ''%%tuple%%'': N-tice
  * ''%%range%%'': Rovnoměrná posloupnost
  * ''%%set%%'', ''%%frozenset%%'': Množina
  * ''%%str%%'': Textový retězec (string)
  * ''%%dict%%'': Slovník
  * ''%%bytearray%%'': Pole binárních hodnot
  * ''%%memoryview%%'': Binární obraz


===== Seznam: list =====

Seznam je kolekce hodnot stejných nebo různých datových typů. Pro výčet metod seznamů zadejte ''%%dir(list)%%''

  * ''%%x = [1, 2, 3, 4]%%'', je seznam tvořený čtveřicí čísel typu ''%%int%%'' jejichž hodnoty jsou ''%%1%%'', ''%%2%%'', ''%%3%%'' a ''%%4%%''
  * ''%%y = [1, '2', 3, 4]%%'', je seznam tvořený trojicí čísel typu ''%%int%%'' jejichž hodnoty jsou ''%%1%%'', ''%%3%%'' a ''%%4%%'' a znakem ''%%'2'%%''

K jednotlivým prvkům (elementům) seznamu můžeme přistupovat pomocí indexu, čísla typu ''%%int%%'', v hranatých závorkách

  * ''%%x[0]%%'' nebo ''%%y[0]%%'' vrátí první prvek v seznamu, v obou případech se jedná o číslo ''%%1%%'' -- v Pythonu se indexuje od 0
  * ''%%x[3]%%'' nebo ''%%y[3]%%'' vrátí poslední prvek v seznamu, v obou případech se jedná o číslo ''%%4%%'' -- poslední prvek seznamu má index o jedna menší než je délka seznamu (počtu prvků seznamu), kterou můžeme získat funkcí ''%%len()%%''
    * ''%%x[3] == x[len(x)-1]%%'' a ''%%y[3] == y[len(y)-1]%%''
    * přístup k poslednímu prvku seznamu se v Pythonu může provést elegantně pomocí indexu ''%%-1%%'': ''%%x[3] == x[-1]%%'' a ''%%y[3] == y[-1]%%''

Pomocí indexů mohu také měnit hodnoty jednotlivých prvků v seznamu

  * ''%%y[0] = 5%%'' změní první prvek seznamu ''%%y%%'' na ''%%5%%''

Ze seznamů můžeme také vybírat menší podseznamy pomocí řezů

  * ''%%x[0:3] == x[:3] == [1,2,3]%%'' což znamená, že řez je proveden od ''%%x[0]%%'' až do ''%%x[3-1]%%''

Při vytváření řezů, můžeme zadat také krok, s jakým se seznam bude procházet

  * ''%%x[1:4:2] = [2,4]%%'' nebo ''%%x[::2] = [1,3]%%'' projde celý seznam s krokem 2
  * pokud zadáme záporný krok, seznam bude procházen pospátku: ''%%x[::-2] = [4,2]%%''


<code python>
# bunka pro hrani se seznamy
</code>


Jelikož jsou indexy seznamu celá čísla a seznamy mohou obecně nabývat spousty hodnot, je vhodné se seznamy pracovat pomocí cyklů


<code python>
seznam = [1, 3, 6]  # vytvorime 1D seznam


for i in seznam:  # k jednotlivycm prvkum seznamu muzeme pristupovat napriklad ve for cyklu
    print(i, end=' ')

print()
# nebo pomoci indexu, kdy nechame for cyklus opakovat tolikrat, kolik prvku mame v seznamu: len(seznam)
for i in range(len(seznam)): 
    print(seznam[i],end=' ')
</code>


<code python>
# pro zajímavost - výstupem funkce enumerate je index prvu v seznamu i samotný prvek
print()
for i, prvek in enumerate(seznam):
    print(prvek,end=' ') 
    print(seznam[i],end=' ')
</code>


==== Vytvoření seznamu ====

  * seznam můžeme vytvářet buď přímo výčtem hodnot oddělených čárkou v hranatých závorkách: ''%%x = [1,2,3,4]%%'', někdy je vhodné takto vytvořit i prázdný seznam ''%%y = []%%'' (inicializovat si proměnnou)
  * přidávat hodnoty do existujícího seznamu (buď prázdného nebo ne) pak můžeme pomocí metody ''%%append()%%'': ''%%y.append(hodnota)%%''
  * v Pythonu je k dispozici tzv. seznamová komprehenze, která vytvoří seznam na jednom řádku, např. ''%%z = [i for i in range(10)]%%''


<code python>
y = []  # prazdny seznam

for i in range(10):
    y.append(i)

print(y)

# append je metoda datoveho typu seznam, podivejte se na dalsi metody aplikovatelne na seznam, umoznuji napriklad vyjimani prvku, razeni seznamu atd.

z = [i for i in range(10)]  # stejny vysledek pomoci seznamove komprehenze

print(z)
</code>


==== Úloha 1. Fibonacciho posloupnost ====

Vytvořte seznam jehož prvky bude [[https://en.wikipedia.org/wiki/Fibonacci_number|Fibonacciho]] posloupnost o ''%%n%%'' prvcích.

Postup ve zkratce: $$F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$$


<code python>
n = 20  # pocet prvku rady

# zde piste svuj kod

</code>


==== Úloha 2. Součet kladných čísel ====

Napište funkci jejímž argumentem je seznam celých čísel a která vrátí součet pozitvních čísel z daného seznamu.


<code python>
seznam = [95, 23, -3, 42, 50, -39, 48, -43, 7, -31, -85, 38, 25, -38, 1, -14, 79, -55, -34, -87] #408

# zde piste svuj kod
</code>


==== Úloha 3. Přátelé Foa ====

Napište funkci, která vyfiltruje seznam řetězců obsahující jména.

Vyberte ta jména, která mají přesně čtyři znaky, to jsou přátelé Foa. Tato jména budou vrácena funkcí jako seznam řetězců.

Ex: vstup = ["Ryan", "Kieran", "Jason", "Yous"], Výstup = ["Ryan", "Yous"]


<code python>
jmena = ["Ryan", "Kieran", "Jason", "Yous"]

# zde piste kod
</code>


==== Úloha 4. Eratostheneovo síto pro nalezení prvočísel ====

Napište funkci, která vrátí seznam tvořený prvočísly od prvního prvočísla až do čísla ''%%n%%'', které bude argumentem funkce. Pro nalezení prvočísel využijte algoritmus zvaný [[https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes|Eratostheneovo síto]].


<code python>

def Sieve_of_Eratosthenes(n):
        
    list_int = [x for x in range(2,n+1)]  # make a list of integers from 2 to n
    list_mark = [True for x in range(2,n+1)] # make a list of True values of the same size as above

    # zde piste svuj kod
</code>


===== Seznam seznamů =====

Již bylo řečeno, že prvkem seznamu může být hodnota jakéhokoli datového typu, například seznam řetězců ''%%seznam_text = ['petr','pavel','josef']%%''

Je tedy možné vytvořit také seznam, jehož prvky budou seznamy ''%%matice = [[1,2,3],[4,5,6],[7,8,9]]%%''

  * ''%%matice[0][0]%%'' představuje první prvek prvního prvku seznamu, tedy první prvek v prvním řádku matice
  * výše je uveden příklad matice, ale obecně může být každý seznam v seznamu různé délky


Seznam je měnitelný datový typ, což v Pythonu znamená, že vytvoříme-li jeden seznam ''%%x = [1,2,3]%%'' a poté druhý seznam takto ''%%y = x%%'', jakákoli manipulace se seznamem ''%%y%%'' mění také seznam ''%%x%%''

Např. ''%%y[0] = 5%%''

Pokud tomu chceme předejít, musíme u 1D seznamů použít například klíčové slovo ''%%list%%'': ''%%y = list(x)%%''

V případě, že elementy seznamu jsou další seznamy, je nejlepší pro tzv. hlubokou kopii použít funkci ''%%deepcopy%%'' z modulu ''%%copy%%''


<code python>
x = [1,2,3]
y = x
y[0] = 5
print(f'x = {x}, y = {y}')

y = list(x)
y[0] = 10
print(f'x = {x}, y = {y}')

y = x.copy() # v případě 1D listu
y[0] = 10
print(f'x = {x}, y = {y}')
</code>


<code python>
import copy

x = [[2,3],2]

y = copy.deepcopy(x)
y[0][0] = 1
print(f'x = {x}, y = {y}')


y2 = list(x)  # toto je pouze melka kopie (vnitrni seznamy jsou v y2 a x stejne objekty)
y2[0][0] = 100
print(f'x = {x}, y2 = {y2}')


y3 = x.copy()  # pozor!, .copy() v tomto pripade vytvari pouze melkou kopii
y3[0][0] = 10
print(f'x = {x}, y3 = {y3}')


</code>


==== Vytvoření matice ====

  * matici můžeme vytvořit pomocí for cyklů nebo seznamové komprehenze


<code python>
matice = []  # nejprve nadeklarujeme praznou matici
n_radku = 3
n_sloupcu = 3

for i in range(n_radku):
    radek = []
    for k in range(n_sloupcu):
        radek.append(i*n_sloupcu+k+1)
    matice.append(radek)

print(matice)


# pomoci seznamove komprehenze

matice_c = [[i*n_sloupcu + k + 1 for k in range(n_sloupcu)] for i in range(n_radku)]

print(matice_c)
</code>


==== Úloha 6. Součet matic. ====

Vytvořte funkci, která dostane jako argument dvojici matic a sečte je


<code python>
mat1 = [[1,2,3],[0,0,0],[5,5,5]]
mat2 = [[-1,-2,-3],[1,1,1],[-3,-3,-3]]

def soucet_matic(mat1,mat2):
    # zde napiste svuj kod
    

print(soucet_matic(mat1,mat2))
    
</code>


===== n-tice: tuple =====

n-tice je neměnitelný seznam, který můžeme nadefinovat například výčtem pomocí kulatých závorek nebo příkazu ''%%tuple%%''

<code python>
t = () # An empty tuple
t = (0, 'one')
t = ('a', ['b', 'c'], (1, 2, 3))
t = tuple(range(10))
</code>

n-tice jsou užitečné například pokud necheme, aby funkce změnila hodnoty argumentů, protože v případě předání seznamu se hodnoty změní


<code python>
def pricti1(z,hodnota):
    for i in range(len(z)):
        z[i] += hodnota
    return z


def pricti2(z,hodnota):
    z = list(z) # jediny rozdil mezi funkcemi
    for i in range(len(z)):
        z[i] += hodnota
    return z
</code>


<code python>
# test funkce pricti1 - vsimni si vystupu
x = (1,2,3,4)   # vytvori n-tici
y = [1,2,3,4]   # vytvori seznam

print(pricti1(y,1))  # pujde
print('seznam y = ',y)


print(pricti1(x,1))  # nepujde
print('seznam x = ',x)
</code>


<code python>
# test funkce pricti2 - vsimni si vystupu
x = (1,2,3,4)   # vytvori n-tici
y = [1,2,3,4]   # vytvori seznam

print(pricti2(y,1))  # pujde
print('seznam y = ',y)

print(pricti2(x,1))  # pujde
print('seznam x = ',x)
</code>


===== Množina (set) =====

  * Jako množina v matematice
  * Kolekce různých datových typů, která není uspořádaná -- nelze tedy indexovat
  * Každý prvek je unikátní
  * Je modifikovatelná

<code python>
s = set() # An empty set
s = {1, 1, 2, 2, 3} # The same as {1, 2, 3}
s = set(range(10))
</code>


<code python>
# vyuziti mnoziny pro vyber unikatnich prvku v seznamu
x = [1, 1, 2, 3, 4, 5]
x_unique = list(set(x))
print(x_unique)
</code>


==== Úloha 7. Opakující se písmena ====

V AJ (a dalších jazicíh) existuje pojem [[https://en.wikipedia.org/wiki/Heterogram_(literature)|Heterogram]]. Tento pojem označuje slovo či větu, ve které se žádné z písmen neopakuje (tedy každé písmeno je zastoupeno pouze jednou). Napište funkci, která zjistí zda je slovo heterogramem. Vraťte True nebo False. Využijte metodu **.lower()** pro převod slova na malá písmena.


<code python>
def is_heterogram(slovo):

    # vas kod


slova = ['roh', 'loupak', 'polotovar', 'struhadlo', 'Ovoce', 'zamenictvi', 'scvrnkl', 'nejnezpravdepodobnostnovavatelnejsimi', 'dvacetikoruny']

for slovo in slova:
    if is_heterogram(slovo):
        print('Slovo {0:s} je heterogram!'.format(slovo))
    else:
        print('Slovo {0:s} není heterogram.'.format(slovo))
</code>


===== Slovník: dictionary =====

  * Každý prvek tvořený **klíčem** (//key//) a **hodnotou** (//value//)
  * Hodnoty jsou ekvivalentní seznamu, klíče slouží k indexaci

<code python>
d1 = {} # An empty dictionary
d2 = dict() # An empty dictionary
d3 = dict.fromkeys(['one', 'two', 'three']) # Empty with keys 'one', 'two', 'three'
d4 = dict.fromkeys('abcde') # Empty with keys 'a', 'b', 'c', 'd', 'e'
d5 = {'one': 1, 'two': [1, 2, 3]} # By a literal
d6 = dict(zip('keys', [1, 2, 3, 4])) # {'k': 1, 'e': 2, 'y': 3, 's': 4}
</code>

  * Indexování:

<code python>
d = {'a': [1, 2, 3], 'b': ['a', 'b', 'c']}
d['a'][0]
d['b']
...
</code>


<code python>
d = {'Daniel': {'vek': 23, 'vaha':65, 'sourozenci':['Jan', 'Adela']},
'Jan': {'vek': 21, 'vaha':80, 'sourozenci':['Daniel, Adela']},
'Pavla': {'vek':22, 'vaha':55, 'sourozenci':['Iveta']}}

print(d.keys())
print(d['Daniel'].keys())
print(d['Daniel']['sourozenci'])

d['Cecil'] = {'vek':78, 'vaha':76, 'sourozenci':['Vitezslav']}
print(d)
</code>


==== Úloha 8. Třídění ====

Musíte roztřídit pytel plný věcí. Na každé věci je etiketa, na které je napsaný primární (a případně i sekundární) materiál, z kterého je daná věc vyrobená. Vaším úkolem je věci správně roztřídit podle materiálu (papir, sklo, organicky_material, plast). Vstupem funkce je seznam veci, výstupem je n-tice/matice.

Příklad:

<code python>
veci = [
    {"typ": "jablka", "material": "organicky_material"},
    {"typ": "jogurt", "material": "organicky_material", "sekundarniMaterial": "plast"},
    {"typ": "lahev vina", "material": "sklo", "sekundarniMaterial": "papir"},
    {"typ": "krabice", "material": "papir"},
    {"typ": "igelitovy sacek", "material": "plast"},
    {"typ": "lahev piva", "material": "sklo", "sekundarniMaterial": "papir"}
]

vystup = (
    ["lahev vina", "krabice", "lahev piva"], #papir
    ["lahev vina", "lahev piva"], #sklo
    ["jablka", "jogurt"], #organicky_material
    ["jogurt", "igelitovy sacek"] #plast
)
</code>


<code python>
def trideni(veci):

    # vas kod
</code>


===== Příklady na procvičení ve zbytku cvičení nebo doma =====


==== Úloha 9. Vrať prostřední znak - na procvičení indexace ====

Napište funkci, která jako argument dostane slovo a vrátí prostřední znak slova pokud je délka slova lichá nebo prostřední dvojici znaků pokud je délka slova sudá.

Příklad:

  * roh => **o**
  * loupak => **up**
  * nejnezpravdepodobnostnovavatelnejsimi => **o**
  * zamenictvi => **ni**


<code python>

</code>


==== Úloha 10. Kreditní karta - na procvičení indexace ====

Při nákupu na internetu chceš použít kreditní/debetní kartu. Při zadávání čísel si všimneš, že jsou vždy viditelné akorát poslední 4 číslice (kvůli bezpečnosti). Dokážeš napsat funkci, která tzv. zamaskuje všechny znaky, až na poslední čtyři? Vstupem funkce je celé číslo, které je potřeba zamaskovat, a maskovací znak. V případě, že má číslo 4 číslice (či méně), vrať číslo bez maskování. V případě, že není zadán znak, použijte **#**.

Příklad:

  * maskovani(90273874982936,'#') => '##########2936'
  * maskovani(123,'o') => 123
  * maskovani(847563,'q') => 'qq7563'


<code python>
def maskovani(cislo, znak):

    # vas kod
</code>


==== Úloha 11. Procházka po městě - na procvičení práce s metodami, podmínkami (případně se slovníkem a množinami) ====

Pepíček žije ve měste, kde ulice vypadají jako [[https://en.wikipedia.org/wiki/Eixample|čtverečkový papír]] (stejně dlouhé a míří buď na sever, jih, východ nebo západ). Jeden den se Pepíček rozhodne, že půjde na výlet (Vyjádřeno seznamem, kde jednotlivá písmena značí orientaci. Vzdálenost je konstantní, tedy jedno písmeno = jedna jednotka vzdálenosti). Napište funkci, která určí zda se Pepíček dokázal vrátit domů nebo zda se na výletě ztratil. //Použijte metodu .count().//

Příklad:

  * prochazka(['j', 'j', 'v', 'j', 'z', 's', 'z', 's', 's', 'z', 'v', 'v']) => True
  * prochazka(['j', 's', 'j', 'v', 'v']) => False


<code python>
def prochazka(cesta):

    # vas kod
</code>


==== Úloha 12. DNA - na procvičení práce se slovníkem, popřípadě seznamy ====

Deoxyribonucleic acid (DNA) nese "instrukce" pro rozvoj a funkci buněk živých organizmů. Pro více informací http://en.wikipedia.org/wiki/DNA

V řetězci DNA, symboly "A" a "T" se navzájem doplňují stejně jako "C" a "G". Napište funkci, která dostane jako vstup jednu stranu DNA a doplní druhou stranu DNA.

Více obdobných cvičení můžete najít [[http://rosalind.info/problems/list-view/|zde]]

Příklad: (vstup --> výstup)

''%%"ATTGC" --> "TAACG"%%''

''%%"GTAT" --> "CATA"%%''


<code python>
def DNA_strand(dna):
    # Vas kod
    
    
DNA_strand('ATTGC')    
</code>


==== Úloha 13. Jsi nadpruměrný? - na procvičení práce s funkcemi a podmínkami (případně s cykly) ====

Prošel jsi testem a chtěl by jsi vědět, jestli byl Tvůj výsledek lepší než průměr ze všech bodů v Tvé třídě.

Napiš funkci, která má jako argument seznam se všemi body ve třídě a druhý argument je Tvé bodové ohodnocení. Funkce spočítá průměr a porovná Tváj výsledek s průměrem. Pokud je větší, vrátí True, pokud ne vrátí False


<code python>
def better_than_average(body,tve_body):
    # zde vas kod



test_arr = [12, 23, 34, 45, 56, 67, 78, 89, 90]
better_than_average(test_arr, 69)
</code>


==== Úloha 14. Součin matice ====

Napiš funkci, která vypočítá součin matic podle pravidla o násobení matic


<code python>

</code>


==== Úloha 15. Gaussova eliminace ====

Pokuste se implementovat Gaussovu eliminační metodu podle postupu v materiálech k předmětu [[https://cw.fel.cvut.cz/wiki/courses/b3b33alp/cviceni/t06|ALP]] (úkol 3). Řešení je možné nalézt ve [[https://www.youtube.com/watch?v=c9HKbcSB6Gk&feature=youtu.be|videu]]


<code python>

</code>


==== Úloha 16. Continued fraction algorithm ====

Napište funkci, která provede tzv. [[https://en.wikipedia.org/wiki/Continued_fraction|continued fraction algorithm]], který rozloží racionální číslo větší než 1 do tvaru $$m_0 + \frac{1}{m_1+\frac{1}{m_2+\frac{1}{m_3 + ...}}}$$

Algoritmus je posán několika kroky:

  - začněte s ''%%n=0%%'' a číslem $ R$ které uložíme do seznamu ''%%x[n]%%''
  - zaokrouhlení: ''%%m[n] = round(x[n])%%''
  - zbytek: ''%%r[n] = x[n] - m[n]%%''
  - pokud ''%%r[n] != 0%%'', pak ''%%x[n+1] = 1/r[n]%%'' a opakuj od bodu 2., jinak ukonči algoritmus
  - výstup je pak vektor ''%%m[n]%%'' a v případě nedokončeného algoritmu (například pokud ukončíme iteraci dříve nebo pokud číslo není možné zcela aproximovat) hodnota ''%%x[n+1]%%''

Při implementaci buď zvolte rozložitelné reálné číslo nebo pouze několik iterací, například pomocí for cyklu.

Příklad pro $\pi = 3.14159$ a pouze jednu iteraci:

  * ''%%n=0%%'', ''%%x[0] = 3.14159%%'', ''%%m[0] = 3%%'', ''%%r[0] = 0.14%%''
  * ''%%x[1] = 1/0.14159%%'', $\pi$ pak můžeme aproximovat jako $\pi \approx 3 + \frac{1}{7} = \frac{22}{7} $


<code python>

</code>


==== Úloha 17. Ověřte správnost continued fraction algoritmu z úlohy 3. ====

Napište funkci, která na svém vstupu bude mít seznam s koeficinety z CFA algoritmu a provede výpočet aproximovaného čísla

Složitější varianta:

Vyjádřete zadané racionální číslo jako zlomek


<code python>

</code>