IB111 Základy programování Radek Pelánek
2018
1/72
xkcd: Tabletop Roleplaying
YOUR PARTY ENTERS THE TAVERN.
I GATHER EVERYONE AROUND / A TABLE. 2 HAVE THE ELVES / START WHITTLING PICE AND / GET OOT SOME FflRCHtfEWT / FOR CHARACTER 5HEETS. /
\       HEY; NO RZC0R5W.
\ /
https://xkcd.com/244/
2/72
To iterate is human, to recurse divine. (L. Peter Deutsch)
• použití funkce při její vlastní definici
• volání sebe sama (s jinými parametry)
https://xkcd.com/688/
Sebereferenčnř test
O Které písmeno není správnou odpovědí na žádnou otázku (A) A   (B) C   (C) B
O Odpověď na 3. otázku je:
(A) stejná jako na 1. otázku   (B) stejná jako na 2. otázku   (C) jiná než odpovědi na 1. a 2. otázku
O První otázka, na kterou je odpověď A, je otázka: (A)l   (B)2 (C)3
Hlavolamiko
• 5 pirátů si dělí poklad: 100 mincí
• nejstarší pirát navrhne rozdělení, následuje hlasování
• alespoň polovina hlasů     rozděleno, hotovo
• jinak     navrhující pirát zabit, pokračuje druhý nejstarší
(a tak dále) (rekurze!)
• priority
O přežít
O mít co nejvíce mincí
O zabít co nejvíc ostatních pirátů
složitější varianty: 6 pirátů a 1 mince, 300 pirátů a 100 mincí
Rekurze a sebereference
Rekurze a sebereference - klíčové myšlenky v informatice
některé souvislosti:
• matematická indukce
• funkcionální programování
• rekurzivní datové struktury (napr. stromy)
• gramatiky
• logika, neúplnost
• nerozhodnutelnost, diagonalizace
Rekurze a sebereference
nejen v informatice
M. C. Escher; Drawing Hands, 1948
Gödel, Escher, Bach: An Eternal Golden Braid; Douglas Hofstadter
Rekurze a úvodní programování
• uvedené aplikace rekurze a sebereference často poměrně náročné
• hodí se pořádně pochopit rekurzi na úrovni jednoduchých programů
• bezprostrední návaznost - Algoritmy a datové struktury
10/72
Faktoriál
n! = 1 • 2 • • • (n — 1) • n
f{n) =
1
pokud n = 1
n • f (n — 1)   pokud n > 1
vT) c\ o 11/72
Faktoriál iterativně (pomocí c
def fact(n): f = 1
for i in range(l, n+1):
f = f * i return f
def fact(n):
if n == 1: return 1
else: return n * fact(n-l)
13/72
Faktoriál rekurzivně - ilustrace výpočtu
fact (4)
24
4 * fact(3
3 * fact (2
'2
4 □ ►   < [S ► <
Vymyslete funkci, která:
• vypíše čísla od 1 do N
• pomocí rekurze - bez použití cyklů f or, while
15/72
Vymyslete funkci, která:
• vypíše čísla od 1 do N
• pomocí rekurze - bez použití cyklů f or, while
def sequence(n): if n > 1:
sequence(n-1) print(n)
16/72
def test(n): print(n) if n > 1:
test (n print(-n)
test(5)
Ilustrace zanořování
test(3)
3 test(2)
def
def
a rekurze
even(n):
print("even", n) odd(n-l)
odd(n):
print("odd", n) if n > 1:
even(n-l)
even(lO)
19/72
20/72
Rekurzivní stromeček
nakreslit stromeček znamená:
• udělat stonek
• nakreslit dva menší stromečky (pootočené)
• vrátit se na původní pozici
Stromeček želví grafikou
def tree(length): forward(length) if length > 10: left(45)
tree(0.6 * length) right(90)
tree(0.6 * length) left(45) back(length)
22/72
oby rekurze, odstranění rekurze
• koncová rekurze (tail recursion)
• rekurzivní volání je poslední příkaz funkce
• lze vesměs přímočaře nahradit cyklem
• „plná" rekurze
• „zanořující se" volání
• např. stromeček
o lze přepsat bez použití rekurze za použití zásobníku
• rekurzivní podoba často výrazně elegantnější
23/72
anojské věže aneb 0 konci světa
• video:
• https://www.fi.muni.cz/~xpelanek/IBlll/hanojske_veze/
• https://www.youtube.com/watch?v=8yaoED8jc8Y
o klášter kdesi vysoko v horách u města Hanoj
• velká místnost se třemi vyznačenými místy
• 64 různě velkých zlatých disků
• podle věštby mají mniši přesouvat disky z prvního na tretí místo
• a až to dokončí ...
24/72
Hanojské věže: pravidla
• N disků různých velikostí naskládaných na sobě
• vždy může být jen menší disk položen na větším
• možnost přesunout jeden horní disk na jiný kolíček
• cíl: přesunout vše z prvního na třetí
25/72
ABC ABC ABC ABC
26/72
Hanojské věže: výstup programu
»> solve(3, "A", "B", "C")
A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B
Hanojské věže: rekurzivní řešení
def solve(n, start, end, auxiliary): if n == 1:
print(start, "->", end) else:
solve(n-1, start, auxiliary, end) solved, start, end, auxiliary) solve(n-1, auxiliary, end, start)
28/72
v
Řešení včetně vypisování stavu
*
***
***
***
*
***
*
***
***
29/72
Stav úlohy, reprezentace
a stav úlohy = rozmístění disků na kolících
• disky na kolíku A seznam
• celkový stav:
• 3 proměnné, v každé seznam - nepěkné
• seznam seznamů, kolíky interně značíme 0, 1, 2
• príklad stavu (6 disků): [[4], [5, 2, 1], [6, 3]]
30/72
Řešení včetně vypisování stavu
def solve(n, start, end, aux, state): if n==l:
disc = state[start].pop()
state[end].append(disc)
print_state(state) else:
solve(n-1, start, aux, end, state) solved, start, end, aux, state) solve(n-1, aux, end, start, state)
def solve_hanoi(n):
state = [list(range(n,0,-1)),  [] , []] print_state(state) solve(n, 0, 2, 1, state)
31/72
Vypisovaní stavu - jednoduše
def print_state(state): print(state) print (" —")
def print_state(state): for i in range(3):
print("Peg", chr(ord('A')+i), state[i]) print (" —")
32/72
Vypisování stavu - textová grafika
def print_state(state):
n = sum( [len(s) for s in state]) for y in range(n+1): line = 1111
for peg in range(3):
for x in range(-n+1, n):
if len(state[peg]) > n-y and abs(x) < state[peg] [n-y]: line += "*" else:
line += 11 11 line += 11 11 print(line) print(M-M*(n*6+l))
Sierpiňského fraktál
rekurzivně definovaný geometrický útvar
aaAA a a ^
34/72
ierpiňského fraktál
35/72
ierpiňského fraktál: kód
def sierpinski(n, length): if n == 1:
triangle(length) else:
for i in range(3):
sierpinski(n - 1, length) forward((2 ** (n - 1)) * length) right(120)
36/72
< [f? ► < -e ► < -ž ►    š   o q, o
37/72
• tutor.fi.muni.cz, úloha Robotanik
• jednoduché „grafické" programovaní robota
• těžší příklady založeny na rekurzi
• vizualizace průběhu „výpočtu", zanořování a vynořování z rekurze
38/72
Robotanik - Kurz počítání
rekurze jako „paměť"
	□ x|
	F2|
F11JJ	
F2JJJ	
< [f? ► < -e ► < -ž ►    š   o q, o
40/72
Pokrývání plochy L kostičkami
• mřížka 8 x 8 s chybějícím levým horním polem
• úkol: pokrýt zbývající políčka pomocí L kostiček
• rozšíření:
• rozměr 2n x 2n
• chybějící libovolné pole
9 obarvení 3 barvami, aby sousedi byli různí
42/72
J	
1	
• rozdělit na čtvrtiny
• umístit jednu kostku
• rekurzivně aplikovat řešení na jednotlivé části
43/72
44/72
Kahoot: program A
def magic(n):
return n + magic(n)
45/72
Kahoot: program B
def test(n): if n > 0:
print(n, end test(n-1) print(n, end
test(3)
řemýšlenío funkcích (rekurzivních obzvlášť)
obecně pro funkce:
• ujasnit vstupně-výstupní chování než začnu psát funkci
rekurzivní funkce navíc:
• při psaní funkce předpokládám, že mám již funkci hotovou
• problém převedu na řešení menšího problému (který již umím vyřešit)
• ošetřím „koncovou podmínku"
Otočení řetězce rekurzivně
»> reverse ("star wars") ;sraw rats;
Otočení řetězce rekurzivně
»> reverse ("star wars") ;sraw rats;
def reverse(s):
if len(s) <= 1: return s return reverse(s [1:]) + s[0]
48/72
Kontrolní otázka
Co dělá následující funkce (vstup je řetězec)
def magie(s):
if len(s) <= 1: return s return magic(s[l:])
Seznam vnořených seznamů
Seznam čísel a vnořených seznamů čísel (SCAVSC) je seznam, který obsahuje čísla nebo SCAVSC.
rekurzivní datová struktura
scavsc = [[2, 8], 4,   [3,  [1, 7], 6],  [2, 4]] Jak vypočítat součet všech čísel?
50/72
Součet vnorených seznamů
def nested_list_sum(alist): total = 0 for x in alist:
if isinstance(x, list):
total += nested_list_sum(x) else:
total += x return total
< if? ► < = > < -ž ►    -s   o q, o
51/72
Príklady použití rekurze v informatice
• Euclidův algoritmus - NSD
• vyhledávání opakovaným půlením
a řadicí algoritmy (quicksort, mergesort)
• generování permutací, kombinací
• fraktály
• prohledávání grafu do hloubky
• gramatiky
52/72
Euklidův algoritmus rekurzivně
def nsd(a,b): if b == 0:
return a else:
return nsd(b, a °/0 b)
hra na 20 otázek hledání v seznamu hledání v binárním stromu
54/72
Vyhledávání: rekurzivní varianta
def binary_search(value, alist, lower, upper): if lower > upper:
return False mid = (lower + upper) // 2 if alist[mid] < value:
return binary_search(value, alist, mid+1, upper) elif alist[mid] > value:
return binary_search(value, alist, lower, mid-1) return True
55/72
Řadicí algoritmy
• quicksort
• vyber pivota
• rozděl na menší a větší
• zavolej quicksort na podčásti
• mergesort
• rozděl na polovinu
• každou polovinu seřaď pomocí mergesort
• spoj obě poloviny
56/72
Generování permutací, kombinací
• permutace množiny = všechna možná pořadí
• příklad: permutace množiny {1,2,3,4}
• jak je vypsat systematicky?
• jak využít rekurzi?
• /c-prvkové kombinace n-prvkové množiny = všechny možné výběry k prvků
• příklad: 3-prvkové kombinace množiny {/4, 6, C, D, E}
• jak je vypsat systematicky?
• jak využít rekurzi?
def combinations(alist, k): if k == 0: return [ [] ] if len(alist) < k: return [] output = []
for comb in combinations(alist[1:], k-1):
comb.append(alist [0])
output append(comb) output.extend(combinations(alist[1:], k)) return output
58/72
ne každé použití rekurze je efektivní Fibonacciho posloupnost (králíci):
f2 = i
'n — fn-1 + fn-:
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Vi Hart: Doodling in Math: Spirals, Fibonacci, and Being a Plant
Fibonacciho posloupnost: rekurzivně
def fib(n):
if n <= 2: return 1
else: return fib(n-l) + fib(n-2)
60/72
Fibonacciho posloupnost: rekurzivní výpočet
fib(5)
,.-''fib(3p\ +
fib(4)
:fib(1) + fib(2):
%1
fib(2)   +,-'' fib(3Kx
i fib(1) + fib(2):
61/72
roblém N dam
• šachovnice N x N
9 rozestavit N dam tak, aby se vzájemně neohrožovaly
• zkuste pro N = 4
pozn. speciální případ „problému splnění podmínek"
63/72
Problém N dam - algoritmus
• ilustrace algoritmu backtracking
• hrubá síla, ale „chytré"
• začneme s prázdným plánem, systematicky zkoušíme umisťovat dámy
• pokud najdeme kolizi, vracíme se a zkoušíme jinou možnost
• přirozený rekurzivní zápis
64/72
HHHH HHHH
resen i
65/72
Problém N dam - reprezentace stavu
• pro každé pole si pamatujeme, zda na něm je/není dáma
• dvourozměrný seznam True/False
• pro každou dámu si pamatujeme její souřadnice
• seznam dvojic x;,y;
• pro každý řádek si pamatujeme, v kterém sloupci je dáma
• seznam čísel x;
o nejvýhodnější reprezentace
66/72
Problém N dam - řešení
def solve_queens(n, state): if len(state) == n: output(state) return True else:
for i in range(n): state.append(i) if check_queens(state) if solve_queens(n, state.pop() return False
state): return True
67/72
Xi X2
Vi
							
							
							
							
							
							
							
							
vT) c\ o
68/72
Kdy se ohrožují dvě dámy?
Xi X2
yi
							
							
							
							
							
							
							
							
Xi = x2
yi = y2 *i +yi *i -yi
^2 + y2
x2 -y2
69/72
Problém N dam - řešení
def
def
output(state):
for y in range(len(state)):
for x in range(len(state)):
if state [y]==x: print ("X", end=M 11) else: print (".11, end=" 11) print() print()
check_queens(state): for yl in range(len(state)): xl = state[yl]
for y2 in range(yl+1, len(state)): x2 = state[y2]
if xl == x2 or xl-yl == x2-y2 or\ xl+yl == x2+y2:
return False
70/72
Backtracking - další príklady použití
• mnoho logických úloh:
• Sudoku a podobné úlohy
• algebrogramy (SEND + MORE = MONEY)
• optimalizační problémy (např. rozvrhování, plánování)
• obecný „problém splnění podmínek"
71/72
• rekurze: využití rekurze pro definici sebe sama
a logické úlohy: Hanojské věže, L kostičky, dámy na šachovnici
• fraktály
• aplikace v programování: vyhledávání, řazení, prohledávání grafu
• klíčová myšlenka v informatice nezapomeňte na piráty
72/72