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.

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

Těžká varianta

courses/b3b33alp/cviceni/t07.txt · Last modified: 2021/09/15 11:10 by vonasvoj