====== 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: 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 2: 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 3: 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 4: 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 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$. Podrobné vysvětlení řešení je ve videu [[https://www.youtube.com/watch?v=7M-FMkA4G4o|Hanojské věže]] ==== Ú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']] ===== 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 (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í úkol ===== ==== Lehká varianta ==== * Napište program **recurrent.py** pro výpočet následující rekurentní funkce: * $R_n(x)=\frac{n}{x} \cdot R_{n-1}(x) + (-1)^n \cdot \frac{n+1}{n-1} \cdot R_{n-2}(x) + \frac{n-1}{2 x} \cdot R_{n-3}(x)$, přičemž * $R_0(x)=-1$, $R_1(x)=x$ a $R_2(x)=-\frac{x+1}{3}$ * 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: 5 1.5 program vytiskne: -40.14814814814815 pro vstup 20 -15.3 program vytiskne: 948.4876144737897 a pro vstup 50 44.4 program vytiskne: -800555.6302016332 ==== Těžká varianta ==== * Napište program **ubongo.py**, který si ze souboru se jménem prvního argumentu programu, přečte rozměr pole a díly, kterými má to pole zaplnit * první řádek obsahuje dvě čísla //S// //R//, kde //R// je počet řádků a //S// je počet sloupců obdélníkového pole * dále násluduje //R// řádků, kde * 0 - definují volná pole v matici, která se mají vyplnit zadanými dílky * -1 - definují obsazená pole, kam dílky nesmí zasahovat * čísla na jednom řádku jsou oddělena jednou nebo více mezerami (použijte funkci "split()" bez parametrů). * každý další řádek obsahuje popis jednoho dílku: * jedna řádka obsahuje souřadnice čtverečků (x y), ze kterých je sestaven celý dílek * souřadnice jsou uvedeny za sebou bez oddělovacích čárek a závorek * jednotlivé souřadnice mohou být libovolně posunuty, dílek nemusí obsahovat čtverec se souřadnicemi (0,0) * Program v souboru **ubongo.py** nalezne pokrytí volných polí matice dílky, které mohou být natočeny, ale nesmí být zrcadlově převráceny. * Výstupem programu je pokrytí matice dílky, kdy plocha prvního dílku (zadaný v souboru hned za maticí volného místa) je vyplněna číslem 1, plocha druhého dílku (na další řádce za prvním dílkem) číslem 2, ... * Notace pro popis dílků: je to seznam x y souřadnic. * Pro T-dílek na obrázku je jeho popis: 0 0 1 0 2 0 1 1 {{:courses:b3b33alp:cviceni:blokus1.eps.png?200|}} * Pro vstup 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 -1 -1 0 0 0 0 0 0 1 0 2 1 2 2 2 2 1 0 0 0 1 1 1 2 1 2 0 2 2 0 0 1 0 1 1 1 2 1 3 0 2 1 2 2 2 1 1 1 0 Graficky znázorněné všechny dílky této úlohy: 1:{{:courses:b3b33alp:cviceni:ubongo-0.png?100|}} 2:{{:courses:b3b33alp:cviceni:ubongo-1.png?100|}} 3:{{:courses:b3b33alp:cviceni:ubongo-2.png?100|}} 4:{{:courses:b3b33alp:cviceni:ubongo-3.png?100|}} program vytiskne: 4 3 3 3 3 4 4 4 2 3 4 2 2 2 1 -1 2 1 2 1 -1 -1 1 1 1