answered
2015-01-27 08:35:08 +0100
OK, pokud jde o to, "jak tu rekurzi sestavit":
Rekurzivní řešení často spočívá v tom, že daný problém rozdělíme na (dva) menší podproblémy, vyřešíme ty a následně jejich výsledky spojíme tak, aby tvořily řešení původního problému. Každý podproblém se přitom stane novým problémem, který řešíme obdobně. Dříve nebo později se dostaneme do situace, kdy ten podproblém už je triviálně řešitelný.
"Sestavení rekurze" spočívá v tom, že musíme vymyslet, jak problém rozdělit na ty menší podproblémy, jak určit, že podproblém už je triviálně řešitelný, a jak dosažená řešení podproblémů sloučit do řešení problému. Jak se to naučit nevím, asi nejspíš praxí. Ale většinou to je dost intuitivní.
Mergesort:
- Zadání: Máme neseřazené pole, chceme seřazené pole.
- Rozdělení: Pole rozdělíme na dvě půlky, každou seřadíme zvlášť (tj. pro každou půlku řešíme stejný typ problému, ale s menší instancí).
- Sloučení: Dvě seřazená pole projdeme jedním sekvenčním průchodem, do cílového pole dáváme vždycky ten prvek, který je menší (zjednodušeně řečeno).
- Detekce triviální instance: Pokud má pole právě 1 prvek, tak je nutně seřazené.
Hanojské věže:
- Zadání: Máme tři tyčky A, B, C. Na tyčce A je položeno N kroužků různé velikost, vždy menší na větším. Chceme je všechny přesunout na tyčku C, přičemž můžeme přesouvat v jednu chvíli jen jeden kroužek a musíme dodžet vlastnost "menší na větším".
- Rozdělení: Přesuneme N-1 kroužků z A na B (tj. řešíme stejný typ problému, ale s menší instancí).
- Sloučení: Poslední zbývající kroužek přesuneme z A na C, potom přesuneme N-1 (tj. všechny) kroužků z B na C.
- Detekce triviální instance: Pokud na zdrojové tyčce zbývá jen jeden kroužek, tak ho prostě přesuneme na cílovou a není co řešit.
Faktoriál: (tradiční příklad na rekurzi, ale implementačně naprosto nevhodný)
- Zadání: Chceme spočítat N!.
- Rozdělení: N! = N*(N-1)! (tj. pro druhý člen opět řešíme stejný typ problému, ale s menší velikostí).
- Sloučení: Když už známe (N-1)!, tak to jen vynásobíme N a máme N!.
- Detekce triviální instance: Z definice 1!=1, 0!=1.
Prohledávání stromu do hloubky:
- Zadání: Máme strom (reprezentovaný jeho kořenem) a hledaná data. Chceme najít vrchol, který nese ta data.
- Rozdělení: Prvek leží v listu některého z n podstromů. Podstromy prohledáváme zvlášť, každý se stává dílčím stromem (tj. stejný typ problému, menší velikost).
- Sloučení: Použijeme první/poslední/všechna/atd. (podle potřeby) nalezená řešení z podstromů.
- Detekce triviální instance: Pokud strom je listem, tak jen porovnáme jeho data s hledanými, a informujeme o výsledku.
Atd.
Nerozumím, co konkrétně se chcete naučit nebo procvičit. Použití rekurze? Počet volání rekurzivní funkce? Potřebnou velikost zásobníku? Co rozumíte tím "mám sestavit sám nějakou složitější rekurzi"?
Josef Kokeš ( 2015-01-26 17:22:07 +0100 )editNo píšu právě že teoreticky tomu docela rozumim, ale když se objeví problém, kterej se má řešit rekurzí (napadá mě třeba coin change, nebo nějaký jeho obměny atd.) tak nedokážu tu rekurzi sestavit. Chápu že tohle asi chce hodně praxi a mě jde o to jak jí získat,
relickus ( 2015-01-26 22:46:04 +0100 )editTaké u složitějších rekurzí začíná být relevantní pojem "dynamické programování". Doporučuji si i o tom něco prostudovat. Jako příklad kdy se hodí je třeba počítání Fibonacciho čísel. Dále se ohledně rekurze dá dočíst něco v přednáškách BI-EFA Efektivní algoritmy. Například přednáška 8 ale rekurzivní algoritmy jsou tam skoro všude.
Sandokan ( 2015-01-29 00:01:21 +0100 )editJj na dynprog jsem už taky koukal ale chtěl jsem se učit "popořadě" tudíž nejdřív zmáknout rekurzi a pak to ostatní.
relickus ( 2015-02-01 16:39:37 +0100 )edit