====== 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 not (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); ==== 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$ ==== 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$. ==== 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''? ==== 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: ==== 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$. Podrobné vysvětlení řešení je ve videu [[https://www.youtube.com/watch?v=7M-FMkA4G4o|Hanojské věže]] ==== Řazení 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']] ===== Témata k procvičení ===== ==== 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 ==== 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í úkol ===== ==== Lehká varianta ==== * Napište program **select.py**, který si ze standardního vstupu přečte sekvenci kladných čísel ''X'' a číslo ''s'' a najde čísla v ''X'', jejichž součet je roven ''s''. * ** Vstup: ** * První řádek obsahuje celá **kladná** čísla oddělená mezerou. Tato čísla reprezentují množinu čísel ''X''. * Druhý řádek obsahuje jedno celé **kladné** číslo ''s''. * ** Úkol: ** * Program nalezne čísla z ''X'', jejichž součet je roven ''s''. * Pro součet můžete využít každé číslo z ''X'' maximálně jednou. Pokud je v ''X'' některé číslo vícekrát, můžete pro součet použít každý jeho výskyt. * Pokud by existovalo více řešení zadaného problému, vypište pouze jedno řešení. Je jedno které. * Můžete se spolehnout na to, že ze zadaného ''X'' lze ''s'' získat vždy. * ** Výstup: ** * Výstupem programu je výpis čísel z ''X'', jejichž součet je roven ''s''. Čísla jsou vypsána na jeden řádek od největšího k nejmenšímu. Čísla jsou oddělená mezerou. * **Nápověda:** * Projděte si přednášku //6) Rekurze// a nechte se inspirovat problémem //Mince//. **Ukázky:** 1) Pro vstup 1 6 3 10 20 15 23 program vytiskne: 20 3 protože ''s = 23 = 20 + 3''. 2) Pro vstup 15 10 51 34 51 26 15 43 81 program vytiskne: 51 15 15 Číslo 15 se ve vstupní množině objevuje 2-krát, proto je možné ho do součtu zařadit také 2-krát. 3) Pro vstup 44 34 16 18 55 25 42 78 program vytiskne buď: 44 34 nebo 44 18 16 protože tato úloha má dvě řešení. ==== Těžká varianta ==== * Napište program **compose.py**, který si ze standardního vstupu přečte sekvenci kladných čísel ''X'' a dvě čísla ''s1'' a ''s2'' a najde - sekvenci čísel ''A'' z čísel ''X'', jejíž součet je roven ''s1'' a - sekvenci čísel ''B'' z čísel ''X'', která nejsou v ''A'', a jejichž součet je roven ''s2''. * ** Vstup: ** * První řádek obsahuje ''X'' jako sekvenci celých **kladných** čísel oddělených mezerou. * Druhý řádek obsahuje ''s1 s2'' ve formátu dvou celých **kladných** čísel oddělených mezerou. * ** Úkol: ** * Program rozdělí ''X'' - na čísla, jejichž součet je roven ''s1'' a - na čísla, jenž ještě nebyla použita a jejichž součet je roven ''s2''. * Pro součty můžete využít každé číslo z ''X'' maximálně jednou. Pokud je v ''X'' některé číslo vícekrát, můžete pro součty použít každý jeho výskyt. * Pokud by existovalo více řešení zadaného problému, vypište pouze jedno řešení. Je jedno které. * Zadání nemusí mít řešení. * ** Výstup: ** * Pokud existuje řešení: * Dvě řádky čísel oddělených mezerou a seřazených na každé řádce podle velikosti od největšího po nejmenší. Součet čísel na prvním řádku bude roven ''s1'', součet čísel na druhém řádku bude roven ''s2''. * Pokud neexistuje řešení: * Výstupem programu bude ''NEEXISTUJE''. **Ukázky:** 1) Pro vstup 18 1 15 21 19 11 26 41 program vytiskne: 15 11 21 19 1 protože ''s1=26=15+11'' a ''s2=41=21+19+1'' 2) Pro vstup 80 195 106 51 186 150 63 45 310 91 286 946 program vytiskne: 195 91 310 186 150 106 80 63 51 3) Pro vstup 59 1 20 124 306 471 186 431 400 497 485 995 1799 program vytiskne buď: 485 431 59 20 497 471 400 306 124 1 nebo: 485 306 124 59 20 1 497 471 431 400 nebo: 471 400 124 497 485 431 306 59 20 1 4) Pro vstup 126 281 78 302 471 255 204 98 453 4 269 813 809 program vytiskne: NEEXISTUJE 5) Pro vstup 440 1196 1478 405 874 652 217 1488 136 1137 407 796 1208 411 1602 1498 453 1085 1016 596 308 931 975 1226 1562 1718 2499 program vytiskne: 652 405 308 217 136 1085 596 411 407 Tyto delší sekvence o maximálně 25 číslech by měl Váš program zpracovat do 10s.