Řetězce a seznamy
IB111 Úvod do programování
Radek Pelánek
2017
1 / 59
Rozcvička: šifry
1 C S A R B V
E K T E O A
2 A J L B N O C E
3 C S B U J T M B W B
2 / 59
Transpoziční šifry
HESLOJEPRASE
H E S LO J E PR A S E
HES LOJ EPR ASE
H ES LO JE PR AS E
pozpátku trojice pozpátku
ob tři dopředu dozadu
šnek cik-cak
PO
K L A
D
JESC
H
O
V A N Y U
R
Y
B
NIABL
I
Z
K
O
U H R A Z E P O
K
L
A
D J
E
S
C
H
O
V
A
N Y
U
R
Y
B
N I
A
B
L
I
Z
K
O U
H
R
A
Z EK
K
3 / 59
Substituční šifry
K O Z A
10 14 25 0
13 17 2 3
N R C D
+3
ZWSQWUDBVWWCGF
SLONSLONSLONSL
HLEDEJPODLIPOU
Jednoduchá substituce - posun o 3 pozice
Substituce podle hesla
H
S 18
7
25 Z+
4 / 59
Řetězce a znaky – ukázky operací
"kos" * 3
"petr" + "klic"
text = "velbloud"
len(text)
text[0]
text[2]
text[-1]
ord(’b’)
chr(99)
str() – explicitní přetypování na řetězec
5 / 59
Uvozovky, apostrofy
jiné jazyky často: uvozovky pro řetězce, apostrofy pro
znaky
Python: lze používat uvozovky i apostrofy
PEP8: hlavně konzistence
6 / 59
Indexování od nuly
Proč indexujeme od 0?
částečně „historicky-technické důvody
ale i dobré „matematické důvody
Pro zájemce:
Why numbering should start at zero (Edsger W. Dijkstra)
http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
http://programmers.stackexchange.com/questions/110804/why-are-zero-based-arrays-the-norm
https://www.quora.com/Why-do-array-indexes-start-with-0-zero-in-many-programming-languages
7 / 59
Kódování
jak jsou znaky reprezentovány?
ASCII, ISO 8859-2, Windows-1250, Unicode, UTF-8, . . .
http://www.joelonsoftware.com/articles/Unicode.html
http://www.polylab.dk/utf8-vs-unicode.html
Python3 – Unicode řetězce
pro tento kurz:
ord, chr – převod znaků na čísla a zpět
anglická abeceda má přiřazena po sobě jdoucí čísla
for i in range(26):
print(chr(ord(’A’)+i))
8 / 59
Řetězce – pokročilejší indexování
(specifické pro Python)
text = "velbloud"
text[:3] # první 3 znaky
text[3:] # od 3 znaku dále
text[1:8:2] # od 2. znaku po 7. krok po 2
text[::3] # od začátku do konce po 3
9 / 59
Řetězce – změny
neměnitelné (immutable) – rozdíl oproti seznamům a
oproti řetězcům v některých jiných jazycích
změna znaku – vytvoříme nový řetězec
text = "kopec"
text[2] = "n" # chyba
text = text[:2] + "n" + text[3:]
10 / 59
Řetězce: další operace
text = "i Have a dream."
print(text.upper())
print(text.lower())
print(text.capitalize())
print(text.rjust(30))
print("X",text.center(30),"X")
print(text.replace("dream","nightmare"))
... a mnoho dalších, více později, příp. viz dokumentace
Pozn. objektová notace
11 / 59
Příklad: Transpozice (rozcvička 1)
úkol: přepis textu po sloupcích
příklad vstupu a výstupu (2 sloupce):
CESKATREBOVA
C S A R B V
E K T E O A
12 / 59
Transpozice (rozcvička 1)
def cipher_columns(text, n):
for i in range(n):
for j in range(len(text) // n + 1):
position = j * n + i
if position < len(text):
print(text[position], end="")
print()
13 / 59
Transpozice (rozcvička 1), kratší varianta
Za využití notace specifické pro Python:
def cipher_columns(text, n):
for i in range(n):
print(text[i::n])
14 / 59
Caesarova šifra (rozcvička 3)
substituční šifra – posun v abecedě
vstup: text, posun
výstup: zašifrovaný text
BRATISLAVA, 1 → CSBUJTMBWB
15 / 59
Caesarova šifra – řešení
def caesar_cipher(text, n):
result = ""
text = text.upper()
for i in range(len(text)):
if text[i] == " ":
result = result + " "
else:
c = ord(text[i]) + n
if (c > ord("Z")): c = c - 26
result = result + chr(c)
return result
Pozn. Řešení má nedostatky – zkuste najít a vylepšit.
16 / 59
Caesarova šifra – rozlomení
máme text zašifrovaný Caesarovou šifrou (s neznámým
posunem)
jak text dešifrujeme?
příklad: MPKTWTDVLVELMZCF
17 / 59
Caesarova šifra – rozlomení
máme text zašifrovaný Caesarovou šifrou (s neznámým
posunem)
jak text dešifrujeme?
příklad: MPKTWTDVLVELMZCF
jak to udělat, aby program vrátil jen jednoho kandidáta?
17 / 59
Caesarova šifra – rozlomení
18 / 59
Vigen`erova šifra
substituce podle hesla – „sčítáme zprávu a heslo
vhodné cvičení
rozlomení Vigen`erovovy šifry?
19 / 59
Seznamy (pole) – motivace
řazení studentů podle bodů na písemce
reprezentace herního plánu (piškvorky, šachy)
frekvence písmen v textu
20 / 59
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(’A’, freqA)
print(’B’, freqB)
print(’C’, freqC)
21 / 59
Seznamy (pole)
0 1 2 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 IB111)
22 / 59
Seznamy v Pythonu
0 1 2 3 4
-1-2-3-4-5
variabilní délka
položky mohou být různého typu
indexování i od konce (pomocí záporných čísel)
23 / 59
Seznamy: použití v Pythonu
s = [] # deklarace prázdného seznamu
s = [3, 4, 1, 8]
s[2] # indexace prvku, s[2] = 1
s[-1] # indexace od konce, s[-1] = 8
s[2] = 15 # změna prvku
s.append(6) # přidání prvku
s[1:4] # indexace intervalu, s[1:4] = [4, 15, 8]
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
24 / 59
Seznamy: konvence zápisu (PEP8)
mezera se dělá: za čárkou
mezera se nedělá: před čárkou, na „okrajích
25 / 59
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í přetypování
na seznam: list(range(10))
26 / 59
Objekty, hodnoty, aliasy – stručné varování
a = [1, 2, 3]
b = [1, 2, 3] nebo b = a[:]
a = [1, 2, 3]
b = a
[1, 2, 3]
[1, 2, 3]
[1, 2, 3]a
b
a
b
parametry funkcí – pouze volání hodnotou
(na rozdíl např. od Pascalu: volání hodnotou a odkazem)
měnitelné objekty (např. seznam) však funkce může měnit
mělká vs hluboká kopie
více později
27 / 59
Vizualizace běhu programu
http://www.pythontutor.com/
vhodné např. pokud je nejasný některý z příkladů ve slidech
28 / 59
N-tice - stručné představení
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)
použití pro přiřazení: a, b = b, a
29 / 59
Pří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 x in num_list:
total += x
return total / len(num_list)
def average3(num_list):
return sum(num_list) / len(num_list)
30 / 59
Ilustrace práce se seznamem
def divisors_list(n):
divisors = []
for i in range(1, n+1):
if n % i == 0:
divisors.append(i)
return divisors
divisors24 = divisors_list(24)
print(divisors24)
print(len(divisors24))
for x in divisors24: print(x**2)
31 / 59
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(’A’, freqA)
print(’B’, freqB)
print(’C’, freqC)
32 / 59
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’)] += 1
for i in range(26):
if frequency[i] != 0:
print(chr(ord(’A’)+i), frequency[i])
33 / 59
Simulace volebního průzkumu – nevhodné řešení
def survey(size, pref1, pref2, pref3):
count1 = 0
count2 = 0
count3 = 0
for i in range(size):
r = random.randint(1,100)
if r <= pref1: count1 += 1
elif r <= pref1 + pref2: count2 += 1
elif r <= pref1 + pref2 + pref3: count3 += 1
print("Party 1:", 100.0 * count1 / size)
print("Party 2:", 100.0 * count2 / size)
print("Party 3:", 100.0 * count3 / size)
34 / 59
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.
35 / 59
Převod do Morseovy abecedy
vstup: řetězec
výstup: zápis v Morseově abecedě
příklad: PES → .--.|.|...
36 / 59
Převod do Morseovy abecedy nevhodně
def to_morse_poor(text):
result = ’’
for i in range(len(text)):
if text[i] == ’A’: result += ’.-|’
elif text[i] == ’B’: result += ’-...|’
elif text[i] == ’C’: result += ’-.-.|’
elif text[i] == ’D’: result += ’-..|’
# etc
return result
37 / 59
Převod do Morseovy abecedy: využití seznamu
morse = [’.-’, ’-...’, ’-.-.’, ’-..’] # etc
def to_morse(text):
result = ’’
for i in range(len(text)):
if ord(’A’) <= ord(text[i]) <= ord(’Z’):
c = ord(text[i]) - ord(’A’)
result += morse[c] + ’|’
return result
(ještě lepší řešení: využití slovníku – bude později)
38 / 59
Převod z Morseovy abecedy
def find_letter(sequence):
for i in range(len(morse)):
if morse[i] == sequence:
return chr(ord(’A’) + i)
return ’?’
def from_morse(message):
result = ’’
sequence = ’’
for symbol in message:
if symbol == ’|’:
result += find_letter(sequence)
sequence = ’’
else:
sequence += symbol
return result 39 / 59
Split – seznam z řetězce
split – rozdělí řetězec podle zadaného oddělovače, vrátí
seznam
>>> vowels = "a,e,i,o,u,y"
>>> vowels.split(",")
[’a’, ’e’, ’i’, ’o’, ’u’, ’y’]
>>> message = ".-..|---|-..|.-"
>>> message.split("|")
[’.-..’, ’---’, ’-..’, ’.-’]
40 / 59
Příklad – načítání vstupu od uživatele
>>> input_string = input()
3 7
>>> xstring, ystring = input_string.split(" ")
>>> x = int(xstring)
>>> y = int(ystring)
41 / 59
Výškový profil
mapy.cz
42 / 59
Výškový profil
heights_profile([3, 4, 5, 3, 4, 3, 2, 4, 5, 6, 5])
#
# # # #
# # # # # # #
# # # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # # #
Ascent 7
Descent 5
43 / 59
Výškový profil
def heights_profile(heights):
for v in range(max(heights)):
for i in range(len(heights)):
if heights[i] >= max(heights) - v:
print("#", end=" ")
else:
print(" ", end=" ")
print()
print()
44 / 59
Výškový profil
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("Ascent", ascent)
print("Descent", descent)
45 / 59
Pascalův trojúhelník
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Explicitní vzorec
Rekurzivní vztah
46 / 59
Pascalův trojúhelník
def pascal_triangle(n):
current_row = [1]
for j in range(n):
for x in current_row:
print(x, end=" ")
print()
next_row = [1]
for i in range(len(current_row)-1):
next_row.append(current_row[i] +\
current_row[i+1])
next_row.append(1)
current_row = next_row
47 / 59
Prvočísla
dělitelné jen 1 a sebou samým
předmět zájmu matematiků od pradávna, cca od 70. let i
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ů)
48 / 59
Výpis prvočísel přímočaře
def print_primes(how_many):
n = 1
while how_many > 0:
if len(divisors_list(n)) == 2:
print(n, end=" ")
how_many -= 1
n += 1
print()
49 / 59
Odbočka: test prvočíselnosti, kryptografie
Test prvočíselnosti:
zkoušíme všechny možné dělitele od 2 do n − 1
vylepšení:
dělíme pouze dvojkou a lichými čísly
dělíme pouze dvojkou a čísly tvaru 6k ± 1
dělíme pouze do
√
n
50 / 59
Test prvočíselnosti: chytřejší algoritmy
náhodnostní algoritmy
polynomiální deterministický algoritmus (objeven 2002)
(vysoce) nad rámec tohoto kurzu
umí se to dělat rychle
51 / 59
Rozklad na prvočísla
rozklad na prvočísla = faktorizace
naivní algoritmy:
průchod všech možných dělitelů
zlepšení podobně jako u testů prvočíselnosti
chytřejší algoritmy:
složitá matematika
aktivní výzkumná oblast
neumí se to dělat rychle
max cca 200 ciferná čísla
52 / 59
Příklad aplikace: asymetrická kryptologie
http://en.wikipedia.org/wiki/Public-key_cryptography
53 / 59
Asymetrická kryptologie: realizace
jednosměrné funkce
jednoduché vypočítat jedním směrem
obtížné druhým (inverze)
ilustrace: míchání barev
RSA (Rivest, Shamir, Adleman) algoritmus
jednosměrná funkce: násobení prvočísel (inverze =
faktorizace)
veřejný klíč: součin velkých prvočísel
bezpečnost ∼ nikdo neumí provádět efektivně faktorizaci
využití modulární aritmetiky, Eulerovy věty, ...
54 / 59
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
55 / 59
Eratosthenovo síto
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
31 32 33 34 35 36 37 38 39 4021 22 23 24 25 26 27 28 29 30
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
31 32 33 34 35 36 37 38 39 4021 22 23 24 25 26 27 28 29 30
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
1. krok
2. krok
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
31 32 33 34 35 36 37 38 39 4021 22 23 24 25 26 27 28 29 30
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
3. krok
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
31 32 33 34 35 36 37 38 39 4021 22 23 24 25 26 27 28 29 30
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
4. krok
56 / 59
Eratosthenovo síto
def eratosthenes(count):
is_candidate = [1 for i in range(count)]
for i in range(2, count):
if is_candidate[i]:
print(i, end=" ")
k = 0
while k < count:
is_candidate[k] = 0
k += i
print()
57 / 59
Zajímavosti
prvočísla – Ulamova spirála
Pascalův trojúhelník – obarvení podle sudosti –
Sierpi´nské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
58 / 59
Shrnutí
Seznamy, řetězce:
základní operace
ukázky použití
kryptografické příklady (historické) a souvislosti (moderní)
Příště: Vyhledávání, řadicí algoritmy
59 / 59