Přidat příklad
Přidat příklad
Přidat vysvětlení ze sbírky Přidat vysvětlení
Upravit text (markdown)
ukončit upravování textuObsah cvičení
Odkazy
odkaz na cvičeníeditace cvičení
Náhled
(experimentální - zdrojové kódy se nezobrazují - dvojklik je většinou rozbalí)živý náhled (může být výpočetně náročné)
1. Želví grafika¶
Čísla
Proměnné
Opakování
Funkce
Matematická knihovna
Želví grafika
Pokud budete knihovnu turtle využívat mimo online prostředí cvičebnice,
je potřeba ukončit kreslení funkcí done:
from turtle import Turtle, done
julie = Turtle()
# kresleni ...
done()
1.1. Rozcvička¶
1.1.1. Jednoduché obrázky¶
Nejprve si zkuste nakreslit nějaký jednoduchý obrázek, třeba trojúhelník, nebo domeček.
from turtle import Turtle
julie = Turtle()
# TODO: trojuhelnik / domecek / cokoliv
1.1.2. Čtverec¶
Využijte for cyklus pro nakreslení čtverce o délce strany 100 pixelů.
from turtle import Turtle
julie = Turtle()
# TODO: vykresleni ctverce
1.1.3. Obecný čtverec¶
Napište funkci pro vykreslení čtverce s danou délkou strany.
from turtle import Turtle
julie = Turtle()
def square(side):
# nahradte "pass" vykreslenim ctverce o delce strany 'side'
pass
square(100)
Poznámka: příkaz pass nic nedělá, pouze zastupuje tělo zatím
neimplementované funkce (díky tomu je program syntakticky správně).
1.1.4. Obecný pětiúhelník¶
Napište funkci pro vykreslení pravidelného pětiúhelníku s danou délkou strany.
from turtle import Turtle
julie = Turtle()
def pentagon(side):
pass
pentagon(100)
1.1.5. N-nožka¶
Napište funkci, která nakreslí stonožku se zadaným počtem článků.
from turtle import Turtle
julie = Turtle()
def centipede(n):
pass
centipede(7)
1.2. Pokročilé kreslení¶
1.2.1. Mnohoúhelníky¶
Napište obecnou funkci pro vykreslení libovolného pravidelného n-úhelníku.
from turtle import Turtle
julie = Turtle()
def polygon(n, side):
pass
polygon(3, 180)
polygon(5, 100)
1.2.2. Hvězdy¶
Napište obecnou funkci pro vykreslení hvězdy. Hvězda je zobecněním
pravidelného n-úhelníka, kde želva nenavštěvuje bezprostředně sousední vrcholy,
ale „přeskakuje“. Délka skoku je daná parametrem step, ten je např. pro pro
první, pěticípou hvězdu roven 2 a pro druhou, sedmicípou hvězdu roven 3. Při
step = 1 půjde o n-úhelník.
from turtle import Turtle
julie = Turtle()
def star(n, step, side):
pass
star(5, 2, 100)
1.2.3. Diamant¶
Napište funkci pro vykreslení diamantu.
from turtle import Turtle
julie = Turtle()
def diamant(n, side):
pass
diamant(12, 30)
1.2.4. Spirála¶
Napište funkci pro vykreslení spirály.
from turtle import Turtle
julie = Turtle()
def spiral(n, angle, step):
pass
spiral(100, 61, 1)
1.2.5. Kružnice¶
Pomocí funkce pro mnohoúhelníky zkuste vykreslit kružnici. Pak napište funkci pro vykresleni kružnice o zadaném poloměru. (Nápověda: využijte porovnání obvodů kružnice a pravidelného n-úhelníku).
from math import pi
from turtle import Turtle
julie = Turtle()
julie.speed(10)
def circle(r):
pass
circle(90)
1.2.6. Kytky¶
Napište funkci pro vykreslení kytky. Může být užitečné si nejprve napsat pomocnou funkci pro vykreslení oblouku (kruhové výseče) o zadaném poloměru a úhlu.
from math import pi
from turtle import Turtle
julie = Turtle()
julie.speed(10)
def flower(radius, angle, leaves):
pass
flower(100, 80, 9)
1.2.7. Čtvercová spirála¶
Napište funkci pro vykreslení čtvercové spirály.
from turtle import Turtle
from math import atan, sqrt, degrees
julie = Turtle()
def square_spiral(n, size):
pass
square_spiral(10, 100)
2. Základní struktury¶
V rámci následující kapitoly se naučíte používat základní struktury, jako jsou proměnné, for cyklus a funkce.
Proměnná
Na proměnné se dá dívat jako na pojmenované „šuplíky“, do kterých si můžeme
ukládat informace. Pokud chceme do proměnné přiřadit nějakou hodnotu,
používáme operátor přiřazení =. Je zvykem v názvech proměnných používat
pouze malá písmena a číslice. V případě víceslovných názvu proměnných
jednotlivá slova oddělujeme podtržítkem.
for cyklus
Občas narazíme na situace, kdy je potřeba zopakovat nějaký úkon několikrát
za sebou. Pro tyto účely můžeme použít for cyklus. Pro použití for cyklu
jsou potřeba 2 věci: řídící proměnná a prvky, které procházíme (seznam,
sekvence, iterátor, generátor, …). Program, který chceme zopakovat
označujeme jako tělo for cyklu a musí být odsazené. For cyklus postupně
přiřazuje prvky for cyklu do řídící proměnné a spouští své tělo. V
následujícím příkladu používáme řídící proměnnou i a prvky, které
procházíme jsou definovány pomocí range(10). For cyklus v následujícím
příkladu postupně vypíše čísla od 0 do 9.
Výsledkem range(n) není přímo seznam, ale tzv. objekt range.
(podívejte se, co přesně vygeneruje range(10) a list(range(10))).
POZOR: v naší sbírce se chová funkce range nesprávně a po jejím
zavolání získáme přímo seznam. Ve svých programech byste se ale na toto
chování neměli spoléhat.
Funkce
Abychom nemuseli psát některé skupiny příkazů pořád dokola, můžeme je seskupovat do takových pojmenovaných balíčků, kterým se říká funkce. Krom toho, že je funkce pojmenovaná skupina příkazů (pro názvy funkcí platí to samé jako pro názvy proměnných), mohou funkce definovat tzv. parametry, což je něco podobného jako proměnná jenom s tím rozdílem, že hodnotu parametrů dostáváme jako vstup ve chvíli, kdy se funkce používá. Funkce toho umí ještě o trochu více (návratové hodnoty), to ovšem uvidíte až v dalších kapitolách.
2.1. Posloupnosti¶
2.1.1. Sudá čísla¶
Napište funkci, která vypíše prvních n sudých čísel větších než 0.
def even_numbers(n):
pass
# 2 4 6 8 10 12 14 16 18 20
even_numbers(10)
2.1.2. Mocniny¶
Napište funkci, která vypíše prvních n mocnin o daném základu.
def powers(base, n):
pass
# 1 2 4 8 16 32 64 128 256 512
powers(2, 10)
2.1.3. Dělitelé¶
Napište funkci, která vypíše všechny dělitele daného čísla (vzestupně).
def divisors(n):
pass
# 1 2 7 14
divisors(14)
2.1.4. Fibonacci¶
Napište funkci, která vypíše prvních n prvků Fibonacciho posloupnosti.
def fibonacci(n):
pass
# 1 1 2 3 5 8 13 21 34 55
fibonacci(10)
2.1.5. Podposloupnosti¶
Napište funkci, která vypíše prvních n prvků posloupnosti, jejíž první
prvky vypadají následovně:
1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 ...
def subsequences(n):
pass
# 1 1 2 1 2 3 1 2 3 4
subsequences(10)
2.1.6. Alternující řada¶
Napište funkci, která vypíše prvních n prvků posloupnosti, jejíž první
prvky vypadají následovně:
1 -1 2 -2 3 -3 4 -4 5 -5 ...
def alternating(n):
pass
2.2. Tabulky¶
2.2.1. Násobilka¶
Napište funkci, která vypíše tabulku s daným počtem řádků a sloupců (+ popisný řádek a sloupce), kde v každé buňce se nachází součin čísla řádku a čísla sloupce.
def table_products(n):
pass
"""
1 2 3 4 5
- - - - -
1 | 1 2 3 4 5
2 | 2 4 6 8 10
3 | 3 6 9 12 15
4 | 4 8 12 16 20
5 | 5 10 15 20 25
"""
table_products(5)
2.2.2. Mocniny¶
def table_powers(n):
pass
"""
1 2 3 4 5
- - - - -
1 | 1 1 1 1 1
2 | 2 4 8 16 32
3 | 3 9 27 81 243
4 | 4 16 64 256 1024
5 | 5 25 125 625 3125
"""
table_powers(5)
2.2.3. Sčítání¶
def table_additions(n):
pass
"""
1 2 3 4 5
- - - - -
1 | 2 3 4 5 6
2 | 3 4 5 6 7
3 | 4 5 6 7 8
4 | 5 6 7 8 9
5 | 6 7 8 9 10
"""
table_additions(5)
2.2.4. Maximum¶
def table_maxs(n):
pass
"""
1 2 3 4 5
- - - - -
1 | 1 2 3 4 5
2 | 2 2 3 4 5
3 | 3 3 3 4 5
4 | 4 4 4 4 5
5 | 5 5 5 5 5
"""
table_maxs(5)
2.2.5. Zbytek po dělení¶
def table_remainders(n):
pass
"""
1 2 3 4 5
- - - - -
1 | 0 1 1 1 1
2 | 0 0 2 2 2
3 | 0 1 0 3 3
4 | 0 0 1 0 4
5 | 0 1 2 1 0
"""
table_remainders(5)
2.3. Textová grafika¶
2.3.1. Vyplněný čtverec¶
Napište funkci, která v textové grafice vykreslí vyplněný čtverec o straně n.
def square(n):
pass
"""
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
"""
square(5)
2.3.2. Prázdný čtverec¶
Napište funkci, která v textové grafice vykreslí prázdný čtverec o straně n.
def empty_square(n):
pass
"""
# # # # #
# . . . #
# . . . #
# . . . #
# # # # #
"""
empty_square(5)
2.3.3. Pyramida¶
Napište funkci, která v textové grafice vykreslí pyramidu o velikosti n.
def pyramid(n):
pass
"""
#
# # #
# # # # #
# # # # # # #
# # # # # # # # #
"""
pyramid(5)
2.3.4. Šachovnice¶
Napište funkci, která v textové grafice vykreslí šachovnici o velikosti n * n.
def chessboard(n):
pass
"""
# . # . # . # .
. # . # . # . #
# . # . # . # .
. # . # . # . #
# . # . # . # .
. # . # . # . #
# . # . # . # .
. # . # . # . #
"""
chessboard(8)
2.3.5. Kruh¶
Napište funkci, která v textové grafice vykreslí kruh. r udává poloměr kruhu.
def circle(r):
pass
"""
. . . . . . . . . . .
. . . # # # # # . . .
. . # # # # # # # . .
. # # # # # # # # # .
. # # # # # # # # # .
. # # # # # # # # # .
. # # # # # # # # # .
. # # # # # # # # # .
. . # # # # # # # . .
. . . # # # # # . . .
. . . . . . . . . . .
"""
circle(5)
2.3.6. Křힶ
Napište funkci, která v textové grafice vykreslí kříž, jehož ramena budou mít délku n.
def cross(n):
pass
"""
# #
# #
# #
# #
#
# #
# #
# #
# #
"""
cross(5)
2.3.7. Diamant¶
Napište funkci, která v textové grafice vykreslí diamant o straně n.
def diamond(n):
pass
"""
#
# # #
# # # # #
# # # # # # #
# # # # # # # # #
# # # # # # #
# # # # #
# # #
#
"""
diamond(5)
2.3.8. Písmeno „H“¶
Napište funkci, která v textové grafice vykresli velké písmeno „H“ o libovolné výšce větší nebo rovné 3.
def letter_H(size):
pass
2.3.9. Písmeno „N“¶
Napište funkci, která v textové grafice vykreslí velké písmeno „N“ o libovolné výšce větší nebo rovné 3.
def letter_N(size):
pass
2.3.10. Písmeno „Y“¶
Napište funkci, která v textové grafice vykreslí velké písmeno „Y“ o libovolné výšce větší nebo rovné 3.
def letter_Y(size):
pass
2.3.11. Vnořené čtverce¶
Napište funkci nested_squares, která v textové grafice vykreslí n
vnořených čtverců.
def nested_squares(n):
pass
"""
# # # # # # # # #
# #
# # # # # # #
# # # #
# # # # #
# # # #
# # # # # # #
# #
# # # # # # # # #
"""
nested_squares(3)
2.3.12. Extra šachovnice¶
Napište funkci, která v textové grafice vykreslí šachovnici o velikosti n * n
polí, kde m je velikost jednoho pole.
def extra_chessboard(n, m):
pass
"""
# # . . # # . .
# # . . # # . .
. . # # . . # #
. . # # . . # #
# # . . # # . .
# # . . # # . .
. . # # . . # #
. . # # . . # #
"""
extra_chessboard(4, 2)
3. Jednoduché výpočty¶
Návratová hodnota – return
V předchozích kapitolách funkce přímo něco prováděly – pohybovaly želvou nebo něco vypisovaly. Mnohokrát však nepotřebujeme aby funkce přímo něco provedla, ale jen aby něco vypočítala a vypočtenou hodnotu (případně nějaké jiné informace) vrátila, abychom s ní mohli dále pracovat. K tomuto účelu je v Pythonu klíčové slovo return. Příkaz return vrátí hodnotu, která za ním následuje, a okamžitě ukončí výpočet funkce. Tato vrácená hodnota je následně dostupná v místě volání funkce a lze s ní dále pracovat. Naprostá většina funkcí vestavěných v Pythonu něco vrací, například funkce round vrací zaokrouhlené číslo, funkce abs vrací absolutní hodnotu zadaného čísla, atd…
Důležitá a často zapomenutá vlastnost return je okamžité ukončení provádění funkce – typicky v případech kdy už funkce odvedla svoji práci a něco vrátila, takže není potřeba nic dále počítat.
Využití zastavení výpočtu funkce pomocí return
Cyklus while
V minulé kapitole byl představen cyklus for, který se hodí, když dopředu víme kolikrát cyklus chceme provést, nebo pokud chceme něco provést pro každou položku v seznamu (více v kapitole Řetězce a seznamy). V některých případech však nevíme, kolikrát cyklus chceme provést na začátku cyklení, ale zjistíme to až v jeho průběhu. Pro tyto případy Python má cyklus while, který jen definuje podmínku a dokud tato podmínka platí, tak se tělo cyklu opakovaně provádí.
Výpis mocnin trojky, menší než 10 000
3.1. Pokročilé počítání¶
Součet čísel od 1 do n
Napište funkci series_sum(n), která vrátí součet čísel od 1 do n.
3.1.1. Faktoriál pomocí for¶
Napište funkci factorial(n), která vrací faktoriál čísla n
a využívá cyklus for. Připomeňme, že n! = 1·2·3· ... ·n a že 0! = 1.
def factorial(n):
pass
def test_factorial():
assert factorial(0) == 1
assert factorial(1) == 1
assert factorial(10) == 3628800
assert factorial(50) == 30414093201713378043612608166064768844377641568960512000000000000
3.1.2. Faktoriál pomocí while¶
Napište funkci factorial(n), která vrací faktoriál čísla n
a využívá cyklus while.
def factorial(n):
pass
def test_factorial():
assert factorial(0) == 1
assert factorial(1) == 1
assert factorial(10) == 3628800
assert factorial(50) == 30414093201713378043612608166064768844377641568960512000000000000
3.1.3. Ciferný součet¶
Napište funkci digit_sum(n), která vrátí
ciferný součet čísla n.
def digit_sum(n):
pass
def test_digit_sum():
assert digit_sum(0) == 0
assert digit_sum(274) == 13
assert digit_sum(123456789) == 45
3.1.4. Opakovaný ciferný součet¶
Napište funkci repeated_digit_sum(n), která vypočítá ciferný součet čísla n.
Ze získaného ciferného součtu opět vypočítá ciferný součet a tento postup opakuje dokud nezbude jednociferné číslo,
které vrátí. Zkuste své řešení rozložit do dvou funkcí.
def repeated_digit_sum(n):
pass
def test_repeated_digit_sum():
assert repeated_digit_sum(123) == 6
assert repeated_digit_sum(123456789) == 9
assert repeated_digit_sum(99989788879879) == 7
3.2. Dělitelnost a prvočísla¶
Připomeňme pár informací. Celé číslo (int) a je dělitelem b pokud existuje celé číslo c tak, že a · c = b –
jednoduše řečeno: zbytek po dělení b / a je 0. Zbytek po dělení v Pythonu získáme pomocí operace b % a.
Prvočísla jsou pak přirozená čísla n, která mají právě dva dělitele (1 a n) – tedy 1 není prvočíslo.
Snažte se využívat funkce, které jste již dříve implementovali. Ušetříte tak čas a kód bude více srozumitelný. Obecně také lze říci, že pokud máte někde v programu dvakrát ten stejný nebo velmi podobný kód, něco je špatně. Zkuste společný kód abstrahovat do zvláštní funkce a tu pak jen volat s různými parametry.
Následující funkce shoping_list pouze vypíše nákupní seznam ve speciálním formátu.
Přestože výsledek je netriviální, samotná funkce zůstává jednoduchá díky volání funkce frame,
která se stará o formátování.
3.2.1. Dělitelé¶
Napište funkci divisors(n), která vypíše všechny dělitele čísla n.
def divisors(n):
pass
divisors(1) # 1
divisors(5) # 1 5
divisors(42) # 1 2 3 6 7 14 21 42
divisors(127) # 1 127
divisors(1024) # 1 2 4 8 16 32 64 128 256 512 1024
3.2.2. Počet dělitelů¶
Napište funkci divisors_count(n), která vrátí počet dělitelů čísla n.
def divisors_count(n):
pass
def test_divisors_count():
assert divisors_count(1) == 1
assert divisors_count(5) == 2
assert divisors_count(42) == 8
assert divisors_count(127) == 2
assert divisors_count(1024) == 11
3.2.3. Je prvočíslo¶
Napište funkci is_prime(n), která vrátí True pokud je číslo n prvočíslo, jinak False.
def is_prime(n):
pass
def test_is_prime():
assert is_prime(1) == False
assert is_prime(2) == True
assert is_prime(3) == True
assert is_prime(42) == False
assert is_prime(127) == True
3.2.4. Prvočísla menší než n¶
Napište funkci primes_less_than(limit), která vypíše všechna prvočísla menší než limit.
def primes_less_than(limit):
pass
primes_less_than(5) # 2 3
primes_less_than(15) # 2 3 5 7 11 13
primes_less_than(100)
# 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
3.2.5. k-té prvočíslo¶
Napište funkci kth_prime(k), která vrátí k-té prvočíslo.
def kth_prime(k):
pass
def test_kth_prime():
assert kth_prime(1) == 2
assert kth_prime(2) == 3
assert kth_prime(10) == 29
assert kth_prime(100) == 541
3.2.6. Prvních k prvočísel¶
Napište funkci primes(count), která vypíše prvních count prvočísel.
def primes(count):
pass
primes(2) # 2 3
primes(5) # 2 3 5 7 11
primes(10) # 2 3 5 7 11 13 17 19 23 29
3.2.7. Prvních k prvočíselných dvojčat¶
Napište funkci twin_primes(count), která vypíše prvních count
prvočíselných dvojčat.
def twin_primes(count):
pass
twin_primes(2) # 3-5, 5-7,
twin_primes(5) # 3-5, 5-7, 11-13, 17-19, 29-31,
twin_primes(10)
# 3-5, 5-7, 11-13, 17-19, 29-31, 41-43, 59-61, 71-73, 101-103, 107-109,
3.2.8. Rozklad na prvočísla¶
Napište funkci factorization(n), která vypíše
rozklad čísla n na prvočísla (jen jako součin).
def factorization(n):
pass
factorization(2) # 2
factorization(7) # 7
factorization(25) # 5 5
factorization(42) # 2 3 7
factorization(360) # 2 2 2 3 3 5
factorization(1024) # 2 2 2 2 2 2 2 2 2 2
3.2.9. Rozklad na prvočísla s mocninami¶
Napište funkci power_factorization(n), která vypíše
rozklad čísla n na prvočísla v mocninném tvaru.
def power_factorization(n):
pass
power_factorization(2) # 2^1
power_factorization(7) # 7^1
power_factorization(25) # 5^2
power_factorization(42) # 2^1 3^1 7^1
power_factorization(360) # 2^3 3^2 5^1
power_factorization(1024) # 2^10
3.2.10. Největší společný dělitel - naivně¶
Napište funkci gcd(a, b), která vrátí
největší společný dělitel
čísel a a b. Funkce může pracovat naivně, tj. zkoušet všechny možnosti a podobně.
def gcd(a, b):
pass
def test_gcd():
assert gcd(5, 7) == 1
assert gcd(8, 8) == 8
assert gcd(10, 5) == 5
assert gcd(5, 10) == 5
assert gcd(42, 36) == 6
assert gcd(0, 7) == 7
3.2.11. Nejmenší společný násobek¶
Napište funkci lcm(a, b), která vrátí
nejmenší společný násobek
čísel a a b.
def lcm(a, b):
pass
def test_lcm():
assert lcm(6, 9) == 18
assert lcm(6, 7) == 42
assert lcm(3, 9) == 9
assert lcm(9, 3) == 9
assert lcm(360, 42) == 2520
3.2.12. Euklidův algoritmus¶
Implementujte Euklidův algoritmus.
def euclid(a, b):
pass
def test_euclid():
assert euclid(5, 7) == 1
assert euclid(8, 8) == 8
assert euclid(10, 5) == 5
assert euclid(5, 10) == 5
assert euclid(42, 36) == 6
3.3. Aproximace¶
3.3.1. Eulerovo číslo¶
Napište funkci e() pro přibližný výpočet
Eulerova čísla
pomocí nekonečného součtu s přesností na miliontiny.
def e():
pass
print(e()) # 2.718282
3.3.2. Pi¶
Napište funkci pi() pro přibližný výpočet
čísla pi
pomocí Leibnizovy řady s přesností na tisíciny.
def pi():
pass
print(pi()) # 3.141
3.3.3. Aproximace sinu¶
Napište funkci sinus(x) pro výpočet sinu úhlu x (v radiánech) pomocí
Taylorovy řady
(sekce Příklady Taylorova rozvoje: sin x) s přesností na tisíciny.
from math import pi
def sinus(x):
pass
print(sinus(1.2)) # 0.932
print(sinus(0)) # 0.0
print(sinus(pi/4)) # 0.707
print(sinus(pi/2)) # 1.0
3.3.4. Aproximace cosinu¶
Napište funkci cosinus(x) pro výpočet cosinu úhlu x (v radiánech) pomocí
Taylorovy řady
(sekce Příklady Taylorova rozvoje: cosin x) s přesností na tisíciny.
from math import pi
def cosinus(x):
pass
print(cosinus(1.2)) # 0.362
print(cosinus(0)) # 1.0
print(cosinus(pi/4)) # 0.707
print(cosinus(pi/2)) # 0.0
3.4. Převody mezi číselnými soustavami¶
Motivační vtip:
Q: Why do programmers always mix up Halloween and Christmas?
A: Because Oct 31 == Dec 25!
3.4.1. Převod z desítkové soustavy do dvojkové¶
Napište funkci convert_10_to_2(n), která vrátí zadané číslo n ve dvojkové soustavě jako řetězec.
def convert_10_to_2(x):
pass
def test_convert_10_to_2():
assert convert_10_to_2(2) == "10"
assert convert_10_to_2(8) == "1000"
assert convert_10_to_2(10) == "1010"
assert convert_10_to_2(31) == "11111"
assert convert_10_to_2(42) == "101010"
3.4.2. Převod z dvojkové soustavy do desítkové¶
Napište funkci convert_2_to_10(n), která vrátí zadaný řetězec n
reprezentující binární číslo v desítkové soustavě jako int.
def convert_2_to_10(n):
for b in n[::-1]:
b # jednotlive bity od zadu
def test_convert_2_to_10():
assert convert_2_to_10("10") == 2
assert convert_2_to_10("1000") == 8
assert convert_2_to_10("1010") == 10
assert convert_2_to_10("11111") == 31
assert convert_2_to_10("101010") == 42
3.4.3. Převod z desítkové soustavy do jiné¶
Napište funkci convert_10_to_x(n, symbols), která vrátí zadané číslo n v jiné soustavě
– soustava, do které převádíme, bude zadána řetězcem znaků symbols, které používá.
def convert_10_to_x(n, symbols):
pass
def test_convert_10_to_x():
assert convert_10_to_x(42, "01") == "101010"
assert convert_10_to_x(42, "0123") == "222"
assert convert_10_to_x(42, "0123456789") == "42"
assert convert_10_to_x(42, "0123456789ABCDEF") == "2A"
4. Náhodná čísla¶
V této kapitole se budeme věnovat (pseudo)náhodným číslům, která se při různých programátorských úkolech hodí, protože ne vždy chceme, aby počítač prováděl náš program pořád stejně dokola, ale aby do něj vnesl nějakou náhodu. Například kdyby počítač měl simulovat hru člověče, chceme, aby dvě hry za sebou nebyly stejné (tzn. neměly stejné hody, respektive, aby to bylo málo pravděpodobné).
Příklady této kapitoly se budou zabývat generováním těchto pseudonáhodných čísel, zjišťování statistik o těchto číslech a simulací různých problémů.
Co je to náhodné číslo
Je taková devítka náhodné číslo? O konkrétním čísle to už nelze říct. Náhodné číslo je pojem označující číslo/prvek z nějakého ohraničeného intervalu/množiny, které není možné předem předvídat na základě hodnot vygenerovaných dříve. Jednoduše pochopitelným příkladem je férová (neupravená) šestistěnná kostka, u níž nevíte co vám při následujícím hodu padne za číslo. Víte jen, že to bude číslo z intervalu [1,6] a že každé číslo padá stejně často, tedy rozložení čísel je uniformní (rovnoměrné). Existují i další rozložení, ale v této kapitole je potřebovat nebudeme.
(zdroj: XKCD)
Pseudonáhodná čísla
„Kdokoliv, kdo zvažuje získávání náhodných čísel pomocí aritmetických metod se nachází ve stavu hříchu.“. V této slavné větě se vyjadřuje John von Neumann k tomu, že počítače jsou konstrukcí deterministické a s generováním opravdu náhodných čísel mají poměrně problém. Generování opravdu náhodných čísel typicky závisí na externích zařízení jako jsou rozpady radioktivních látek atp. Pro velkou část vstupů se ale obejdeme s pseudonáhodnými čísly, která vykazují jen některé náhodnostní rysy. Pro účely tohoto předmětu nám tyto pseudonáhodná čísla stačí. Zmíníme-li někdy náhodná, máme namysli pseudonáhodná.
Jak je používat v Pythonu
Funkce pro práci s náhodnými čísly se nacházejí v samostatném modulu
random a jsou to randint(nejnizsi, nejvyssi), která vygeneruje
číslo v intervalu [nejnizsi, nejvyssi] a random(), která vygeneruje
číslo v intervalu [0.0,1):
Python generuje čísla deterministicky
Python (a další programovací jazyky) generují pseudonáhodná čísla z takzvaného semínka (seedu) za pomoci deterministických metod. Proto dvě spuštění následujícího kódu vygenerují stejné náhodné číslo.
4.1. Hrátky s náhodností¶
4.1.1. Šestiboká kostka¶
Napište funkci, která bude vracet nově vygenerované náhodné číslo simulující šestistěnnou kostku s čísly 1–6.
from random import randint
def dice():
pass
print(dice(), dice(), dice())
4.1.2. Dokud padá sudé číslo¶
Napište funkci, která bude provádět házení obyčejnou šestistěnnou kostkou tak dlouho dokud nepadne liché číslo. Poté funkce vrátí celkový součet všech hozených hodů.
from random import randint
def turn():
pass
print(turn(), turn(), turn())
4.1.3. Statistiky¶
Napište funkci, která vygeneruje a vypíše count náhodných čísel v intervalu
[lower, upper] a následně vypíše nejmenší, největší číslo. Vypište také
aritmetický průměr ze všech vygenerovnaých čísel.
from random import randint
def statistics(count, lower, upper):
pass
statistics(10, 1, 100)
4.1.4. Frekvence kostky¶
Napište funkci, která provede count hodů obyčejnou šestibokou kostkou a
následně vypíše kolikrát které číslo padlo. Tip: pro ukládání frekvencí se
mohou hodit seznamy z následující kapitoly či
nějaká jiná datová struktura.
from random import randint
def dice_freq(count):
pass
dice_freq(1000)
4.1.5. Frekvence součtu hodů dvou kostek¶
Napište funkci, která provede count hodů dvěma šestibokými kostkami,
následně vypíše kolikrát daný součet (2 až 12) padl. Tip: pro ukládání
frekvencí se mohou hodit seznamy z následující kapitoly či nějaká jiná datová struktura.
from random import randint
def two_dice_freq(count):
pass
two_dice_freq(1000)
4.1.6. Falešná mince¶
Napište funkci, která bude simulovat falešnou minci (hlava je True a orel
je False). Hlava padá s pravděpodobností 85 % a orel s pravděpodobností 15
%.
from random import randint, random
def coin_flip():
pass
print(coin_flip())
4.2. Simulace a analýzy¶
4.2.1. Opilec na cestě domů¶
Opilec je na půli cesty mezi domovem a hospodou, každý krok udělá náhodně jedním směrem. Napište funkci, která bude simulovat opilcův pohyb. Jejími parametry budou vzdálenost mezi domovem a hospodou a počet kroků do opilcova usnutí (tj. maximální délka simulace). Simulace skončí buď tehdy, když opilec dojede domů nebo do hospody, případně po vyčerpání počtu kroků.
Ukázkový výstup:
>>> drunkman_simulator(10, 100)
home . . . . . * . . . . pub
home . . . . * . . . . . pub
home . . . * . . . . . . pub
home . . . . * . . . . . pub
home . . . * . . . . . . pub
home . . . . * . . . . . pub
home . . . * . . . . . . pub
home . . * . . . . . . . pub
home . * . . . . . . . . pub
home . . * . . . . . . . pub
home . . . * . . . . . . pub
home . . * . . . . . . . pub
home . . . * . . . . . . pub
home . . * . . . . . . . pub
home . . . * . . . . . . pub
home . . . . * . . . . . pub
home . . . . . * . . . . pub
home . . . . * . . . . . pub
home . . . . . * . . . . pub
home . . . . * . . . . . pub
home . . . . . * . . . . pub
home . . . . . . * . . . pub
home . . . . . * . . . . pub
home . . . . . . * . . . pub
home . . . . . . . * . . pub
home . . . . . . . . * . pub
home . . . . . . . . . * pub
home . . . . . . . . * . pub
home . . . . . . . . . * pub
home . . . . . . . . . . pub
Ended in the pub again!
from random import randint, random
def drunkman_simulator(size, steps):
pass
drunkman_simulator(10, 100)
Vyzkoušejte různé kombinace parametrů? Při jaké konfigurace dochází domů už celkem pravidelně?
4.2.2. Analýza opilce¶
Pokud jste se zabývali otázkami položenými v předchozím příkladu, zjistili jste, že to není až tak jednoduché zjistit. V tomto příkladu tedy použijeme předchozí program pro jednoduchou analýzu, jak to dopadne, když to zkusíme zopakovat vícekrát za sebou.
Nejprve upravte funkci z předchozí příkladu tak, aby nevypisovala stav opilce
(například přidáním volitelného parametru output a zapodmínkováním výpisu)
a aby vracela True dojde-li opilec domů a False pokud ne.
Následně napište funkci, která provede simulaci opilce count krát a vypíše
procentuální úspěšnost dojití domů.
from random import randint, random
def drunkman_simulator(size, steps, output=False):
pass
def drunkman_analysis(size, steps, count):
pass
drunkman_analysis(10, 100, 100)
# Arriving home in 45.0 % of cases
4.2.3. Hledač pokladů¶
Máme hledače pokladů, který hledá právě jeden ukrytý poklad ve čtverci o hraně
width polí. Hledač začíná na pozici [0,0] (vlevo nahoře) a v každém
kroku se pohne jedním ze 4 směrů se stejnou pravděpodobností. Pokud by měl
vyjít ze čtverce, zůstává stát (a jeho neúspěšný krok se započítá).
Napište funkci, která pro zadanou šířku width zjistí, zdali v steps
krocích hledač najde poklad.
Následně napište funkci, která provede předchozí funkci pro zadaný parametr
count krát a vypíše, jaká je pravděpodobnost nalezení pokladu.
Poklad na začátku umístěte na náhodnou pozici.
from random import randint, random
def treasure_hunter(width, steps):
pass
def treasure_hunter_analysis(width, steps, count):
pass
treasure_hunter_analysis(10, 100, 100)
#Treasure found in 33.0 % of cases
4.2.4. Čekání na tramvaj¶
Chcete vědět, jak dlouho budete čekat na zastávce šaliny. Šalina jezdí každých
n minut. Nasimulujte count náhodných příchodů na zastávku (v náhodné
časy). Vytiskněte, v kolika procentech případů budete čekat déle než w
minut.
from random import randint
def tramway_waiting_more_than(w, n, count):
pass
tramway_waiting_more_than(4, 5, 100)
Srovnejte nasimulovanou pravděpodobnost s vypočítanou pravděpodobností (pomocí geometrické pravděpodobnosti).
4.2.5. Průměrná vzdálenost dvou bodů ve čtverci¶
Napište funkci, která náhodně zvolí dva body ze čtverce o velikosti size a
vrátí jejich vzdálenost. Následně napište funkci, která tento výběr bude
opakovat count krát a vypíše průměrnou vzdálenost.
from random import randint, random
def random_points_distance(size):
pass
def average_points_distance(count, size):
pass
print(average_points_distance(100, 5))
4.2.6. Tipující student¶
Napište funkci, která experimentálně zjistí (pro count pokusů) jaká je
pravděpodobnost, že student natipuje alespoň polovinu n otázkového testu,
ve kterém každá otázka má právě 4 možnosti a právě jedna z nich je správně.
from random import randint
def random_student(n, count):
pass
random_student(10, 100)
Srovnejte experimentálně zjištěnou hodnotu s teoreticky odvozenou hodnotou.
4.2.7. Odhad čísla PI¶
Naprogramujte funkci využívající náhodná čísla pro odhad čísla PI za použití metody Monte Carlo, podrobnější popis viz http://mathfaculty.fullerton.edu/mathews//n2003/montecarlopimod.html
- Shrnutí algoritmu:
Potřebujete n náhodných bodů ve čtverci o hraně a
Z n vygenerovaných bodů leží nějaký počet m v kruhu vepsanému tomuto čtverci
Obsah čtverce je
S2 = a^2Obsah kruhu je
S1 = PI * (a/2)^2Odhad PI je
PI = 4 * (m/n)
from random import randint, random
def guess_pi(count):
pass
print(guess_pi(1000))
Jaký je vztah mezi počtem pokusů a výsledným odhadnutým číslem PI? Proč?
4.2.8. Náhodné pexeso¶
Naprogramujte funkci, která nasimuluje jednu hru pexesa na jednorozměrném
hracím plánu o velikosti size a vrátí počet provedených tahů. Poté zjistěte
průměrnou délku jedné hry, pro hrací pole různých délek.
Poznámky: v tomto příkladu využijete seznamy, nezapomeňte také, že velikost šachovnice podléhá jistým omezením, které správný programátor zkontroluje.
from random import randint, shuffle
def pexeso(size, output = False):
pass
def average_pexeso_length(board_sizes = range(2, 20, 2), count = 100):
pass
print(pexeso(10, True))
average_pexeso_length()
5. Řetězce a seznamy¶
5.1. Seznamy¶
Seznam je datová struktura pro uložení více prvků, např. posloupnosti čísel nebo slov ve větě.
Pro práci se seznamy je připraveno několik užitečných funkcí. Dokážete odhadnout, co která dělá?
Pomocí for cyklu můžeme projít všechny prvky seznamu:
Odkazy a kopie
Pokud máme seznam values a provedeme a = values,
nevytváří se nová kopie pole, v paměti bude stále jediné,
akorát se na něj budou nyní odkazovat 2 proměnné.
(codelens_lists_demo)
Pokud potřebujete kopii pole, použijte příkaz a = list(values).
(codelens_lists_demo2)
Pokud budete někdy vytvářet kopii složitější datové struktury (např. seznamu seznamů),
použijte funkci deepcopy z knihovny copy.
Slicing
Slicing je jednoduchý způsob, jak získat nějakou podčást (výřez) seznamu.
5.1.1. Součet, maximum a hledání¶
Napište funkce nad seznamem čísel, které zjistí:
součet všech čísel v seznamu,
nejvyšší číslo v seznamu,
zda se určitá hodnota vyskytuje v seznamu,
tedy ekvivalenty operací max, sum a in (ale s použitím pouze
základních operací nad seznamy).
def my_sum(numbers):
pass
def my_max(numbers):
pass
def my_in(x, array):
pass
def test_sum_max_in():
assert my_sum([6, 5, 11, 8]) == 30
assert my_max([6, 5, 11, 8]) == 11
assert my_max([-10, -3, -5]) == -3
assert my_in(5, [6, 5, 11, 8]) == True
assert my_in(4, [6, 5, 11, 8]) == False
5.1.2. Součin nenulových čísel¶
Napište funkci, která vypočítá součin čísel v seznamu, ale ignoruje přitom případné nuly.
def nonzero_product(numbers):
pass
def test_nonzero_product():
assert nonzero_product([0, 2, 3, 0, 0, 3]) == 18
assert nonzero_product([0, 0, 0, 0]) == 1
5.1.3. Modifikace vs. vytváření nového seznamu¶
Napište funkci double_all, která dostane na vstupu seznam čísel a každý
jeho prvek vynásobí dvěma. Dále napište funkci create_doubled, která
dostane na vstupu seznam čísel a vrátí nový seznam získaný ze vstupního tak, že
každý prvek vynásobí dvěma. Na rozdíl od předchozí funkce však nemění předaný
seznam.
def double_all(numbers):
pass
def test_double_all():
a = [1, 4, 2, 5]
double_all(a)
assert a == [2, 8, 4, 10]
def create_doubled(numbers):
pass
def test_create_doubled():
a = [1, 4, 2, 5]
b = create_doubled(a)
assert a == [1, 4, 2, 5]
assert b == [2, 8, 4, 10]
5.1.4. Zploštění¶
Napište funkci, jejímž vstupem je seznam seznamů a výstupem je seznam, který obsahuje prvky všech jednotlivých seznamů.
def flatten(lists):
pass
def test_flatten():
assert flatten([[0, 2, 3], [1, 2, 3], [9, 10]]) == [0, 2, 3, 1, 2, 3, 9, 10]
5.2. Řetězce¶
Samotný počítač pracuje s binárními čísly, ale protože my lidé raději pracujeme s desítkovými čísly a ještě raději s písmenky a z něho složeným textem. Postupně tak přibyla do většiny programovacích jazyků možnost jak s písmenky a texty z nich složených pracovat velmi jednoduchým a efektivním způsobem. Python v tomto ohledu není výjimkou a v této sekci se právě tomu, jak se s písmenky pracuje Pythonu budeme věnovat.
Co je to řetězec
Řetězec (= string) je nemodifikovatelná posloupnost po sobě jdoucích znaků
(charů), která je datového typu str, například jednou z takových
posloupností znaků h, j, o a a může být ahoj.
Jak vytvářet řetězce
Když chceme vytvořit řetězec musíme náš text obalit do mezi "
(uvozovek), ‘ (apostrofů) případně """ (trojitých uvozovek), ale
poslednímu způsobu se budeme věnovat, protože je oproti těm prvním dvěma
speciální.
Vyzkoušejte si
Číslo vs řetězec
Jako lidé je nám celkem jedno jestli je 42 číslo nebo text. Python je
ale v tomhle ohledu poněkud striknější, protože potřebuje vědět jak s ním
má zacházet.
Intuitivně byste řekli, že 6 je přece 6! Jenže proto, aby mohly být dvě
hodnoty sobě rovné, musí nejdřív souhlasit jejich datový typ a to v tomto
případě nesouhlasí (str není int). Na toto místo patří ještě
poznámka, že ne všechny programovací jazyky se k tomuto staví stejně.
Existují programovací jazyky, které vám hodnoty automaticky převedou do
nějakého typu, ve kterém se porovnání dá provést… Diskuze o tom, zdali
je to moudré jsou vždy vděčným způsobem jak mezi programátory rozpoutat
pořádnou flame-war.
A když tedy potřebujete pracovat s číslem jako řetězcem, použijte třeba
funkci str(42).
Speciální znaky
S některými znaky v řetězcích musíme zacházet jinak než s ostatními.
Například když chceme udělat nový řádek, nemůžeme použít odřádkování pomocí
klávesy Enter, ale musíme místo ní napsat sekvenci \n (zpětné lomítko
následované znakem n). Znak je \ má uvnitř řetězců speciální
význam, říká, že se spolu se znakem po něm má nahradit něčím jiným. Což
znamená také znamená, že abychom do řetězce dostali znak \ musíme zadat
\\.
Taktéž s uvozovkami a apostrofy můžeme narazit, pokusíme-li se je použít v řetězci, který jako obalovací znaky používá stejný znak. Python by v takovém případě považoval nalezený znak za konec řetězce a vše co následuje za ním za další kód.
Víceřádkové řetězce
Protože je někdy můžeme chtít používat delší řetězce se řadou nových řádků,
může být přehlednější obalit náš text pomocí """ (trojích uvozovek), v
rámci něhož stačí udělat normální odřádkování pomocí klávesy Enter.
Tenhle postup se též může hodit jako svérázný (a rychlý) způsob zakomentování většího množství řádků, trik spočívá v tom, že řetězec se nikam neuloží, takže se prostě zahodí:
"""
def foo():
some problematic code
"""
Základní operace s řetězci
Jak jsme si nastínili v úvodu je řetězec posloupnost znaků, očíslovaná od
začátku řetězce od 0 (což znamená být že poslední znak je na pozici délky
řetězce mínus 1!) a můžeme k nim přistupovat pomocí hranatých závorek.
Dalšími základními operacemi je zjištění její délky pomocí funkce
len(retezec), jejich zřetězení (konkatenace) pomocí operátoru + a
opakování pomocí operátoru *.
Řetězec je ale neměnný, nemůžeme na danou pozici přiřadit žádný nový znak:
Další operace
Může nás též zajímat, zda-li nějaký znak je v řetězci přítomen, k tomu
slouží operátor in. Také můžeme nad řetězce iterovat po jednom znaku.
Každé písmeno má přiřazenou svou číselnou reprezentaci, tu můžeme získat
pomocí funkce ord(znak), pro opačný směr slouží funkce chr(znak).
Další užitečné funkce jsou retezec.upper() a retezec.lower(), které
převedou celý řetězec na velká/malá písmena.
Krájení (slicování)
Někdy se může velmi hodit získat pouze nějakou podčást řetězce. K tomu se používá tzv. slicování (krájení). Která funguje, že definujeme od, do a každý kolikátý znak chceme. Pohrajte si:
5.2.1. Prokládání textu textem¶
Napište funkci, která mezi každá dvě písmena daného textu vloží dodaný text.
def dummy(text, rubbish):
pass
def test_dummy():
assert dummy('pampeliska', '') == 'pampeliska'
assert dummy('pampeliska', 'X') == 'pXaXmXpXeXlXiXsXkXa'
assert dummy('pampeliska', 'XX') == 'pXXaXXmXXpXXeXXlXXiXXsXXkXXa'
5.2.2. Zdvojení písmen¶
Napište funkci, která vrátí nový řetězec, ve kterém bylo každé písmenko zdvojeno.
def duplication(text):
pass
def test_duplication():
assert duplication("PYTHON") == "PPYYTTHHOONN"
5.2.3. Pozpátku¶
Napište funkci, která vám vrátí řetězec s písmeny uspořádanými pozpátku.
def reverse(text):
pass
def test_reverse():
assert reverse('ONMEJATEJOLSEH') == "HESLOJETAJEMNO"
5.2.4. Cenzura¶
Napište funkci, která zcenzuruje dodaný řetězec tak, že každý druhý znak
nahradí za X.
def censorship(text):
pass
def test_censorship():
assert censorship("Vinnetou: Jsem krestan.") == "VXnXeXoX:XJXeX XrXsXaX."
5.2.5. Počet A¶
Napište funkci, která spočítá počet výskytů písmene (znaku) A/a.
def count_a(text):
pass
def test_count_a():
assert count_a('Liska Adelka') == 3
5.2.6. Znaky na stejných pozicích¶
Napište funkci, která dostane dva řetězce a vypíše ty znaky, které jsou na shodných pozicích stejné.
def string_intersection(left, right):
pass
string_intersection('ZIRAFA', 'KARAFA')
# R A F A
string_intersection('PES', 'KOCKA')
# (prazdny retezec)
5.2.7. Rozdíl v počtu a¶
Napište funkci příjimající dva řetězce, která vypíše informaci o tom, který z řetězců obsahuje méně znaků ‘a’/’A’ a jaký je absolutní rozdíl mezi počty ‘a’/’A’ mezi oběma řetězci. Případně vypíše, že je počet áček v obou řetězcích stejný.
def diff_a(left, right):
pass
diff_a("AstalaVistas", "Jehovista")
# Second string contains less 'a'/'A': 3
diff_a("", "")
# Both strings contain same number of 'a'/'A'
5.2.8. Palindrom¶
Napište funkci, která vrátí, zda je řetězec palindromem. Palindromem je takové
slovo či věta, která má při čtení v libovolném směru stejný význam, například
nepotopen či jelenovi pivo nelej (mezery můžete ignorovat).
def palindrom(text):
pass
def test_palindrom():
assert palindrom("JELENOVIPIVONELEJ") == True
5.2.9. Hodnota slova¶
Každý znak A-Z má hodnotu 1-26 (diakritiku a velikost písmen pro tento příklad ignorujte). Napište funkci, která spočítá a vrátí hodnotu vloženého řetězce (slova).
def word_value(text):
pass
def test_word_value():
assert word_value("AHOJ") == 34
5.2.10. Divný filtr¶
Napište funkci, která profiltruje vstupní text následujícím způsobem: sečte hodnoty dvou předchozích písmen (A–Z jsou 1–26, diakritiku a velikost písmen můžete pro tento příklad ignorovat) a pokud bude rovna hodnotě aktuálního písmene, odstraní ho.
Poznámka: pokud písmeno odstraníte už jej nikdy nepoužijete ;-)
def strange_filter(text):
pass
def test_strange_filter():
assert strange_filter("ABCDEIGHO") == "ABDEGH"
5.2.11. Kapitalizace slov¶
Napište funkci pro kapitalizaci všech slov v dodaném vstupním řetězci.
def capitalize(text):
pass
def test_capitalize():
assert capitalize("jenom tak klidne levituji ve vzduchu.") == "Jenom Tak Klidne Levituji Ve Vzduchu."
5.2.12. Náhodný řetězec¶
Napište funkci pro generování náhodných řetězců, která bude brát dva parametry:
length udávající délku výstupu a chars obsahující řetězec všech
povolených znaků.
from random import randint
def random_string(length, chars):
pass
print(random_string(10, "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"))
5.2.13. Naivní hledání¶
Napište funkci se dvěma parametry needle (jehla) a haystack (kupka
sena) pro hledání začáteční pozice subřetězce. Pokud nebude podřetězec nalezen
vrátí funkce -1.
Poznámka: použijte naivní algoritmus… ona existuje spousta chytrých algoritmů na hledání podřetězců, jejichž pochopení a implementace je nad rámec tohoto předmětu.
def search(needle, haystack):
pass
def test_search():
assert search("tri", "bratri") == 3
5.3. Šifry a jiné kratochvíle¶
Od pradávna existovali lidé, kteří potřebovali ukrývat význam zpráv před nechtěnými zraky nepovolaných či přímo nepřátelských lidí. Například historie Caesarovy šifry se táhne až k Juliu Caesarovi a od té doby je v neustálém hledáčku států a bezpečnosti… S nástupem sofistikovaných strojů se objevily různé „neprolomitelné“ šifrovací zařízení. Jedním z klasických je německá Enigma z druhé světové války, jejíž prolomení vedlo k založení informatiky jako vědecké disciplíny a vedlo k dnešním počítačům.
Co je to šifrování
Šifrování je proces, při kterém z nějakého nezašifrovaného textu (plaintextu) pomocí jistého principu (například posunu) a znalosti (hesla, klíče,…) vytvoříme zašifrovaný text. Z tohoto zašifrovaného textu je pak v ideálním případě původní text zjistitelný pouze velmi obtížně či příliš zdlouhavě. Šifrování je velmi komplexní téma a zabývá se jím kryptografie, více se můžete dozvědět například v předmětu PV080.
Proč se budeme zabývat šifrováním
V rámci této podkapitoly se budeme věnovat jednodušším a známým šifrám, protože umí velmi dobře posloužit na procvičení práce s řetězci, seznamy a znaky.
Chcete-li potrápit své mozkové závity u šifer neznámých a třeba využít své nově nabyté programátorské schopnosti poohlédněte se po šifrovačkách, například InterLoS či TMOU.
5.3.1. Caesarova šifra¶
Napište funkci, která zašifruje text tak, že posune všechna jeho písmena v abecedě o n dopředu (cyklicky), můžete se inspirovat popisem Caesarovy šifry.
def caesar(text, klic):
pass
def test_caesar():
assert caesar('zirafa', 3) == "CLUDID"
5.3.2. Vigenèrova šifra¶
Napište funkci, která zašifruje text podle předem daného klíče. Pro posun písmen zdrojového textu se postupně používají písmena z klíče: ‘a’ posouvá o 0, ‘b’ o 1, … ‘z’ o 25. Pokud je klíč kratší než zdrojový text, jsou použita písmena z klíče opět od začátku. Můžete se inspirovat popisem Vigenèrovy šifry.
def vigenere(text, klic):
pass
def test_vigenere():
assert vigenere('pampeliska', 'klic') == "ZLUROWQUUL"
5.3.3. Protřepat, nemíchat¶
Vytvořte funkci, která bude na vstupu brát text a číslo. Funkce vrátí text kde jednotlivé n-tice budou vždy pozpátku.
def tuple_reverse(text, n):
pass
def test_tuple_reverse():
assert tuple_reverse('HESLOJETAJEMNO', 3) == "SEHJOLATEMEJON"
assert tuple_reverse('SEHJOLATEMEJON', 3) == "HESLOJETAJEMNO"
6. Binární vyhledávání, testování, typy¶
6.1. Testování, typy¶
Otypování různých datových typů |
|
|---|---|
seznam |
|
fronta |
|
množina |
|
slovník |
|
union (jeden z typů) |
|
optional
(buď typ nebo |
|
n-tice |
|
|
|
6.1.1. Doplnění typů¶
Otypujte následující funkce. Funkce dice_max(count) vrací nejvyšší číslo,
které padlo na kostce.
from random import randint
def dice():
return randint(1, 6)
def dice_max(count):
maximum = dice()
for _ in range(count-1):
roll = dice()
if roll > maximum:
maximum = roll
return maximum
6.1.2. Doplnění assertu¶
Doplňte do předchozího kódu assert tak, aby funkce dice_max přijímala
pouze count >= 1.
Assert napište na první řádek funkce. Bezprostředně za začátek funkce se často píší asserty, které udávají vstupní podmínky.
6.1.3. Pokročilejší doplnění typů¶
Upravte funkci dice_max z předchozího příkladu tak, aby umožňovala
count == 0 a v takovém případě vrátila None. Upravte typy tak, aby
mypy prošlo! Upravte assert a ponechte jej na začátku funkce.
6.1.4. Testování¶
Napište smysluplné testy (asserty) na funkci palindrom a opravte na základě
testů její chyby.
def palindrom(text):
length = len(text)
for i in range((length-1)//2):
if text[i] != text[length - 1 - i]:
return False
return True
def palindrom_test():
assert palindrom('aa')
assert not palindrom('abc')
# Sem přidejte další případy
palindrom_test()
6.2. Binární vyhledávání¶
V následující kapitole si vyzkoušíme jednoduchou techniku známou jako binární vyhledávání, na které si ilustrujeme, jak některé výpočetní úlohy mohou trvat až překvapivě krátkou dobu.
Následující úlohy budou převážně vycházet z následujícího zadání:
Hrajeme hru dvou hráčů. Jeden s hráčů si myslí číslo z předem zadaného intervalu a cílem druhého hráče je číslo uhodnout. K tomu používá otázky typu „Je číslo, které si myslíš, větší než X?“
Jaká je nejlepší strategie pro druhého hráče, aby položil co nejméně otázek?
Princip binárního vyhledávání
V případě, kdy by nás nezajímal počet otázek, které položíme, mohli bychom klást otázky postupně:
Je číslo, ktere si myslíš, větší než 1?
Je číslo, ktere si myslíš, větší než 2?
Je číslo, ktere si myslíš, větší než 3?
…
V nejhorším případě bychom položili tolik otázek, kolik je možných čísel, které si náš protihráč může myslet. Na druhou stranu bychom mohli položením otázky zkusit vyřadit, co nejvíce možností. Představme si, že si protihráč může myslet čísla od 1 do 1000. Jaká by měla být naše první otázka, aby vyřadila co nejvíce možností bez ohledu na to, jak na ni protihráč odpoví?
Je číslo, které si myslíš, větší než 500?
Bez ohledu na to, jak protihráč odpoví, se mi počet čísel, které musím uvažovat zmenší na polovinu. Představme si, že protihráč odpověděl na naší otázku „ANO“. Která čísla ještě připadají v úvahu? Jaká bude naše další otázka?
Je číslo, které si myslíš, větší než 750?
Touto otázkou se nám opět smrskne na polovinu. Když budeme v této strategii pokračovat a v každém kole se nám počet přípustných čísel zmenší na polovinu, jistě uhádneme protihráčovo číslo v nejhorším případě po desáté otázce. Obecně počet otázek v nejhorším případě odpovídá dvojkovému logaritmu počtu čísel, ze kterých se myšlené číslo vybírá.
Zkuste odhadnout, jaké budou výsledky následujících dvojkových logaritmů.
Uživatelský vstup
Abychom hru dokázali správně naimplementovat, budeme muset načítat vstup od
uživatele. Na to můžeme použít již funkci input. Tato funkce umí
vypsat na obrazovku danou instrukci a počkat na vstup od uživatele. Jakmile
uživatel svůj vstup potvrdí, funkce vrátí řetězec obsahující to, co
uživatel zadal. Pokud chceme s uživatelským vstupem dále pracovat jako
jiným typem (například celé číslo), je vhodné použít přetypování.
6.2.1. Hádání čísla člověkem¶
Napište funkci guess_number_human(upper_bound), která umožňuje hrát s počítačem hru
na hádání čísla: počítač si myslí číslo (celé číslo v intervalu [1, upper_bound]), hráč se ho snaží uhodnout. Po každém pokusu dostane hráč od
počítače informaci, zda je hledané číslo menší nebo větší než to, které si
tipnul. Hru si můžete vyzkoušet zde (klikejte na čísla v pravé části).
from random import randint
def guess_number_human(upper_bound: int) -> None:
pass
# --- pokus c. 1 ---
# Zadej svuj tip: 5
# Moje cislo je mensi.
# --- pokus c. 2 ---
# Zadej svuj tip: 3
# Moje cislo je vetsi.
# --- pokus c. 3 ---
# Zadej svuj tip: 4
# Jo, to je ono!
guess_number_human(10)
6.2.2. Hádání čísla počítačem¶
Napište funkci guess_number_pc(upper_bound), která umožňuje hrát s počítačem
hru na hádání čísla, tentokrát si však číslo myslí uživatel a počítač hádá. Po
každém pokusu si počítač vyžádá od uživatele informaci, zda je myšlené číslo
větší nebo menší než to, které si počítač tipnul.
def guess_number_pc(upper_bound: int) -> None:
pass
# Mysli si cislo od 1 do 10.
# Je cislo 5 mensi (0), rovno (1), nebo vetsi (2) nez tvoje cislo?
# 2
# Je cislo 2 mensi (0), rovno (1), nebo vetsi (2) nez tvoje cislo?
# 2
# Tvoje cislo je 1.
guess_number_pc(10)
6.2.3. Hádání čísla: počítač vs. počítač¶
Napište funkci guess_number_pc_pc(upper_bound), která vykoná hru v hádání
myšleného čísla počítače proti počítači. Na závěr vypíše počet pokusů potřebných k uhádnutí čísla.
from random import randint
def guess_number_pc_pc(upper_bound: int) -> None:
pass
# A: Myslim si cislo od 1 do 10
# --- pokus c. 1 ---
# B: Tipuji 5
# A: Moje cislo je mensi.
# --- pokus c. 2 ---
# B: Tipuji 2
# A: Moje cislo je vetsi.
# --- pokus c. 3 ---
# B: Tipuji 3
# A: Jo, to je ono!
# Uhadnuto na 3 pokusu
guess_number_pc_pc(10)
6.2.4. Binární vyhledávání¶
Napište funkci binary_search(needle, haystack), která zjistí, zda se
hodnota needle nachází ve vzestupně uspořádaném seznamu haystack.
Funkce musí mít logaritmickou časovou složitost.
def binary_search(needle: int, haystack: List[int]) -> bool:
pass
def test_binary_search_basic() -> None:
assert binary_search(5, [1, 2, 5, 8])
assert not binary_search(4, [1, 2, 5, 8])
6.2.5. Otestování binárního vyhledávání¶
Napište funkci test_binary_search_extended a vložte do ní alespoň 5 testů předchozí
funkce binary_search.
6.2.6. Binární vyhledávání pozice¶
Vylepšete předchozí funkci tak, aby vracela index pozice, kde se hledaný prvek nachází. Pokud prvek v seznamu není, vraťte -1.
def binary_search_position(needle: int, haystack: List[int]) -> int:
pass
def test_binary_search_position() -> None:
assert binary_search_position(5, [1, 2, 5, 8]) == 2
assert binary_search_position(4, [1, 2, 5, 8]) == -1
6.2.7. Binární vyhledávání seznamu pozic¶
Vylepšete předchozí funkci tak, aby vracela seznam indexů pozic, na kterých se hledaný prvek vyskytuje. Pokud prvek v seznamu není ani jednou, vrátíte prázdný seznam.
def binary_search_position_list(needle: int, haystack: List[int]) -> List[int]:
pass
def test_binary_search_position_list() -> None:
assert binary_search_position_list(5, [1, 2, 3, 3, 5, 5, 5, 8]) == [4, 5, 6]
assert binary_search_position_list(4, [1, 2, 5, 8]) == []
6.2.8. Umocňování¶
Napište funkci super_power(base, exp), která umocní dané číslo base na
daný exponent exp. Funkce musí mít logaritmickou časovou složitost vzhledem
k hodnotě exponentu.
def super_power(base: int, exp: int) -> int:
pass
def test_super_power() -> None:
assert super_power(2, 7) == 128
assert super_power(5, 15) == 30517578125
7. Algoritmy nad seznamy¶
Přístup do seznamů
Kopírování seznamu
Vnořené seznamy
7.1. Pascalův trojúhelník¶
7.1.1. Trojúhelník¶
Napište funkci triangle(n), která vrací seznam n seznamů takových, že první obsahuje 1 jedničku,
druhý 2 jedničky až poslední n jedniček.
def triangle(n: int) -> List[List[int]]:
pass
def test_triangle() -> None:
assert triangle(0) == []
assert triangle(1) == [[1]]
assert triangle(3) == [[1], [1, 1], [1, 1, 1]]
assert triangle(5) == [[1], [1, 1], [1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1, 1]]
7.1.2. Pascalův trojúhelník – kombinační čísla¶
Napište funkci pascal_binomial(n), která vrací n řádků Pascalova
trojúhelníku.
Trojúhelník bude reprezentovaný jako seznam řádků, kde každý řádek je seznam
hodnot v trojúhelníku. Funkce by měla hodnoty napočítávat pomocí kombinačních
čísel a
měla by využívat následující strukturu.
def factorial(n: int) -> int:
pass
def binomial_coefficient(n: int, k: int) -> int:
pass
def pascal_binomial(n: int) -> List[List[int]]:
pass
def test_pascal_binomial() -> None:
assert pascal_binomial(0) == []
assert pascal_binomial(1) == [[1]]
assert pascal_binomial(3) == [[1], [1, 1], [1, 2, 1]]
assert pascal_binomial(5) == [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
7.1.3. Pascalův trojúhelník – z předchozího řádku¶
Napište funkci pascal(n), která vrací n řádků Pascalova
trojúhelníku.
Trojúhelník bude reprezentovaný jako seznam řádků, kde každý řádek je seznam
hodnot v trojúhelníku. Funkce by měla hodnoty napočítávat jako součet hodnot z
předchozího řádku.
Pro vykreslení trojúhelníku můžete použít pomocnou funkci print_pascal
(tato funkce nebude fungovat v online prostředí).
def pascal(n: int) -> List[List[int]]:
pass
def test_pascal() -> None:
assert pascal(0) == []
assert pascal(1) == [[1]]
assert pascal(3) == [[1], [1, 1], [1, 2, 1]]
assert pascal(5) == [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
def print_pascal(pascal: List[List[int]]) -> None:
max_number_size = len(str(pascal[-1][len(pascal)//2])) + 2
for row in pascal:
line = ""
for x in row:
line += ("{0: ^" + str(max_number_size) + "}").format(x)
print(("{0: ^" + str(max_number_size * len(pascal[-1])) + "}").format(line))
# print_pascal(pascal(7))
7.2. Řadicí algoritmy¶
Řadicí algoritmy mají za úkol seřadit daný seznam (typicky čísel) od nejmenšího po největší (samozřejmě lze řadit i naopak). Takových algoritmů je celá řada a mají různé strategie a vlastnosti. Ve většině programovacích jazyků včetně Pythonu je nějaký řadicí algoritmus již implementován. Vlastní implementace řazení je zde jen z tréningových důvodů. Volba špatného řadícího algoritmu, špatná implementace či ignorování vestavěných může vést k neočekávanému chování programů, jak ilustruje kóan Letní šála. Pro lepší představu jak algoritmy pracují existuje na internetu mnoho vizualizací, které se snaží princip každého algoritmu názorně ukázat (např. http://www.sorting-algorithms.com nebo http://sortvis.org/).
Vaše implementace řadících algoritmů by měla pracovat se zadaným seznamem a
ten upravovat, tj. funkce nic nevrací jen prohazuje položky v daném
seznamu. (prohodit obsah dvou proměnných v Pythonu lze snadno pomocí a,
b = b, a)
Testovací funkce:
- ::
- def sort_tester(sorting_function: Callable[[List[int]], None]) -> None:
- lists = [
[7, 6, 100, 3, 2, 11, -1, 10, 10, 42, 42, 42, 2, 13, 0, -5]
]
- for lst in lists:
returned = sorting_function(lst) if returned:
lst = returned
- for i in range(1, len(lst)):
assert lst[i - 1] <= lst[i]
7.2.1. Bubble sort¶
Implementujte Bubble sort.
def bubble_sort(l: List[int]) -> None:
pass
def test_bubble_sort() -> None:
sort_tester(bubble_sort)
7.2.2. Select sort¶
Implementujte Select sort.
def select_sort(l: List[int]) -> None:
pass
def test_select_sort() -> None:
sort_tester(select_sort)
7.2.3. Insert sort¶
Implementujte Insert sort.
def insert_sort(l: List[int]) -> None:
pass
def test_insert_sort() -> None:
sort_tester(insert_sort)
7.2.4. Analýza rychlosti¶
Proveďte experimentálně analýzu všech naimplementovaných řadících algoritmů.
Buď můžete vaše funkce doplnit o počítání provedených elementárních operací
(porovnávání a přiřazení) nebo můžete měřit čas nutný k seřazení velkých polí
pomocí time.time(). Napište si pomocné funkce pro generování polí zadané
délky (a s různými vlastnostmi: úplně náhodné, téměř seřazené, obrácená
posloupnost) a zkoušejte, u kterých algoritmů se tyto vlastnosti seznamu
projeví. Porovnejte svoje algoritmy i s vestavěnou metodou list.sort().
7.2.5. Quick sort¶
Implementujte Quick sort. Funkce nemusí měnit původní seznam (může vrátit nový, seřazený).
def quick_sort(l: List[int]) -> List[int]:
pass
def test_quick_sort() -> None:
sort_tester(quick_sort)
7.2.6. Merge sort¶
Implementujte Merge sort. Funkce nemusí měnit původní seznam (může vrátit nový, seřazený).
def merge_sort(l: List[int]) -> List[int]:
pass
def test_merge_sort() -> None:
sort_tester(merge_sort)
7.2.7. Counting sort¶
Implementujte Counting sort. Funkce nemusí měnit původní seznam (může vrátit nový, seřazený). Upozornění: algoritmus je vhodný pokud počet možných hodnot prvků je výrazně menší než jejich počet.
def counting_sort(l: List[int], lower: int, upper: int) -> List[int]:
pass
def test_counting_sort() -> None:
lst = [7, 2, 6, 10, 3, -2, -10, 10, 10, 2, 4, 0, -5]
lst = counting_sort(lst, -10, 10)
for i in range(1, len(lst)):
assert lst[i - 1] <= lst[i]
7.2.8. Radix sort¶
Implementujte Radix sort. Funkce nemusí měnit původní seznam (může vrátit nový, seřazený).
def radix_sort(l: List[int]) -> List[int]:
pass
def test_radix_sort() -> None:
sort_tester(radix_sort)
7.3. Neefektivní řadící algoritmy¶
8. Datové struktury¶
Při řešení různorodých problémů se hodí mít možnost uspořádat si data do takového uspořádání (struktury), která nám napomůže ke správnému řešení či zlepší jeho efektivitu, přehlednost atp. Tyto struktury jsou obecně nazývány datovými a informatika jim věnuje nemálo pozornosti.
Datová struktura
Datová struktura je konkrétní způsob uspořádání nějakých dat. Konkrétní datová struktura typicky implementuje nějakou abstraktní datovou strukturu, která popisuje s jakými daty pracujeme a jaké operace s danou strukturou můžeme provádět (e.g. přidání/odebrání prvku atp.)
Pole
Jednou z nejjednodušších struktur, mající fixní počet míst pro data jednoho
datového typu, je vestavěna do jazyků jako C, C++, Java apod. V Pythonu se
místo této struktury používají seznamy, která mají řadu funkcí navíc,
například append, či možnost mít v seznamu libovolně různorodé datové
typy.
Seznam
Jednou z nejjednodušších datových struktur v Pythonu je seznam (anglicky/slangově “list”), probíraný v kapitole Řetězce a seznamy. Pro zopakování, nejdůležitější operace:
V této kapitole se budeme zabývat jen zásobníky, frontami, slovníky a množinami, ale datových struktur existuje velká řada a během dalšího studia se s nimi určitě potkáte, například se stromy:
(zdroj: XKCD)
8.1. Zásobníky¶
Zásobník (anglicky “stack”), slangově s je speciální variantou seznamu,
umožňující prvky vkládat a odebírat pouze z vrcholu zásobníku, tedy podle
principu LIFO: Last In – First Out. Tyto dvě dodatečné operace se nazývají
pop a push. V Pythonu pro ně můžeme použít seznamy, které obě
operace implementují:
8.1.1. Interpretace výrazu v postfixu¶
Při běžném počítání s aritmetickými výrazy 6 + 5 používáme takzvanou
infixovou notaci s operátorem mezi operandy. V tomto příkladě budeme pracovat
s takzvaně reverzní polskou notací, kdy operátor následuje po operandech,
například 6 5 *.
Vyzkoušejte si převést 7 * 8 + 2 * 6 + 5 do postfixu a následně si ho
zkuste spolu s 5 7 * 3 - 4 + vyhodnotit.
Napište funkci, která obdrží řetězec v postfixové notaci a ta výraz za pomocí
zásobníku vyhodnotí. Implementuje operace +, -, / a * v
plovoucí čárce.
Tip: může se vám hodit metoda split, která je použitelná na řetězcích: "a
b c".split().
def evaluate_postfix(expr: str) -> float:
pass
def test_evaluate_postfix() -> None:
assert evaluate_postfix("8 7 * 6 5 + 2 * +")) == 78
assert evaluate_postfix("6 5 -")) == 1
assert evaluate_postfix("15 7 1 1 + - / 3 * 2 1 1 + + -")) == 5
8.1.2. Stejná výška¶
Máte 3 sloupce složené z válců, každý válec má stejný průměr, ale mají různou výšku. Výšku sloupce můžete změnit odebráním válce zvrchu. Válce pouze odebírejte, nepřehazujte je na jiné věže.
Napište funkci equal_height, která vrátí nejvyšší možnou výšku takovou, že všechny sloupce
mají stejnou výšku. Funkce zároveň upraví seznamy sloupců (viz asserty níže).
Bonusový úkol: upravte pro jakýkoliv počet sloupců
(t1: List[int], t2: List[int], t3: List[int] -> ts: List[List[int]]).
def equal_height(t1: List[int], t2: List[int], t3: List[int]) -> int:
pass
def test_equal_height() -> None:
t1 = [1, 1, 1, 2, 3]
t2 = [2, 3, 4]
t3 = [1, 4, 1, 1]
assert equal_height(t1, t2, t3) == 5
assert t1 == [1, 1, 1, 2]
assert t2 == [2, 3]
assert t3 == [1, 4]
8.1.3. Další větší než¶
Napište funkci next_greater, která pro seznam lst vrátí seznam n-tic
(e, ng), kde e je prvek ze seznamu lst a ng je další prvek,
který je větší než e. Když se v seznamu nenachází větší prvek, použijte
None.
Ve výsledném seznamu se musí nacházet všechny prvky z předaného seznamu, na pořadí nezáleží.
def next_greater(lst: List[int]) -> List[Tuple[int, Optional[int]]]:
pass
def test_next_greater() -> None:
assert set(next_greater([4, 5, 2, 25])) == {(4, 5), (5, 25), (2, 25), (25, None)}
assert set(next_greater([13, 7, 6, 12])) == {
(13, None),
(7, 12),
(6, 12),
(12, None),
}
assert set(next_greater([11, 13, 21, 3])) == {
(11, 13),
(13, 21),
(21, None),
(3, None),
}
8.2. Fronty¶
Fronta (anglicky/slangově “queue” či “deque”) je struktura, do které lze
prvky přidávat (push) a odebírat (pop). Pořadí odebírání se ale
děje podle principu FIFO (First In – First Out), tak jako v klasické frontě
v obchodě. Jedná se tedy opět jen o speciální variantu seznamu, umožňující
vkládat prvky na jeden konec a odebírat z druhého konce. Mohli bychom tedy
klidně opět využít seznamy, tento způsob však není moc efektivní (přidávání
nebo odebírání prvků ze začátku seznamu způsobí, že všechny prvky dál se
musí posunout o 1 pozici). Lepší je tedy použít specializovaný typ deque z
knihovny collections.
from collections import deque
queue = deque(["Petr", "Zdenek", "Filip"]) # 3 studenti cekaji ve fronte na obed
queue.append("Kuba") # Kuba prisel na konec fronty
print(queue) # deque(["Petr", "Zdenek", "Filip", "Kuba"])
queue.append("Roman") # Roman prisel na konec fronty
print(queue) # deque(["Petr", "Zdenek", "Filip", "Kuba", "Roman"])
student = queue.popleft() # prvni student ve fronte (Petr) dostal obed
print(queue, student) # deque(["Zdenek", "Filip", "Kuba", "Roman"]), student: "Petr"
student = queue.popleft() # dalsi student ve fronte (Zdenek) dostal obed
print(queue, student) # deque(["Filip", "Kuba", "Roman"]), student: "Zdenek"
8.2.1. Má mě rád, nemá mě rád¶
Nejprve si vygenerujeme kytici lineárně uspořádaných n květin, každou o 1
až 4 okvětních lístcích. Poté vezmeme první květinu a utrhneme z ní právě jeden
lístek a zařadíme ji nakonec. Postup opakujeme dokud nejsou všechny květiny
otrhané. Má vás rád?
from random import randint
def game(n: int) -> None:
pass
print(game(1))
print(game(10))
8.2.2. Horký brambor¶
Horký brambor je jednoduchá dětská hra, kterou hraje n lidí s jedním horkým
bramborem, který si mezi sebou přehazují. Kdo má brambor vyhodnotí jednoduché
kritérium (jako každý sedmý) a pokud toto kritérium splňuje, pak vypadává ze
hry. Vyhrává poslední hráč.
Naprogramujte tuto hru za použití fronty. Přičemž hraje n lidí, jejichž
jména dostane program v seznamu a vypadává každý k-tý hráč. Průběh hry,
vítěze a počet kol průběžně vypisujte.
def hot_potato(namelist: List[str], k: int) -> None:
pass
hot_potato(["Bill","David","Susan","Jane","Kent","Brad","Sam"],7)
# Bill is off!
# Sam is off!
# Kent is off!
# David is off!
# Brad is off!
# Jane is off!
# After 43 rounds Susan is winner!
8.2.3. Fronta v obchodě¶
V obchodě je fronta u samoobslužných pokladen. Vaším úkolem je napsat funkci
queue_time, která vypočítá nejmenší možný celkový čas nutný k vyřízení celé
fronty.
Funkce dostává parametry customers a n. customers je seznam
kladných čísel, každé číslo reprezentuje zákazníka a jeho hodnota udává čas,
který potřebuje k vyřízení nákupu. n je kladné číslo, které reprezentuje
počet pokladen.
from collections import deque
def queue_time(customers: Deque[int], n: int) -> int:
pass
def test_queue_time() -> None:
# they have to wait for each other
assert queue_time(deque([5,3,4]), 1) == 12
# because 1st customer spends 10 "times" and others go to second machine
assert queue_time(deque([10,2,3,3]), 2) == 10
assert queue_time(deque([2,3,10]), 2) == 12
8.3. Slovníky¶
Slovník, někdy též asociativní seznam (slangově též “mapa”) mapuje klíče na hodnoty. Je podobný seznamu, ale jeho prvky nejsou indexovány pomocí posloupnosti celých čísel, ale pomocí klíčů. Klíčem může být například číslo, řetězec nebo jiný neměnitelný objekt, tedy seznam klíčem být nemůže. Pod tímto klíčem můžeme přistupovat k uloženým hodnotám, jsou-li takové ve slovníku přítomny, či nové ukládat.
(demo_dictionary)
8.3.1. Morseova abeceda¶
Napište funkce pro převod řetězce do a z Morseovy abecedy.
MORSE_CODE = {
"A": ".-", "B": "-...", "C": "-.-.", "D": "-..",
"E": ".", "F": "..-.", "G": "--.", "H": "....",
"I": "..", "J": ".---", "K": "-.-", "L": ".-..",
"M": "--", "N": "-.", "O": "---", "P": ".--.",
"Q": "--.-", "R": ".-.", "S": "...", "T": "-",
"U": "..-", "V": "...-", "W": ".--", "X": "-..-",
"Y": "-.--", "Z": "--..", "1": ".----", "2": "..---",
"3": "...--", "4": "....-", "5": ".....", "6": "-....",
"7": "--...", "8": "---..", "9": "----.", "0": "-----",
}
def encode(value: str) -> str:
pass
def decode(value: str) -> str:
pass
def test_encode() -> None:
assert encode('SOS') == "... --- ..."
assert encode('HELLOWORLD') == ".... . .-.. .-.. --- .-- --- .-. .-.. -.."
def test_decode() -> None:
assert decode('.... . .-.. .-.. --- .-- --- .-. .-.. -..') == "HELLOWORLD"
assert decode(encode('IDENTITY')) == "IDENTITY"
zkuste reprezentovat abecedu jinou datovou strukturou; která by byla vhodná?
zkuste implementovat podporu pro mezery ve vstupu a case-insensitive vstup
8.3.2. Frekvenční analýza písmen¶
Napište funkci freq_analysis(text), která spočítá výskyt jednotlivých
písmen (znaků) ve vstupním textu a následně tento seznam vypíše setříděný
sestupně podle počtu výskytů.
dummy = """Monty Python and Monty Python all over here."""
def freq_analysis(text: str) -> None:
pass
freq_analysis(dummy)
8.3.3. Frekvenční analýza slov¶
Napište funkci freq_analysis(text), která spočítá výskyt jednotlivých slov
ve vstupním textu a následně tento seznam vypíše setříděný podle abecedy.
Tip: může se vám hodit metoda split, která je použitelná na řetězcích: "a
b c".split().
dummy = """Monty Python and Monty Python all over here."""
def freq_analysis(text: str) -> None:
pass
freq_analysis(dummy)
8.4. Množiny¶
V množině nemají jednotlivé prvky své indexy, ale můžeme prvky přidávat i odebírat a testovat, zda je nějaký prvek v množině. Množina neobsahuje duplicity (když do ní třikrát přidáme číslo 4, pořád ho bude obsahovat pouze jedenkrát). Přestože nemůžeme přistupovat k jednotlivým prvkům pomocí indexů, můžeme projít celou množinu (a provést nějakou operaci pro každý prvek množiny).
Množinové operace na množinách
8.4.1. Kontrola unikátnosti seznamu¶
Napište funkci, která zkontroluje, zda předaný seznam obsahuje jen unikátní položky.
def unique_check(temp: List[int]) -> bool:
pass
def test_unique_check():
assert unique_check([1, 5, 6, 5, 4, 9]) == False
assert unique_check([1, 5, 6, 3, 9]) == True
8.4.2. Kontrola řádku Sudoku¶
Napište funkci, která zkontroluje, zda předaný seznam reprezentuje správný řádek vyplněného Sudoku, tj. obsahuje pouze čísla 1 až 9 a každé z nich právě jedenkrát.
def sudoku_line_check(line: List[int]) -> bool:
pass
def test_sudoku_line_check() -> None:
assert sudoku_line_check([1, 2, 8, 9, 3, 5, 6, 7, 4]) == True
assert sudoku_line_check([1, 2, 8, 9, 3, 5, 7, 4]) == False
assert sudoku_line_check([1, 1, 2, 8, 9, 3, 5, 7, 4]) == False
assert sudoku_line_check([0, 1, 2, 3, 4, 5, 6, 7, 8]) == False
8.5. Procvičování¶
8.5.1. Vyhodnocení logického výrazu v postfixové notaci¶
Funkce vrátí True, pokud je předaný výrok pravdivý, jinak False. Výraz se skládá z následujících znaků:
‘T’: True
‘F’: False
‘N’: negace
‘K’: konjunkce
‘A’: disjunkce
‘C’: implikace
def evaluate_logic_expression(expr: str) -> bool:
pass
def test_evaluate_logic_expression() -> None:
assert evaluate_logic_expression("TFK") == False
assert evaluate_logic_expression("FNTFCNK") == True
8.5.2. CalcuLoS¶
Následující úloha byla adaptována z šifrovací hry InterLoS 2015.
Napište program, který vezme za vstup řetězec složený pouze z písmen
INTERLOS a transformuje (respektive vyhodnotí) na řetězec složený z písmen
LOS podle níže popsaných pravidel.
Vyhodnocování probíhá zleva, narazí-li se na nějaké z písmen LOS (hodnota)
pokračuje se směrem vpravo. Je-li nalezen nějaký znak z INTER (operátor)
vyhodnotí se za použití argumentů, které ihned následují. Přitom ale může
dojít k situaci, že tyto argumenty nejsou hodnotami, ale operátory, pak se musí
vyhodnotit nejdříve tyto argumenty.
Ukázkové vyhodnocení:
LINLRETOS Nejprve musíme vyhodnotit T na O → O
LINLREOS Pak musíme vyhodnotit E na O a S → SO
LINLRSO Následně musíme vyhodnotit R na S → S S
LINLSSO Poté musíme vyhodnotit N na L a S → S
LISSO A nakonec musíme vyhodnotit I na S a S → O
LOO Výsledek.
Operátor I bere dva argumenty, vrací jednu hodnotu podle následující tabulky:
L |
L |
L |
L |
O |
L |
O |
S |
S |
L |
S |
O |
Operátor N bere dva argumenty, vrací jednu hodnotu podle následující tabulky:
L |
L |
O |
S |
O |
O |
S |
L |
S |
S |
L |
O |
Operátor T bere jeden argument, vrací jednu hodnotu podle následující tabulky:
L |
S |
O |
O |
S |
L |
Operátor E bere dva argumenty, vrací dvě hodnoty: E x y → y x pro všechny x a y z hodnot.
Operátor R bere jeden argument, vrací dvě hodnoty: R x → x x pro všechny x z hodnot.
8.5.3. Kontrola uzávorkování¶
Napište funkci, která pro zadaný řetězec složený pouze ze závorek [](){}
ověří, že jde o korektní uzávorkování.
def parenthesis_check(value: str) -> bool:
pass
def test_parenthesis_check() -> None:
assert parenthesis_check('([]({()}))[]{[()]}') == True
assert parenthesis_check('([)]') == False
8.5.4. Placení v kině¶
Před kinem čekají lidi ve frontě na nový film. Každý má jenom jednu 100, 50 nebo 25dolarovou bankovku. Vstupenka stojí 25 dolarů.
Napište funkci can_sell_tickets, která dostane frontu a vrátí True,
když je možné prodat všem vstupenky, jinak False.
from collections import deque
def can_sell_tickets(people: Deque[int]) -> bool:
pass
def test_can_sell_tickets() -> None:
assert can_sell_tickets(deque([25, 25, 50]))
# not enough to give change for 100
assert not can_sell_tickets(deque([25, 100]))
# can't give back 75 exactly
assert not can_sell_tickets(deque([25, 25, 50, 50, 100]))
9. Objekty¶
Objekty slouží ke spojení souvisejících dat a často i operací na těchto
datech. Třída (class) je předpis (šablona) pro vytváření nových
objektů nějakého typu. Nejjednodušším případem jsou tzv. struktury
(záznamy), sloužící pouze ke spojení souvisejících dat (např. souřadnic
jednoho bodu). Některé programovací jazyky mají speciální typ pro definici
struktury obsahující několik datových položek, v Pythonu se k tomu
využívají jednoduché třídy s metodu __init__, která nastaví
(inicializuje) všechny požadované atributy struktury. Syntaxe pro
vytvoření struktury je následující:
Třída může obsahovat i další metody (funkce pracující na datech objektu).
Objekt pak má nějaký stav (data, atributy) a navíc i chování (metody).
Prvním parametrem metody je vždy objekt, na kterém došlo k volání této metody,
silnou konvencí je nazývat tento parametr self.
S objekty jsme pracovali již mnohokrát. Například seznamy jsou objekty s
metodami jako append, sort, atd. A třeba knihovna turtle obsahuje
třídu Turtle pro reprezentaci kreslící želvy. Nový objekt želvy se
vytvoří voláním turtle1 = Turtle().
Další konvencí Pythonu je pojmenovávat atributy, ke kterým by nemělo být
přistupováno z vnějšku přímo, ale pouze pomocí metod (tzv. soukromé atributy),
s podtržítkem na začátku (např. _name).
9.1. Struktury¶
9.1.1. Barevné kruhy¶
Vytvořte třídu pro reprezentaci barevného kruhu na daných souřadnicích.
class Circle:
def __init__(self, x: float, y: float, radius: float, color: str) -> None:
pass
def test_circle() -> None:
circle = Circle(4, 5, 10, 'red')
assert circle.y == 5
assert circle.color == 'red'
9.1.2. Obdélník¶
Napište třídu Rectangle pro reprezentaci obdélníku o dané šířce a výšce a funkci pro výpočet obsahu předaného obdélníku.
class Rectangle:
pass
def area(rectangle: Rectangle) -> float:
pass
def test_rectangle() -> None:
rectangle = Rectangle(4, 3)
assert rectangle.width == 4
assert rectangle.height == 3
assert area(rectangle) == 12
9.1.3. Bod¶
Napište třídu pro reprezentaci bodu v rovině (parametry x a y). Potom implementujte funkci, která vypočítá vzdálenost dvou bodů.
9.1.4. Kniha¶
Napište třídu pro reprezentaci knihy (s atributy název, autor, ISBN a cena).
Dále napište funkce print_info pro výpis informací o knize
a draw_cover pro vykreslení obálky knihy.
Výstup může vypadat třeba nějak takto (nemusíte si ale hrát se zarovnáním do středu):
name: Cooking for Geeks
author: Jeff Potter
isbn: 0596805888
price: $22
+-------------------------+
| |
| |
| |
| Cooking for Geeks |
| |
| |
| |
| Jeff Potter |
| |
| |
| |
| |
+-------------------------+
9.2. Objekty s metodami¶
9.2.1. Kruh¶
Napište třídu pro reprezentaci kruhu s daným středem a poloměrem.
Implementujte metody pro výpočet obvodu, obsahu a vrácení informačního řetězce (__str__).
class Circle:
def __init__(self, center: float, radius: float) -> None:
pass
def get_perimeter(self) -> float:
pass
def get_area(self) -> float:
pass
def __str__(self) -> str:
pass
def test_circle() -> None:
circle = Circle((-130, -130), 100)
assert str(circle) == "Circle at (-130, -130) with radius 100"
assert circle.get_area() == 31415.926535897932
9.2.2. Želvy¶
Prozkoumejte následující třídu pro reprezentaci kreslící želvy a vyzkoušejte si její použití.
class Turtle:
def __init__(self) -> None:
self.x = 0
self.y = 0
self.direction = 0
self.lines = []
def left(self, angle: float) -> None:
self.direction -= angle
def right(self, angle: float) -> None:
self.direction += angle
def forward(self, distance: float) -> None:
nx = self.x + distance * math.cos(self.direction * math.pi / 180)
ny = self.y + distance * math.sin(self.direction * math.pi / 180)
self.lines.append((self.x, self.y, nx, ny))
self.x, self.y = nx, ny
def get_lines_svg(self) -> str:
svg = ""
for x1, y1, x2, y2 in self.lines:
svg += """\t<line x1='{}' y1='{}' x2='{}' y2='{}'
style='stroke: red; stroke-width:2' />\n""".format(x1, y1, x2, y2)
return svg
def save(self, filename: str) -> None:
with open(filename, "w") as f:
f.write('<svg width="100%" height="100%" xmlns="http://www.w3.org/2000/svg" xmlns:xlink= "http://www.w3.org/1999/xlink">\n')
f.write(self.get_lines_svg())
f.write("\n</svg>")
Přidejte želvě metodu pro vykreslení mnohoúhelníka.
Upravte želvu tak, aby začínala na náhodné pozici (třeba v intervalu 0-500).
Upravte želvu tak, aby uměla kreslit i jinou barvou než černou (např. můžete přidat metodu
set_color(self, color: str) -> None).Přidejte želvě metodu, která ji posune o danou vzdálenost náhodným směrem (
random_step(self, distance: float) -> None).Napište funkci
chase(steps: int = 10) -> None. Funkce vytvoří 2 želvy, jedna bude honit druhou. První (černá) bude daný počet kroků náhodně chodit (třeba o 100), druhá (červená) bude vždy chodit směrem k první (taky třeba o 100). Nakonec funkce uloží obě želvy do jednoho svg (pozn.: není možné přímo použít metodusave()), můžete využít metodu:def turn_towards(self, other_turtle: 'Turtle') -> None: self.direction = math.atan2(other_turtle.y - self.y, other_turtle.x - self.x) / math.pi * 180
Napište funkci
multichase(steps: int = 10, turtles: int = 10) -> None, která vytvoří požadovaný počet želv a uloží je do seznamu; v každém kroku každá ze želv udělá krok (třeba 10) k nejbližší želvě (může se hodit metoda typufind_nearest(self, turtles: List['Turtle']) -> 'Turtle', která vrátí nejbližší želvu z daného seznamu).Zkuste změnit želvy na tanky, které po sobě budou střílet.
9.2.3. Příšera¶
Doplňte následující kostru třídy a vyzkoušejte její funkčnost. Poté přidejte
příšeře další metody, např. is_defeated, která vrací True, pokud už příšera
nemá žádné životy.
9.2.4. Zásobník¶
Vytvořte třídu pro reprezentaci zásobníku podporující operace přidání prvku, odebrání prvku a test na prázdnost.
class Stack:
pass
def test_stack() -> None:
stack = Stack()
stack.push(5)
stack.push(10)
assert stack.pop() == 10
assert not stack.is_empty()
assert stack.pop() == 5
assert stack.is_empty()
9.2.5. Fronta¶
Vytvořte třídu pro reprezentaci fronty podporující operace přidání prvku, odebrání prvku, test na prázdnost, seřazení prvků ve frontě a konverzi fronty na zásobník.
class Queue:
pass
def test_queue() -> None:
queue = Queue()
queue.enqueue(42)
queue.enqueue(10)
queue.enqueue(5)
assert not queue.is_empty()
assert queue.dequeue() == 42
queue.sort()
stack = queue.to_stack()
assert stack.pop() == 10
assert queue.dequeue() == 5
9.2.6. Knihovna¶
Vytvořte třídu Library pro reprezentaci kolekce knih s metodami pro přidání
knihy, odebrání knihy, nalezení knihy podle názvu nebo ISBN, nalezení všech
knih daného autora, nalezení všech knih s cenu pod zadanou mez. Pro
reprezentaci knih využijte třídu Book ze cvičení Kniha.
9.2.7. Geometrické tvary¶
Napište třídy pro několik jednoduchých geometrických útvarů (čtverec, kruh,
rovnostranný trojúhelník). Každá třída bude mít metody pro výpočet obvodu,
výpočet obsahu a vrácení informačního řetězce (__str__). V následující
ukázce si všimněte dynamické (pozdní) vazby jmen metod (např. get_perimeter
na řádku 10) na jejich definice (tj. skutečně volaná metoda se různí podle
toho, na jaký objekt zrovna ukazuje proměnná shape).
9.2.8. Vektory¶
Python umožňuje přetížit mnoho operátorů (např. +, * atp.) skrze tzv.
magické funkce (např. __add__ pro přetížení operátoru +). S využitím
následující kostry implementujte třídu reprezentující vektor
class Vector:
def __init__(self, x: float, y: float) -> None:
self.x = x
self.y = y
def __str__(self) -> str:
return "(" + str(self.x) + ", " + str(self.y) + ")"
def __add__(self, vector: 'Vector') -> 'Vector':
"""Return vector 'self'+'vector'."""
pass # TODO
def __rmul__(self, c: float) -> 'Vector':
"""Return vector 'self'*c."""
pass # TODO
def test_vector() -> None:
u = Vector(1, 3)
v = Vector(2, 7)
w = u + v
assert w.x == 3
assert w.y == 10
w = 3 * u
assert w.x == 3
assert w.y == 9
9.2.9. Piškvorky¶
Vytvořte třídu Grid pro reprezentaci čtverečkovaného pole s rozehranou
partií piškvorek. Využijte pak tuto třídu pro hru piškvorek mezi 2 hráči
(střídají se 2 hráči (symboly ‘X’ a ‘O’), tah (poloha symbolu) se načítá jako
vstup od uživatele, vyhrává hráč, který má 5 svých znaků v řadě.
class Grid:
def __init__(self, size: int) -> None:
pass
def in_grid(self, coords: Tuple[int, int]) -> bool:
"""Return true iff corrds=(x,y) is in the grid."""
pass
def add_symbol(self, symbol: str, coords: Tuple[int, int]) -> bool:
"""
Add symbol 'symbols' to grid at position 'coords' (if the coordine
is valid).
Returns True if successful, False otherwise.
"""
pass
def __str__(self) -> str:
pass
def check_five(self) -> bool:
"""Return true iff there are 5 same symbols in a row in a grid
(vertically or horizonally or diagonally).
"""
pass
def generate_move(self, symbol: str = 'X') -> Optional[Tuple[int, int]]:
"""
Generates random move so the move does not help an enemy to win
and self player wins, if currennly possible.
"""
pass
def is_full(self) -> bool:
"""Return true iff the contains no empty fields."""
pass
9.3. Doplňující zdroje¶
(Námět: napište funkci, která dostane seznam (barevných kruhů) a nějakým způsobem je vykresli – např. pomocí želví grafiky, knihovny Image, nebo uložením vektorového obrázku ve formátu SVG.)
10. Rekurze¶
Syn: Kolik otoček potřebuji na zašroubování žárovky?
Otec: Pokud už je zašroubovaná, tak 0.
Jinak ji zatoč jednou, zeptej se mě znova a k mé odpovědi přičti 1.
Rekurze je využití sebe sama. Typickými příkladem je rekurzivní definice, tedy použití X v definici X. Můžeme třeba definovat funkci faktoriál pomocí funkce faktoriál:
0! = 1
n! = n * (n - 1)! pro n > 0
Totéž ve slovech:
Syn: Kolik je faktoriál čísla n?
Otec: Pokud je n rovno 0, pak 1.
Jinak se mě zeptej na faktoriál čísla (n - 1) a moji odpověď vynásob číslem n.
Při programování se pak rekurze objeví jako funkce, která pro výpočet
využívá sebe sama. Téměř jedna ku jedné můžeme k definici matematické
funkce faktoriál napsat definici výpočetní funkce faktorial v Pythonu:
(faktorial_demo)
Nejedná se o definici v kruhu, protože v každém kroku dochází ke zjednodušování (faktoriál n je definován pomocí faktoriálu n - 1) a je definován i bázový případ (n = 0) bez rekurze, ke kterému vše směřuje. Jde tedy spíše o definici ve spirále.
Jak postupovat při návrhu rekurzivních algoritmů? Nejprve určete
podproblémy, které potřebujete k vyřešení vašeho problému (například pro
výpočet n! potřebuji určit jediný podproblém (n - 1)!) Tyto
podproblémy vyřešte rekurzivně a z jejich výsledků poskládejte výsledné
řešení. Dále je nutné určit bázový případ (případně více bázových případů)
a jejich řešení (například faktoriál 0 je 1). Bázový případ musí být
takový, aby se k němu všechny větve výpočtu časem dostaly, jinak by výpočet
nikdy neskončil.
Další ukázkou rekurzivního algoritmu je výpočet největšího společného dělitele, zde už však není 1 ku 1 korespondence s obvyklou definicí největšího společného dělitele. Korektnost funkce tady vyplývá z korektnosti zjednodušovacího rekurzivního kroku (\(nsd(a, b) = nsd(a \mod b, b)\) pro b > 0) a bázového případu (\(nsd(a, 0) = a\)), ke kterému výpočet nevyhnutelně směřuje (a v konečném počtu kroků se k němu dostane).
(nsd_demo)
10.1. Zmenši a panuj¶
Mnoho problémů lze řešit tak, že nejprve vyřešíme zjednodušenou verzi problému a řešení zjednodušeného problému rozšíříme na řešení původního problému. Nejčastější variantou je redukce na problém s o 1 menším vstupem (viz faktoriál výše), někdy je však možné zmenšit velikost vstupu na polovinu a zmenšování může být dokonce i nepravidelné (jako v případě Euklidova algoritmu pro NSD výše). Této technice se říká zmenši a panuj, anglicky decrease-and-conquer. Může být implementována buď iterativně (pomocí cyklu) nebo rekurzivně (funkce s jediným rekurzivním voláním).
10.1.1. Součet čísel¶
Napište rekurzivní funkci, která zjistí součet přirozených čísel od 1 do
n. Při vymýšlení funkce series_sum(n) si představte, že máte k
dispozici funkci series_sum(k) pro libovolné k < n. Nezapomeňte na bázový
případ.
def series_sum(n: int) -> int:
pass
def test_series_sum() -> None:
assert series_sum(1) == 1
assert series_sum(5) == 15
assert series_sum(10) == 55
assert series_sum(100) == 5050
10.1.2. Prvek posloupnosti¶
Napište rekurzivní funkci, která počítá n-tý prvek posloupnosti definované následujícím induktivním způsobem:
\(a_0 = 5\)
\(a_n = 2 \cdot a_{n - 1} - 1\)
def sequence(n: int) -> int:
pass
assert sequence(0) == 5
assert sequence(1) == 9
assert sequence(2) == 17
assert sequence(3) == 33
10.1.3. Zašroubování žárovky¶
Napište rekurzivní funkci, která n-krát vypíše „twist“.
def screwing(n: int) -> None:
pass
screwing(3)
# Ocekavany vystup:
# twist
# twist
# twist
10.1.4. Součet seznamu čísel¶
Napište rekurzivní funkci pro součet seznamu čísel.
def list_sum(numbers: List[int]) -> int:
pass
def test_list_sum() -> None:
assert list_sum([1, 8, 2, 0, 4, 2]) == 17
10.1.5. Binární vyhledávání¶
Napište funkci binary_search(value, numbers), která zjistí, zda se hodnota
value nachází ve vzestupně uspořádaném seznamu numbers. Funkce musí
mít logaritmickou časovou složitost. Pozor na to, že kopírování seznamu má
lineární časovou složitost vzhledem k počtu prvků. Je tedy vhodné napsat si
pomocnou funkci, která bude hledat zadané číslo v části seznamu ohraničeném 2
parametry (např. left a right pro levou a pravou mez intervalu, ve
kterém hledáme).
def binary_search(value: int, numbers: List[int]) -> bool:
pass
def test_binary_search() -> None:
assert binary_search(5, [1, 2, 5, 8]) == True
assert binary_search(4, [1, 2, 5, 8]) == False
10.2. Rozděl a panuj¶
Někdy je potřeba k vyřešení problému nejprve vyřešit hned několik podproblémů a potom zkombinovat řešení podproblému do výsledného řešení. Této technice návrhu algoritmů se říká rozděl a panuj, anglicky divide-and-conquer. Zatímco v předchozí sekci byla složitost napsání iterativní a rekurzivní implementace téměř stejná, u algoritmů navržených touto technikou bývá rekurzivní implementace výrazně jednodušší a elegantnější. (Odstranit rekurzi je ale vždy možné pomocí zásobníku.)
10.2.1. Hanojské věže¶
Máme 3 věže, na jedné z nich (budeme jí říkat zdrojová), je nasunuto n kotoučů různé velikosti od největšího po nejmenší. Úkolem je přesunout všechny kotouče ze zdrojové na cílovou věž, přičemž vždy můžeme přesouvat pouze jeden kotouč a nikdy nesmíme dát větší kotouč na menší. Pokud jste se s hrou ještě nesetkali, vyzkoušejte si ji. Naším úkolem teď bude vymyslet rekurzivní algoritmus, který přesune n kotoučů ze zdrojové na cílovou věž, resp. vypíše kroky, které je potřeba k přesunu udělat. Řešení pro 3 kotouče, a věže pojmenované ‘A’ (zdrojová věž), ‘C’ (cílová věž) a ‘B’ (pomocná věž):
>>> hanoi(3, 'A', 'C', 'B')
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
# Vypise premistovani kotoucu pri reseni Hanojskych vezi.
# - n: pocet kotoucu
# - source: tyc, na ktere jsou kotouce na zacatku
# - target: tyc, na kterou chceme kotouce premistit
# - auxiliary: pomocna tyc, kterou lze vyuzit v prubehu premistovani
def hanoi(n: int, source: str, target: str, auxiliary: str) -> None:
pass
hanoi(3, 'A', 'C', 'B')
10.2.2. Hanojské věže graficky¶
Rozšiřte předchozí úlohu o vykreslování mezistavů po každém přesunu pomocí ascii grafiky.
>>> hanoi(3, 'A', 'C', 'B')
# | |
### | |
##### | |
----- ----- -----
A B C
| | |
### | |
##### | #
----- ----- -----
A B C
...
10.2.3. Maximum a minimum¶
S využitím techniky rozděl a panuj napište funkci pro zjištění minima a maxima ze seznamu čísel. Vaše funkce by měla obsahovat 2 rekurzivní volání. Zkuste se vyhnout kopírování části seznamu (podobně jako v úloze Binární vyhledávání).
def min_max(numbers: List[int]) -> Tuple[int, int]:
pass
def test_min_max() -> None:
assert min_max([8, 4, 3, 5, 9, 2, 1, 7, 6]) == (1, 9)
10.2.4. Rychlé řazení¶
Metodu rozděl a panuj lze využít k efektivním algoritmům pro řazení. Jeden z možných přístupů je vybrat libovolný prvek (tzv. pivot), a všechna ostatní čísla rozdělit na 2 části – menší než pivot a větší než pivot. Tyto dvě části seřadíme rekurzivně a spojíme do výsledného pole. Rozdělení čísel na prvky menší a větší než pivot je jednoduché, pokud povolíme vytvářet nové seznamy (tím se mírně zhoršuje paměťová složitost). Implementujte tento rekurzivní algoritmus, nezapomeňte na bázový případ. Můžete si přečíst podrobnosti o QuickSortu na Khan Academy a pokusit se implementovat rozdělování prvků na místě (bez potřeby vytváření nových seznamů).
# vraci serazene pole 'array' (samotne pole 'array' nemeni)
def quick_sort(array: List[int]) -> List[int]:
pass
def test_quick_sort() -> None:
assert quick_sort([2, 7, 8, 1, 4, 5, 9, 3, 6]) == list(range(1, 10))
10.3. Fraktály¶
Rekurze je příkladem obecnějšího jevu odkazování na sebe sama, tzv. sebe-reference. Sebe-reference se vyskytuje v jazyce (Třeba tato věta mluví sama o sobě.), v knihách, v divadle, ve filmu, ale dokonce i v matematice. Sebe-reference je dokonce hlavní ingrediencí nejslavnějších důkazů matematiky (Gödelovy věty o neúplnosti) a také informatiky (existence problémů, pro které neexistuje algoritmus, který by je řešil – např. problém zastavení).
Vedle rekurze jsou nejtypičtějším zástupcem sebe-reference fraktály, obrázky, které jsou soběpodobné, tedy jejich části připomínají obrázek jako celek. Fraktály můžete objevit všude možně v přírodě (např. větve stromů, kapradina). Fraktály a rekurze nejsou dva nezávislí reprezentanti sebe-reference, i mezi nimi je silná souvislost. Rekurze je totiž velmi elegantní způsob, jak jednotlivé fraktály definovat. Díky tomu často můžeme složité fraktály vykreslit pomocí jednoduchých rekurzivních funkcí.
Technická poznámka:
Ke kreslení fraktálů využijeme knihovnu turtle, se kterou jsme
pracovali v první kapitole. Nezapomeňte po dokončení kreslení zavolat
funkci done z této knihovny (měl by to být poslední řádek vašeho
programu, rozhodně ji nevkládejte do rekurzivní funkce, jinak bude kreslení
ukončeno předčasně).
10.3.1. Vnořené čtverce¶
Úkolem je napsat rekurzivní funkci, která vykreslí vnořené čtverce. Parametr funkce bude udávat, kolik čtverců má být vykresleno. Při vymýšlení rekurzivní funkce si nejprve ujasněte (můžete zapsat do komentáře), co funkce dělá – není důležité jen to, co želva vykreslí, ale také to, kde skončí a jakým směrem bude natočená. Dále si představte, že již máte k dispozici funkci, která umí kreslit menší počty čtverců a využijte ji k napsání těla funkce. Nezapomeňte na bázový případ. Funkce bude obsahovat jediné rekurzivní volání, takže by bylo jednoduché ji přepsat pomocí cyklu bez rekurze (můžete si vyzkoušet).
from turtle import Turtle
julie = Turtle()
julie.speed(10)
# depth: kolik ctvercu vykreslit
# length: delka strany nejvetsiho ctverce
def nested_squares(depth: int, length: float = 180.0) -> None:
pass
nested_squares(8)
10.3.2. Strom¶
S využitím techniky rozděl a panuj napište rekurzivní funkci pro vykreslení stromku, jako vidíte na obrázku. Po vykreslení základního stromku můžete vyzkoušet různé variace, např. změnit stupeň větvení, délku větví, naklonění větví atd.
from turtle import Turtle
julie = Turtle()
julie.speed(10)
julie.left(90)
# length: delka kmenove cary
def tree(length: float) -> None:
pass
tree(90)
10.3.3. Kochova vločka¶
Napište rekurzivní funkci pro vykreslení Kochovy křivky. Vhodným složením tří Kochových křivek (jakoby do trojúhelníka) získáte Kochovu vločku.
from turtle import Turtle
julie = Turtle()
julie.speed(10)
julie.setposition(-190, 0)
# depth: pocet rekurzivnich zanoreni
# size: sirka krivky
def koch(depth: int = 5, size: float = 380.0) -> None:
pass
koch(5)
10.3.4. Sierpinského trojúhelník¶
Napište rekurzivní funkci pro vykreslení Sierpinského trojúhelníka (není nutné „nezpracované“ trojúhelníky vyplňovat černou barvou).
from turtle import Turtle
julie = Turtle()
julie.speed(10)
# depth: pozadovana hloubka rekurzivniho zanoreni
# length: delka strany trojuhelnika
def sierpinski_triangle(depth: int, length: float = 180.0) -> None:
pass
sierpinski_triangle(5)
10.3.5. Fraktálové sušenky¶
Fraktály mají své místo i v kuchyni. Příkladem mohou být fraktálové sušenky, připomínající Sierpinského koberec. I tento fraktál lze poměrně snadno vykreslit pomocí želví grafiky. Pro vyplňování čtverců barvou můžete použít funkci fill z knihovny turtle.
Pokud byste si chtěli fraktálové sušenky upéct, přikládáme mnoholetou praxí ověřený recept (nezapomeňte donést ochutnávku na cvičení). Stejně jako kreslení fraktálů, i jejich pečení je výhodné provádět rekurzivně, není tedy překvapením, že zmíněný recept je rekurzivní. Můžete také vymyslet jiné sebe-referenční pochoutky.
from turtle import Turtle
julie = Turtle()
julie.speed(10)
julie.setposition(-180, -180)
# vykresli ctverec bez vyplne
def empty_square(length: float) -> None:
for i in range(4):
julie.forward(length)
julie.left(90)
# vykresli vyplneny ctverec
def filled_square(length: float) -> None:
julie.pendown()
julie.begin_fill()
for i in range(4):
julie.forward(length)
julie.left(90)
julie.end_fill()
# funkce pro vykresleni Sierpisnkeho koebrce
# depth: pozadovane rekurzivni zanoreni
# length: delka strany
def sierpinski_carpet(depth: int, length: float = 360.0) -> None:
# nechceme, aby pri presunech zelva kreslila
julie.penup()
# ---------------------------------------
# TODO: dopiste tuto rekurzivni funkci
# ---------------------------------------
# vykresli fraktalovou susenku
def fractal_cookie(depth: int, length: float = 360.0) -> None:
# okraj
empty_square(length)
# vnitrek
sierpinski_carpet(depth, length)
fractal_cookie(3)
10.3.6. Hilbertova křivka¶
Napište funkci pro vykreslení Hilberotvy křivky.
from turtle import Turtle
julie = Turtle()
julie.speed(10)
def hilbert(depth: int = 4, right: bool = True, length: int = 10) -> None:
pass
hilbert()
10.4. Akumulátor¶
Při psaný funkcí s více rekurzivními voláními je potřeba dávat pozor na to, jestli se výpočty jednotlivých volání nepřekrývají. Klasickým odstrašujícím příkladem je výpočet n-tého Fibonacciho čísla. Následující naivní rekurzivní algoritmus vede k exponenciální časové složitosti.
def fibonacci_disaster(n: int) -> None:
if n < 2:
# bazove pripady
return n
else:
# rekurzivni volani
return fibonacci_disaster(n - 1) + fibonacci_disaster(n - 2)
print(fibonacci_disaster(30))
To však neznamená, že nelze Fibonacci čísla počítat pomocí rekurze
efektivně, je však potřeba zvolit jiný přístup. Lze použít techniku
akumulátoru, díky níž nám postačí jediné rekurzivní volání na konci funkce
(tzv. koncová rekurze, anglicky tail recursion). Myšlenka je stejná jako
u iterativního výpočtu Fibonacciho čísel cyklem – udržujeme si poslední 2
vypočítaná Fibonacciho čísla a kolik čísel nám ještě zbývá napočítat, než
se dostaneme k požadovaném Fibonaccimu číslu. Časová složitost je pak
lineární vzhledem k n.
(fibonacci_acc_demo)
10.4.1. Tetranacciho posloupnost¶
Napište efektivní rekurzivní funkci pro výpočet n-tého čísla Tetranacciho posloupnosti, která je definovaná následujícím induktivním způsobem:
\(a_0 = 0\), \(a_1 = 1\), \(a_2 = 1\), \(a_3 = 2\),
\(a_n = a_{n - 1} + a_{n - 2} + a_{n - 3} + a_{n - 4}\)
10.5. Doplňující zdroje¶
Robotanik (umimeprogramovat.cz) (Skvělé na procvičení rekurzivního uvažování.)
11. Práce s textem¶
11.1. Práce s textem¶
Pokročilá práce s řetězci
Čtení a zápis do souborů
input_file = open("input.txt", "r") # otevreni souboru pro cteni
content = input_file.read() # nacteni celeho obsahu souboru do retezce
lines = input_file.readlines() # nacteni souboru souboru jako seznam radku
output_file = open("output.txt", "w") # otevreni souboru pro zapis
output_file.write("Some sentence.") # zapis retezce do souboru
some_file.close() # uzavreni souboru
# doporucovana konstrukce with, ktera zajisti automaticke uzavreni souboru:
with open("input.txt", "r") as input_file:
pass
11.1.1. “head” / “tail”¶
Načtěte soubor alice-in-wonderland.txt a
naprogramujte funkce:
head, která vypište prvníchnřádků obsahu souboru,tail, která vypište posledníchnřádků obsahu souboru.
def head(filename: str, n: int) -> None:
pass
head("alice-in-wonderland.txt", 3)
#
# ALICE’S ADVENTURES IN WONDERLAND
#
def tail(filename: str, n: int) -> None:
pass
tail("alice-in-wonderland.txt", 3)
# all their simple sorrows, and find a pleasure in all their simple joys,
# remembering her own child-life, and the happy summer days.
#
11.1.2. Každé druhé slovo¶
Načtěte soubor lorem-ipsum.txt a
vypište každé druhé slovo, které se v něm nachází.
def every_second(filename: str) -> None:
pass
every_second("lorem-ipsum.txt")
# ipsum sit consectetur elit, do tempor ut et magna Rhoncus purus
# enim Risus tristique aliquet. in quam orci eu Scelerisque imperdiet
# fermentum vel porta
11.1.3. Nejčastější slova¶
Načtěte soubor sherlock-holmes.txt a
vypište 10 nejčastěji se vyskytujících slov v textu. Pro zajímavost se omezte
pouze na slova délky 3 a více.
def most_freq_words(filename: str) -> None:
pass
most_freq_words('sherlock-holmes.txt')
11.1.4. Průměrný počet slov ve větě¶
Analyzujte text v souboru
alice-in-wonderland.txt a vraťte
průměrný počet slov ve větě.
def average_sentence_len(filename: str) -> float:
pass
print(average_sentence_len('alice-in-wonderland.txt'))
11.1.5. Frekvence písmen¶
Proveďte frekvenční analýzu některého z výše uvedených souborů. Vypište, kolikrát se v textu vyskytují jednotlivá písmena.
Tip: pro ověření, že je daný znak písmeno, můžete použít funkci isalpha.
def freq_analysis(filename: str) -> None:
pass
freq_analysis('my_file.txt')
11.1.6. Podmíněná frekvenční analýza¶
Pro každé písmeno v textu vypište 5 písmen, které za ním následují nejčastěji.
Můžete využít například soubor
devatero_pohadek.txt.
def cond_freq_analysis(filename: str) -> None:
pass
cond_freq_analysis('devatero_pohadek.txt')
11.1.7. Imitace textu¶
Napište funkci text_imitation(filename, length), která analyzuje text
v souboru filename. Funkce pak vygeneruje pseudo-náhodný text o length
slovech. Text se generuje po slovech. Další generované slovo se náhodně vybírá
z těch, které v původním textu po naposledy vygenerovaném slově následovaly.
def text_imitation(filename: str, length: int) -> None:
pass
text_imitation('devatero_pohadek.txt', 10)
11.1.8. Imitace textu po písmenech¶
Upravte vaše předchozí řešení tak, aby vytvářelo slova a to po jednotlivých písmenech.
11.1.9. Analýza jmen¶
Načtěte soubor jmena.csv. Implementujte funkci
most_common_names(filename), která ze souboru vypíše count nejčastěji
užívaných jmen (globálně).
def most_common_names(filename: str, count: int) -> None:
pass
most_common_names('jmena.csv', 10)
11.1.10. Analýza jmen II¶
Upravte předchozí funkci tak, aby jako parametr brala ještě seznam roků. Funkce
vypíše count nejčastějších jmen v letech, které dostane v seznamu.
def most_common_names_years(filename: str, count: int, years: List[int]) -> None:
pass
most_common_names_years('jmena.csv', 10, [2005, 1996, 2003])
11.1.11. Zpracování jmen¶
Napište funkce, která přečte všechny jména v souboru
NAMES.txt, zpracuje je tak, aby měla velké pouze
první počáteční písmeno (JOHN -> John) a seřadí je v abecedě. Po té je uloží
do jiného souboru.
def process_names(input_filename: str, output_filename: str) -> None:
pass
process_names('NAMES.txt', 'names.txt')
11.2. Regulární výrazy¶
Regulární výraz (regular expression), označovaný též zkráceně jako regexp či regex je speciální řetězec znaků, který představuje určitý vzor pro textové řetězce. Regulární výraz je tedy nějaký obecný popis, který vždy odpovídá určité skupině řetězců (např.: email, html tag, datum…). Můžeme je využít ke kontrole vstupu, hledání a nahrazování v textu, parsování html a mnoha dalším úkolům.
O regulárních výrazech bylo mnoho napsánu a existuje mnoho návodů a taháků: regularnivyrazy.info, python.org, Wikipedia, Cheat Sheet, OverAPI a další. Existují i weby, kde si lze práci s regulárními výrazy snadno vyzkoušet online (např.: pythex.org). Můžete je také procvičit na Tutorovi.
Pro práci s regulárními výrazy v Pythonu lze využít knihovnu re
Raw string
Protože zpětná lomítka mají speciální význam také v regulárních výrazech (a tedy jich obvykle obsahují hodně), vyhovovalo by nám více takové chování, kdy by se zpětná lomítka v řetězci nijak neinterpretovala. Toho lze dosáhnout přidáním znaku r těsně před samotný řetězec, např. r’raw string with ‘.
11.2.1. Celá čísla¶
Napište funkci is_integer(string), která vrátí True pokud zadaný
string je celé číslo.
import re
def is_integer(string: str) -> bool:
pass
def test_is_integer() -> None:
assert is_integer("42") == True
assert is_integer("-42") == True
assert is_integer("4a2") == False
11.2.2. Čísla¶
Napište funkci is_number(string), která vrátí True pokud zadaný
string je číslo.
import re
def is_number(string: str) -> bool:
pass
def test_is_number() -> None:
assert is_number("42.01") == True
assert is_number("-42") == True
assert is_number("4.b") == False
assert is_number("42.") == False
11.2.3. Jména¶
Využijte soubor jmen, které jste vytvořili ve cvičení Zpracování jmen. Funkce search_in_file(pattern, filename) vypíše z daného souboru všechny řádky, které odpovídají vzoru. Pomocí této funkce vypište všechny jména která
obsahují
ooobsahují alespoň 3 znaky
o(ne nutně po hned sobě)obsahují pouze samohlásky
obsahují pouze souhlásky [stačí přidat jediný znak do předchozího vzoru]
začínají na
BneboDa končí na w nebo zobsahují buď
infneboreckromě prvního a posledního písmene obsahují pouze samohlásky a mají přesně 5 písmen
začínají a končí na
Aa mají nejvýše 4 písmenazačínají na
NneboMa obsahují alespoň 5 samohlásekkromě
amůžou obsahovat nejvýše 2 jiná písmena, což ale můžou být jediněl,mnebon
# vypise radky, ktere splnuji zadany vzor
def search_in_file(pattern: str, file_name: str) -> None:
with open(file_name) as f:
lines = f.read().split('\n') # nacteme vsechny radky do seznamu
for line in lines: # prochazime radky a hledame shodu
if re.search(pattern, line):
print(line)
search_in_file(r'.*', 'names.txt')
11.2.4. Zpracování CSV¶
Ze souboru students.csv vypište následující
statistiky:
seznam všech křestních jmen
seznam všech použitých křestních jmen (bez opakování) s počtem jejich výskytů
seznam všech použitých křestních jmen s počtem jejich výskytů začínající daným písmenem
řaďte jména podle abecedy
pro každého člověka informaci o studovaném semestru v následujícím formátu:
50668: 1. semestr 1. rocniku,43583 : 5. semestr 1 cykludalší informace (třeba rozložení mezi fakultami)
names("students.csv", "s")
# Samuel 3
# Sandra 1
# Sebastian 1
semesters("students.csv")
# 50668 : 1. semestr 1 rocniku
# 421714: 2. semestr 1 rocniku
# 564138: 1. semestr 1 rocniku
# 43583 : 5. semestr 1 cyklu
# 81908 : 5. semestr 1 cyklu
# 844632: 1. semestr 1 rocniku
# 798639: 1. semestr 1 rocniku
# ....
12. Bitmapová grafika¶
Uspořádané k-tice
Jednou z nejjednodušších struktur, se kterou jsme se už setkali v případě, kdy jsme chtěli prohodit obsah dvou proměnných, jsou uspořádané k-tice (anglicky „tuple“). Podobně jako v matematice se jedná o uspořádaný soubor prvků dané velikosti. Svým způsobem jsou podobné seznamům, avšak na rozdíl od nich vytvořené k-tice už nemůžeme nikterak měnit. Pro vytvoření uspořádané k-tice používáme čárku. Při práci s uspořádanými k-ticemi můžeme použít tzv. pattern matching, kde jednotlivé prvky k-tice můžeme jednoduše přiřadit do zvláštních proměnných.
Základní vytvoření obrázku
Obrázek si v dnešním cvičení můžeme představit jako mřížku pixelů, kde každému pixelu přísluší nějaká barva. Pixel, jehož souřadnice jsou (0, 0) se nachází v levém horním rohu. Pro zápis barvy typicky používáme RGB model.
Barvu v RGB modelu měníme nastavením různé intenzity červeného (R), zeleného (G) a modrého (kanálu). Každý kanál může nabývat hodnot od 0 do 255.¶
from PIL import Image
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
# Zjisti, zda je zadany bod uvnitr kruhu o danem polomeru, jehoz stred
# je uprostred ctvercoveho obrazku.
def in_circle(size: float, radius: float, x: float, y: float) -> bool:
return (x - size / 2) ** 2 + (y - size / 2) ** 2 < radius ** 2
def circle(size: int = 150, radius: int = 50) -> None:
# Vytvorime objekt pro manipulaci s obrazkem
im = Image.new("RGB", (size, size))
# Prochazime vsechny pixely naseho obrazku a kontrolujeme, zda lezi
# v kruhu
for x in range(size):
for y in range(size):
if in_circle(size, radius, x, y):
# Pixel na souradnicich (x, y) obarvime na cerno.
im.putpixel((x, y), BLACK)
else:
# Pixel na souradnicich (x, y) obarvime na bilo.
im.putpixel((x, y), WHITE)
# obrazek si muzeme zobrazit
im.show()
# nebo jej muzeme ulozit do souboru
im.save("demo_circle.png")
# Vykresli kruh o polomeru 50 na bilem ctverci o strane 150.
circle()
Abyste mohli bez problému pracovat s obrázky, musíte mít nainstalovanou
knihovnu Pillow. Následně musíte importovat třídu Image:
from PIL import Image
12.1. Kreslení¶
12.1.1. Čtverec¶
Na bílé pozadí o zadané velikosti nakreslete černý čtverec o zadané straně, jehož střed bude umístěn do středu obrázku.
from PIL import Image
def square(size: int = 250, a: int = 70) -> None:
pass
12.1.2. Trojúhelník¶
Na bílé pozadí o zadané velikosti nakreslete černý rovnostranný trojúhelník o dané straně, jehož těžiště bude umístěno do středu obrázku.
def triangle(size: int = 150, a: int = 50) -> None:
pass
12.1.3. Kruh¶
Na bílé pozadí o zadané velikosti nakreslete černý kruh o zadaném poloměru a se středem na zadaných souřadnicích.
def circle(size: int = 150, center: Tuple[int, int] = (75, 75), radius: int = 20) -> None:
pass
12.1.4. Elipsa¶
Na bílé pozadí o zadané velikosti nakreslete černou elipsu o zadaných poloměrech, jejíž střed bude umístěn do středu obrázku.
def ellipse(size: int = 150, radius_a: int = 50, radius_b: int = 20) -> None:
pass
12.1.5. Spirála¶
Na bílé pozadí o zadané velikosti nakreslete spirálu začínající ve středu obrázku.
def spiral(size: int = 150, turn_inc: int = 5, tstep: float = 0.05) -> None:
pass
12.1.6. Šachovnice¶
Nakreslete šachovnicový vzor o zadané velikosti obrázku a šířce pruhu.
def chessboard(size: int = 150, stripe: int = 30) -> None:
pass
12.1.7. Šachovnice s kruhy¶
Nakreslete následující obrázek, parametrem kreslící funkce je velikost obrázku, šířka šachovnicových pruhů a šířka mezikruží.
12.1.8. Překrývající se kruhy¶
Napište funkci, která vykreslí více černých kruhů. Každé překrytí kruhů invertuje pozadí kruhu. Kruhy jsou zadané pomocí seznamu, v němž každá položka je dvojice střed a poloměr, viz ukázka:
def circles_overlap(size: int, circles: List[Tuple[Tuple[int, int], int]]) -> None:
pass
circles = [
((20, 20), 40),
((200, 150), 100),
((200, 300), 140),
((300, 200), 50),
]
circles_overlap(500, circles)
12.1.9. Vlny¶
Napište funkci, která vykreslí následující obrázek. Parametrem je velikost obrázku a počet vln.
def waves(size: int, k: int) -> None:
pass
12.1.10. Vlny a čtverec¶
Napište funkci, která vykreslí následující obrázek. Parametrem je velikost obrázku, počet vln a strana čtverce, jehož střed je ve středu obrázku.
def waves_square(size: int, k: int, a: int) -> None:
pass
12.2. Transformace¶
V následujících příkladech budeme pracovat s již existujícími obrázky, a ty pak nějakým způsobem transformovat. Na rozdíl od předchozích příkladů budeme potřebovat otevřít soubor s již existujícím obrázkem:
im = Image.open(filename).convert("RGB")
# muzeme jednoduse zjistit rozmery obrazku
width, height = im.size
Podobně jako pro zápis barvy, existuje i rozhraní pro čtení barvy daného pixelu.
r, g, b = im.getpixel((0, 0))
im.putpixel((0, 0), (r + 1, g + 1, b + 1))
Pokud nemáte žádný vhodný obrázek po ruce, stáhněte si tento:
12.2.1. Odstranění barvy¶
Napište funkci, která odstraní z daného obrázku zelenou barvu (alternativně červenou nebo modrou):
def without_green(filename: str) -> None:
pass
12.2.2. Invertování barev¶
Napište funkci, která invertuje barvy v daném obrázku.
def invert_colors(filename: str) -> None:
pass
12.2.3. Stupně šedi¶
Napište funkci, která převede barevný obrázek na obrázek ve stupních šedi.
def grayscale(filename: str) -> None:
pass
12.2.4. Zrcadlení¶
Napište funkci, která daný obrázek transformuje do “zrcadlení”.
def mirror(filename: str) -> None:
pass
12.2.5. Převrácení¶
Napište funkci, která daný obrázek převrátí vzhledem k jeho vertikální ose.
def invert(filename: str) -> None:
pass
12.3. Šifry¶
12.3.4. Schovávačka¶
Představte si, že máte jeden černo-bílý obrázek (tedy takový, který obsahuje
jen pixely černé a bílé barvy) a chtěli byste jej schovat do jiného obrázku,
takovým způsobem, aby nebyla jeho přítomnost zřejmá. Naprogramujte tedy dvě
funkce, encode, která dostane dva obrázky a jeden ukryje do druhého, a
funkci decode, která z obrázku vytáhne ten ukrytý.
Jak na to? Poznáte okem rozdíl mezi pixely s barvami (88, 63, 149) a (88,
62, 149)? Spíš ne, takže co takhle ten jeden bit využít pro zakódování
jednoho pixelu z tajného obrázku…
Poznámka: úkolem schovávání informací tak, aby nebyly zjistitelné se zabývá vědní disciplína steganografie.