====== 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

<code python>
def funkce(promenna):
   if (ukoncovaci podminka):
      funkce(zmenena_promenna)         
</code>

Pomocí rekurze můžeme například implementovat **for** cyklus:

<code python>
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);
</code>


==== Úkol 1: narovnání ====

  * Uvažujme pole, které může obsahovat jako prvky další pole, např.:
<code>
a=[1, 2, [3, [4, 5], 6, [7]], [8, 9], 10]
</code>
  * 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)$:
<code>
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
</code>
  * K testu prvku, zda je pole (list), použijte funkci type:
<code python>
if type(x) is list:
</code>
 
==== Ú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: 
  
<code python>  
cards = [  [3,"A"],  [3,"Q"],  [0,"2"],  [1,"10"]  ]
</code>

výsledek pro setřídění:

<code python>
[  [0, "2"],  [1, "10"],  [3, "Q"],  [3, "A"]  ]
</code>

Seřaďte toto pole:

<code python>
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']]
</code>
===== 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 **recurent.py** pro výpočet následující rekurentní funkce: 
    * $R_n(x)=\frac{n-2}{n}xR_{n-1}(x)-\frac{1}{n}R_{n-2}(x)+\frac{3}{n+1}R_{n-3}(x)$, přičemž
    * $R_0(x)=1$, $R_1(x)=x$ a $R_2(x)=2x$
  * 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)$. 
  * Program musí pracovat efektivně a umět spočítat hodnotu funkce $R$ i pro hodnoty n=100
  * Program v souboru **recurent.py** odevzdejte do odevzdávacího systému (úloha HW07).

Například pro vstup:
<code>
3
14.58
</code>

program vytiskne:
<code>
137.6076
</code>

==== 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 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 
<code>
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
</code>

Příklad dílku 1:
<code>
0 0 0 1 0 2 1 2 2 2 2 1
</code>

<code>
souřadnice 
y

2***
1* *
0*
 012 souřadnice x
</code>



Graficky znázorněné všechny dílky

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:

<code>
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
</code>