Cvičení 7: Rekurze, třídění

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);

• 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$

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$.

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?

• 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:

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 Hanojské věže

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']]

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

• 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.

• 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

2) Pro vstup

15 10 51 34 51 26 15 43
81

program vytiskne:

51 15 15

3) Pro vstup

44 34 16 18 55 25 42
78

program vytiskne buď:

44 34 

44 18 16

• 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
  1. sekvenci čísel A z čísel X, jejíž součet je roven s1 a
  2. 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
    1. na čísla, jejichž součet je roven s1 a
    2. 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

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

485 306 124 59 20 1
497 471 431 400

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