IB113 Radek Pelánek
2021
Vstup: seznam českých slov, napr.
https://wiki.korpus.cz/doku.php/seznamy:
srovnavaci_seznamy
(přes 300 tisíc slovních tvarů)
Výstup: největší množina slov, které jsou vzájemnou přes myč kou
vlasti, slavit, vstali, stavil, svitla, svalit
vynikal, vanilky, vynikla, navykli, vnikaly, viklany
kotle, loket, kotel, lokte, teklo, otekl
(8 řádků kódu v Pythonu, výpočet pod 1 sekundu)
Seznamy (pole) - motivace
• razení studentů podle bodů na písemce
• reprezentace herního plánu (piškvorky, šachy) 9 frekvence písmen v textu
Frekvenční analýza nevhodně
def frequency_analysis(text): text = text upper() freqA = 0 freqB = 0 freqC = 0
for letter in text: if letter == 'A':
freqA += 1 elif letter == 'B':
freqB += 1 elif letter == 'C : freqC += 1 print(1A1, freqA) print(1B1, freqB) print ( 'C , freqC)
0 12 3 4
• „více položek za sebou v pevném pořadí"
• indexováno od nuly
• základní koncept dostupný ve všech jazycích, běžně „pole" (array), položky stejného typu, pevně daná délka
• seznamy v Pythonu - obecnější (ale pomalejší)
• Python a pole - knihovna NumPy (nad rámec IB113)
Seznamy v Pythonu
0 12 3 4 -5 -4 -3 -2 -1
• variabilní délka
• položky mohou být různého typu
• indexování i od konce (pomocí záporných
Seznamy: použití v Pythonu
s = [] # deklarace prázdného seznamu
s = [3, 4, 1, 8]
s [2]
s[-l]
s [2] = 15
# indexace prvku, s[2] =1
# indexace od konce, s[-l] = 8
# změna prvku s.append(6) # přidání prvku na konec
s[l:4] # indexace intervalu, s[l:4] = [4, 15,
len(s) # délka seznamu, len(s) = 5
t = [3, "pes",  [2, 7], -8.3]
# seznam může obsahovat různé typy
list() - přetypování na seznam
8]
anipulace se seznamy
alist = [3, 8, 7] alist.append(10) alist.insert(1, 11) alist.remove(7)
# přidání na konec seznamu
# přidání na zadanou pozic
# odstranění dané hodnoty
Seznamy: konvence zápisu (PEP8)
• mezera se dělá: za čárkou
• mezera se nedělá: před čárkou, na „okrajích"
menovaní seznamu
• nepoužívat: list (kolize s vestavěnou funkcí na pretypovaní)
• neutrální názvy (primárně pro ukázky): alist, my_list
• názvy dokumentující typ: num_list, str_list
• názvy popisující význam: words, names, points, books
10/47
Python: seznamy a cyklus for
• cyklus for - přes prvky seznamu*
• range - vrací seznam* čísel
• typické použití: for i in range (n)
• ale můžeme třeba:
• for animal in ["dog", "cag", "pig"]: ...
• for letter in "hello world": ...
(*) ne úplně přesně - z důvodu efektivity se používají generátory a speciální „range object", v případě potřeby použijte explicitní pretypovaní na seznam: list (range (10))
< [S? ► < i ► < ± >   i •o^o
11/47
Príklad: výpočet průměrné hodnoty
def average1(num_list): total = 0
for i in range(len(num_list)):
total += num_list[i] return total / len(num_list)
def average2(num_list): total = 0
for value in num_list:
total += value return total / len(num_list)
def average3(num_list):
return sum(num_list) / len(num_list)
12/47
Prvky a indexy
jasně rozlišujte proměnné určené pro: indexy seznamu
• typicky i, j • prvky seznamu
• ideálně názvy odpovídající významu
• příp. generické value
• rozhodně ne i, j
13/47
Vestavěná podpora pro práci se seznamy
»> numbers = [4, 1, 8, 12, 3]
>» sum (numbers)
28
>» min(numbers) 1
>» max (numbers) 12
>» 8 in numbers True
14/47
Ilustrace práce se seznamem
def divisors_list(n): divisors = [] for i in ranged, n+1) : if n °/0 i == 0:
divisors.append(i) return divisors
divisors24 = divisors_list(24)
print(divisors24)
print(len(divisors24))
for x in divisors24: print(x**2)
Vytvorení seznamu
různé způsoby vytvoření seznamu písmen abecedy: alist = list("abcdefghijklmnopqrstuvwxyz")
alist = []
for i in range(26):
alist.append(chr(ord(1 a')+i))
alist = [chr(ord(1 a')+i) for i in range(26)]
Frekvenční analýza nevhodně
def frequency_analysis(text): text = text upper() freqA = 0 freqB = 0 freqC = 0
for letter in text: if letter == 'A':
freqA += 1 elif letter == 'B':
freqB += 1 elif letter == 'C : freqC += 1 print(1A1, freqA) print(1B1, freqB) print ( 'C , freqC)
Frekvenční analýza lépe
def frequency_analysis(text): text = text upper() frequency = [0 for i in range(26)] for letter in text:
if ord(letter) >= ord('A') and\ ord(letter) <= ord('Z'): frequency[ord(letter) - ord('A')] += for i in range(26):
if frequency[i]   != 0:
print(chr(ord(1A1)+i), frequency [i])
imulace volebního průzkumu - nevhodné řešení
def survey(size, prefl, pref2, pref3): count1 = 0 count2 = 0 count3 = 0
for i in range(size):
r = random.randint(1, 100) if r <= prefl: count1 += 1 elif r <= prefl + pref2: count2 += 1 elif r <= prefl + pref2 + pref3: count3 += print ("Party 1:11, 100 * count 1 / size) print("Party 2:", 100 * count2 / size) print("Party 3:", 100 * count3 / size)
Simulace volebního průzkumu - lepší řešení
def survey(size, pref): n = len(pref)
count = [0 for i in range(n)] for _ in range(size):
r = random.randint(1, 100) for i in range(n):
if sum(pref [:i]) < r <= sum(pref [:i+1]) count [i] += 1 for i in range(n):
print("Party", i+1, 100*count [i]/size)
Toto řešení má stále nedostatky (po stránce funkčnosti) -zkuste dále vylepšit.
20/47
• vstup: řetězec
• výstup: zápis v Morseově abecedě
• příklad: PES —. —. I . I . . .
21/47
Prevod do Morseovy abecedy nevhodně
def to_morse(text): result = 11
for i in range(len(text)):
if text[i] == 'A': result += 1 elif text[i] == 'B': result += elif text [i] == elif text[i] == # etc
return result
'C 'D'
result += result +=
i _ i _
22/41
Prevod do Morseovy abecedy: využití seznamu
morse = ['.-', '-..'] # etc
def to_morse(text): result = 11
for i in range(len(text)):
if ord('A') <= ord(text[i]) <= ord('Z'):
c = ord(text[i]) - ord('A')
result += morse[c] + 1I1 return result
(ještě lepší řešení: využití slovníku - bude později)
Prevod z Morseovy abecedy
def find_letter(sequence):
for i in range(len(morse)): if morse[i] == sequence:
return chr(ord('A') + i) return 1?1
def from_morse(message): result = 11 sequence = 11 for symbol in message: if symbol == 1|1:
result += find_letter(sequence) sequence = 11 else:
sequence += symbol return result < n►     ► < i ► < i ►   i ^
Split - seznam z řetězce
split - rozdělí řetězec podle zadaného oddělovače, vrátí seznam
»> vowels = Ma,e5 i,o,u,y"
»> vowels, split(M,")
['a',  'e',  'i1,  'o1,  'u', 'y']
»> message = 11. -. . I---I -. . I . -"
»> message. split (" I")
25/47
Príklad - načítaní vstupu od uživatele
»> input_string = input () 3 7
»> xstring, ystring = input_string.split( »> x = int(xstring) »> y = int (ystring)
Výškový prof i
475 rn n.m.
Stoupáni: 367 m
Klesaní: 363 m
mapy.cz
27/47
heights_profile([3, 4, 5, 3, 4, 3, 2, 4, 5, 6, 5])
#
# # # #
# # # # # # # ###### #### ########### ###########
Ascent 7 Descent 5
28/47
def heights_profile(heights):
for v in range(max(heights)):
for i in range(len(heights)):
if heights [i] >= max(heights) - v:
print ("#", end=M 11) else:
print ("    5 end=M 11)
print() print()
•<□►   4 ^ t   <  -z  ►   4 S ►
29/47
def elevation(heights): ascent = 0 descent = 0
for i in range(len(heights)-1): if heights [i] < heights [i+1]:
ascent += heights[i+1] - heights [i] else:
descent += heights [i] - heights [i+1] print ("Ascent11, ascent) print ("Descent11, descent)
30/47
Objekty, hodnoty, aliasy - stručné varování
a = [1,2,3] 3 = 11,2,3]
b = [1, 2, 3] nebo b = a[:]        b = a
[1,2,3] a—[1,2,3]
b-M1,2,3] b
• parametry funkcí - pouze volání hodnotou
(na rozdíl např. od Pascalu: volání hodnotou a odkazem)
• měnitelné objekty (napr. seznam) však funkce může měnit
• mělká vs hluboká kopie
• více později
31/47
zualizace běhu programu
http://www.pythontutor.com/
X = [1.
y = [4,
3   z = y
y = x
x = z
6
7 x
31 SI
[1
y = x
x.append(4) y.append(5) z =  [1.  2. 3
x.append(6) y.append(7)
14   y = "hello"
2 .  3] # a di fferent  [1.  2.  3] List!
4.  5] # a different list!
Frames
Global variables x [_•
'L-
Objects
0	1	2
4	5	6
st		
0	1	2
1	2	3
vhodné např. pokud je nejasný některý z příkladů ve
Zdvojnásobení seznamu
Příklad: vstupem seznam čísel (např. [4, 1, 6]), chceme „získat dvojnásobky" (tj. 8, 2, 12)
Důležité ujasnit, co přesně chceme:
• vypsat dvojnásobky
• vrátit nový seznam, který obsahuje dvojnásobky
• změnit seznam, aby obsahoval dvojnásobky
Jak vypadají jednotlivé programy?
33/47
• n-tice (tuples)
• neměnitelná varianta seznamů
• kulaté závorky místo hranatých (někdy lze vynechat): t = (1, 2, 3)
• neměnitelné podobně jako řetězce
• typické užití:
• souřadnice: (x, y)
• barva: (r, g, b)
9 použití pro přiřazení: a, b = b, a
34/47
Explicitní vzorec
(S)
íl ín\ — n!
(o) (i) ™ ~ (n-fe)!fc!
Rekurzivní vztah
(o) © ©
© © © © a) = (n1) + ("í1)
5    ^) c\ o 35/47
Pascalův trojúhelník
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)
Kompaktní zápis
pro zajímavost:
def get_next_row(row):
return [1] + [sum(p) for p in zip(row, row[1:])] + [1]
37/47
a dělitelné jen 1 a sebou samým
• předmět zájmu matematiků od pradávna, cca od 70. důležité aplikace (moderní kryptologie)
• problémy s prvočísly:
• výpis (počet) prvočísel v intervalu
• test prvočíselnosti
• rozklad na prvočísla (hledání dělitelů)
let i
38/47
Výpis prvočísel přímočaré
def print.primes(how_many): n = 1
while how_many > 0:
if len(divisors_list(n)) == 2: print (n, end=" 11) how_many -= 1
n += 1
print()
39/47
Eratosthenovo síto
• problém: výpis prvočísel od 2 do n
• algoritmus: opakovaně provádíme
• označ další neškrtnuté číslo na seznamu jako prvočíslo
• všechny násobky tohoto čísla vyškrtni
•<□►   4 ^ t   <  -ž  ►   <  -š ►
40/47
•<□►   4 ^ t   <  -Ž  ►   4 S ►
41/47
def
def
thenovo sfto
reset_multiples(is_candidate, i): k = i
while k < len(is_candidate): is_candidate[k] = False k += i
eratosthenes(n):
is_candidate = [True for _ in range(n)] for i in range(2, n): if is_candidate [i]:
print (i, end=" 11) reset_multiples(is_candidate, i)
Pozn. Všimněte si, že funkce mění seznam.
42/47
Zajímavosti
• prvočísla - Ulamova spirála
• Pascalův trojúhelník - obarvení podle sudosti -Sierpiňského trojúhelník
Vi Hart: Doodling in math: Sick number games
https : //www.khanacademy. org/math/recreational-math/vi-hart/doodling-in-math/v/ doodling- in-math-sick-number-games
43/47
Úlohy se seznamem slov
Vstup: seznam slov, např.
["kost", ■'rozum", "ale", "broskev", "igelit", "cesta", "elektrika"]
• výpis prvních písmen
• výpis délek slov
• nejdelší slovo v seznamu
• výpis slov obsahujících e
• výpis písmen vyskytujících se za e
44/47
Kontrolní otázky
• Je u datové struktury seznam důležité pořadí prvků?
• Může v Pythonu seznam obsahovat položky různého typu?
• Jakým příkazem přidáme do seznamu nový prvek?
• Jak zjistíme délku seznamu?
• Proč není dobrý nápad dát proměnné obsahující seznam jméno list?
• Řetězec je v mnoha ohledech podobný jako „seznam znaku . V cem se lisí (
• Jak vytvořit seznam obsahující čísla od 1 do 5? (uveďte několik různých způsobů)
• Jak zjistíme poslední prvek seznamu? Zkuste najít 3 různé způsoby
45/47
https://www.umimeprogramovat.cz/rozhodovacka https://www.umimeprogramovat.cz/porozumeni https://www.umimeprogramovat.cz/vystup-programu
^> sada „Seznamy"
46/47
• datová struktura seznam
• základní operace se seznamy
• příklady
příště: algoritmy se seznamy - vyhledávání, řazení
47/47