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);
binomial(k,n)
, která počítá hodnotu $ n \choose k $
Napište rekurzivní výpočet Fibonacciho posloupnosti. Pro tuto posloupnost platí:
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:
fib(n)
si nejprve zjistí, jestli už je znám výsledek pro $n$
hint[]
Napište funkci fibFast(n)
pro zrychlený výpočet Fibonacciho posloupnosti
hint
?
a=[1, 2, [3, [4, 5], 6, [7]], [8, 9], 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
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 .
int
string
a je to hodnota karty, tedy např. “Q” nebo “1”
[1,“1”], [2,“A”], [0,“K”]
Napište funkci, který vzestupně třídí karty podle jejich barvy a podle jejich hodnoty.
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$.
$ \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.
X
a číslo s
a najde čísla v X
, jejichž součet je roven s
.
X
.
s
.
X
, jejichž součet je roven s
.
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.
X
lze s
získat vždy.
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.
Ukázky:
1) Pro vstup
1 6 3 10 20 15 23
program vytiskne:
20 3protože
s = 23 = 20 + 3
.
2) Pro vstup
15 10 51 34 51 26 15 43 81
program vytiskne:
51 15 15Číslo 15 se ve vstupní množině objevuje 2-krát, proto je možné ho do součtu zařadit také 2-krát.
3) Pro vstup
44 34 16 18 55 25 42 78
program vytiskne buď:
44 34nebo
44 18 16protože tato úloha má dvě řešení.
X
a dvě čísla s1
a s2
a najde
A
z čísel X
, jejíž součet je roven s1
a
B
z čísel X
, která nejsou v A
, a jejichž součet je roven s2
.
X
jako sekvenci celých kladných čísel oddělených mezerou.
s1 s2
ve formátu dvou celých kladných čísel oddělených mezerou.
X
s1
a
s2
.
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.
s1
, součet čísel na druhém řádku bude roven s2
.
NEEXISTUJE
.
Ukázky:
1) Pro vstup
18 1 15 21 19 11 26 41
program vytiskne:
15 11 21 19 1protože
s1=26=15+11
a s2=41=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 1nebo:
485 306 124 59 20 1 497 471 431 400nebo:
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 407Tyto delší sekvence o maximálně 25 číslech by měl Váš program zpracovat do 10s.