=== Seminář 4 (11.10.) Rekurze, backtrack,  minisoutěž ===

Do soutěže a klasifikace se počítá každá vyřešená úloha ze všech uvedených níže. Prohlédněte si zběžně všechny a snažte se určit si pro sebe jejich vhodné pořadí od nejjednodušších až po nejnáročnější, i to je důležitou součástí soutěžní strategie.

------------

**Soutěžní úlohy** \\
**41.** Klasický průchod postorder [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=780| 839 Not so Mobile ]]\\

**42.** Velmi přehledná funkce [[ http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1637|10696 f91]]\\
//Rekurentní vztah odvodíte snadno, když začnete u vhodné hodnoty N.//

**43.** Připojte domečky k síti [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1803|10862 Connect the Cable Wires]]\\
//Zbavte se rekurze standardním obratem tak, že budete předpokládat znalost F(1), F(2), ... F(N) a potom si rozmyslíte, co se stane a jak tato čísla využijete, když přidáte jeden domeček, tj, když budete hledat F(N+1).// 

**44.** Komprese 2D bitových map [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=119|183 Bit Maps]]\\
//Mapu lze rekonstruovat jedním průchodem vstupního řetězce.//

**45.** Je to ještě vůbec rekurze? [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1520|10579 Fibonacci Numbers]]\\

**46.** Klasický backtracking [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=936|995 Super Divisible Numbers]]\\
//Co číslice, to krok backtracku, číselná soustava je tu spíše jen jako ozdoba.// 

**47.** Hanojské věže [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=190|254 Towers of Hanoi]]\\
//Rozmyslete si, a i nasimulujte, jak se jednotlivé konfigurace opakují, abyste nemuseli překládat pokaždé všechny disky.// 

**48.** Pouze specifické posloupnosti z 0 a 1 [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1391|10450 World Cup Noise]]\\  
//Počítejte zvlášť počet posloupností délky k končících 0 a zvlášť končících 1, při hledání počtu posloupností délky k+1 se to může hodit.//

-------------
**Nášup** také soutěžně použitelný\\

**49.** Spravedlivé házení mincemi [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1269|10328 Coin Toss]]\\
//Ve skutečnosti jde o řetězce s určitými vlastnostmi, něčím to připomíná úlohu 48 (10450 World Cup Noise).//

**4A.** Počty sousedních jedniček [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2692|11645  Bits ]]\\
//Asi příbuzné s předchozí úlohou?//

**4B.** Stavba nízké zídky [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1859|10918 Tri Tiling]]\\
//Uvažte, jestli i tuto úlohu lze z rekurze převést na DP pomocí vhodné tabulky reflektující rozmanitě členité konce rozestavěné zdi.//