====== Cvičení 7: Rekurze, třídění ======
==== Rekurze ====
Při rekurzivním volání volá funkce samu sebe. Aby nedošlo k nekonečné smyčce, musí toho volání obsahovat ukončovací podmínku. Obecně lze rekurzi zapsat
def funkce(promenna):
if (ukoncovaci podminka):
funkce(zmenena_promenna)
Pomocí rekurze můžeme například implementovat **for** cyklus:
def recursivePrint(index, array):
if (index < len(array) ):
print(array[index], end=' ' );
recursivePrint(index+1, array)
print(array[index], end=' ' );
a = []
for i in range(10):
a.append(i*i)
print("List je",a)
recursivePrint(0, a);
==== Úkol 1: narovnání ====
* Uvažujme pole, které může obsahovat jako prvky další pole, např.:
a=[1, 2, [3, [4, 5], 6, [7]], [8, 9], 10]
* Napište funkci flatten, která vytvoří jedno pole, které bude obsahovat všechny prvky z pole a vložené do tohoto pole.
* Výsledkem funkce $flatten(a)$:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
* K testu prvku, zda je pole (list), použijte funkci type:
if type(x) is list:
==== Úkol 2: binomický koeficient ====
* Napište funkci ''binomial(k,n)'', která počítá hodnotu $ n \choose k $
* Můžete využít vztah $ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} $
* Počáteční podmínky $\binom{n}{0}=\binom{n}{n}=1$ a $\binom{n}{1}=\binom{n}{n-1}=n$
==== Úkol 3: výpočet Fibonacciho posloupnosti ====
Napište rekurzivní výpočet Fibonacciho posloupnosti. Pro tuto posloupnost platí:
* $F_n = F_{n-1} + F_{n-2}$
* První členy posloupnosti jsou $F_0 = 0$ a $F_1 = 1$.
==== Úkol 4: rychlejší výpočet Fibonacciho posloupnosti ====
Předchozí řešení je pomalé pro výpočet větších $n$. Důvodem je, že při rekurzivním volání dochází často k opakovanému výpočtu stejných členů posloupnosti.
{{courses:b3b33alp:cviceni:fibonaccistack.png?300|}}
Řešením je zapamatovat si již vypočítané hodnoty a ty použít:
* Funkce ''fib(n)'' si nejprve zjistí, jestli už je znám výsledek pro $n$
* Pokud ano, vrátí ho
* Pokud ne, vypočítá hodnotu posloupnosti pro $n$ a uloží ho do seznamu známých hodnot
* Známé hodnoty lze ukládat např. v globálním poli ''hint[]''
Napište funkci ''fibFast(n)'' pro zrychlený výpočet Fibonacciho posloupnosti
* Porovnejte časy výpočtu fib(100) a fibFast(100)
* Jak byste lépe alokovali pole ''hint''?
==== Úkol 5: hanojské věže ====
Máme tři věže (označme je $A$,$B$ a $C$), na kterých je rozmístěno $n$ disků o různých velikostech. Vždy platí, že menší disk smí být položen na větší disk, ne naopak. Na začátku je všech n disků na věži $A$, přičemž jsou seřazeny podle velikosti (největší leží dole, nejmenší nahoře).
Cílem je přemístit disky tak, aby všechny ležely na věži $C$.
==== Úkol 6: třídění karet ====
Uvažujme [[ https://en.wikipedia.org/wiki/Playing_card#/media/File:Svg-cards-2.0.svg | hrací karty ]].
* Máme karty čtyř barev, každá barva má dále karty 2,3,4,5,6,7,8,9,10,J,Q,K,A
* Kartu budeme reprezentovat 1D polem, kde:
* první prvek je barva karty (0,1,2,3). Tento prvek bude ''int''
* druhý prvek je typu ''string'' a je to hodnota karty, tedy např. "Q" nebo "1"
* Příklad karty: ''[1,"1"], [2,"A"], [0,"K"]''
* Pořadí karet v dané barvě je toto: 2,3,4,5,6,7,8,9,10,J,Q,K,A, kde
* 2 má nejmenší hodnotu
* A má největší hodnotu
* platí že $2<3$, $3<4$, ... Q $<$ K, J $>$ 10, atd.
Napište funkci, který **vzestupně** třídí karty podle jejich barvy a podle jejich hodnoty.
* na vstupu je seznam (pole) karet
* funkce vrátí setříděné pole tak, že na začátku budou karty barvy 0, pak karty barvy 1,atd., přičemž v každé skupině budou karty setříděny podle jejich hodnot.
* Příklad:
cards = [ [3,"A"], [3,"Q"], [0,"2"], [1,"10"] ]
výsledek pro setřídění:
[ [0, "2"], [1, "10"], [3, "Q"], [3, "A"] ]
Seřaďte toto pole:
cards = [[0, 'Q'], [2, '10'], [1, 'K'],
[1, '8'], [2, '10'], [2, '4'],
[3, '4'], [0, '4'], [1, '3'],
[2, '5'], [0, 'K'], [3, '4'],
[1, 'J'], [0, '3'], [0, '9']]
===== domácí příprava =====
==== Expanze polynomu ====
Napište funkci, která vypíše expanzi polynomu $(x+y)^n$.
* Nápověda: $(x+y)^n = \sum_0^n {n \choose k} x^{n-k}y^k$
* Tip: místo výpisu může funkce vrátit pole reprezentující polynom (viz {{ https://cw.fel.cvut.cz/wiki/courses/b3b33alp/cviceni/t04 | cvičení 4}} )
==== Determinant matice ====
* rekurzivní výpočet determinantu pomocí kofaktorové metody můžeme rozvinout determinant podle řádku či podle sloupce, což je pro relativně malé matice celkem efektivní metoda. Například podle řádku i
$ \det \mathbf {A} =\sum _{j=1}^{n}\ {a}_{ij}{C}_{ij}$
kde $ {C}_{ij}$ jsou kofaktory, tedy $ {C}_{ij}$ je $ (-1)^{i+j}$ krát determinant matice, která vznikne z A odstraněním i-tého řádku a j-tého sloupce.
===== domácí práce =====
==== Lehká varianta ====
* Napište program **recurrent.py** pro výpočet následující rekurentní funkce:
* $R_n(x)=\frac{n}{n+1} \cdot R_{n-1}(x) + (-1)^n \cdot \frac{n+2}{n} \cdot R_{n-2}(x) + \frac{x}{n+2} \cdot R_{n-3}(x)$, přičemž
* $R_0(x)=1$, $R_1(x)=2 \cdot x$ a $R_2(x)= 3 \cdot x$
* Program načte z první řádky standardního vstupu celé kladné číslo $n$ a z druhé řádky standardního vstupu reálné číslo $x$.
* Program na výstup vytiskne hodnotu $R_n(x)$.
* Ověření výsledku probíha s přesností na 8 desetinných míst.
* Program musí pracovat efektivně a umět spočítat hodnotu funkce $R$ i pro hodnoty n=100
* Program v souboru **recurrent.py** odevzdejte do odevzdávacího systému (úloha HW07).
Například pro vstup:
7
1.577
program vytiskne:
4.24302193
==== Těžká varianta ====
* Napište program **bracket.py**, který si ze standardního vstupu přečte číslo N, na druhé řádce číslo M, na třetí řádce číslo O
* Na standardní výstup vygeneruje všechny možné korektní uzávorkování s použitím N závorek typu '()', M závorek typu '[]' a O závorek typu '{}'
* Čísla M, N, O jsou celá čísla větší nebo rovna 0
* Pořadí jednotlivých řádků výstupu nehraje při vyhodnocení roli.
* Program v souboru **bracket.py** odevzdejte do odevzdávacího systému (úloha HW07).
**Příklad I** Vstup:
1
2
0
Výstup:
[]([])
()[][]
[[]]()
[][]()
()[[]]
[()][]
([])[]
[[()]]
[()[]]
[([])]
[[]()]
([[]])
[][()]
([][])
[]()[]
**Příklad II.** Vstup
1
1
1
program vytiskne (ukazujeme pouze prvních 15 řádků, délka úplného řešení pro vstup (1, 1, 1) je 30):
([{}])
([]{})
([]){}
({[]})
({}[])
({})[]
()[{}]
()[]{}
(){[]}
(){}[]
[({})]
[(){}]
[()]{}
[{()}]
[{}()]
...