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í
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]
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í:
Ú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
Ú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']]
domácí příprava
Expanze polynomu
Napište funkci, která vypíše expanzi polynomu $(x+y)^n$.
Determinant matice
$ \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:
3
14.58
program vytiskne:
137.6076
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, …
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
Příklad dílku 1:
0 0 0 1 0 2 1 2 2 2 2 1
souřadnice
y
2***
1* *
0*
012 souřadnice x
Graficky znázorněné všechny dílky
1:
2:
3:
4:
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