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 839 Not so Mobile

42. Velmi přehledná funkce 10696 f91
Rekurentní vztah odvodíte snadno, když začnete u vhodné hodnoty N.

43. Připojte domečky k síti 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 183 Bit Maps
Mapu lze rekonstruovat jedním průchodem vstupního řetězce.

45. Je to ještě vůbec rekurze? 10579 Fibonacci Numbers

46. Klasický backtracking 995 Super Divisible Numbers
Co číslice, to krok backtracku, číselná soustava je tu spíše jen jako ozdoba.

47. Hanojské věže 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 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 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 11645 Bits
Asi příbuzné s předchozí úlohou?

4B. Stavba nízké zídky 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.

courses/a4b36acm1/2012_zs/seminar_4_1110.txt · Last modified: 2018/10/03 03:51 (external edit)