Rozkopané křižovatky (Úlohy z MO kategorie P, 42. část)
Abstrakt
V dalším dílu cyklu zajímavých úloh z Matematické olympiády kategorie P (programování) se seznámíme s jednou praktickou úlohou z celostátního kola 45. ročníku MO (školní rok 1995/96). Úkolem v ní bylo určit počet různých cest mezi dvěma body v pravidelné pravoúhlé silniční síti, ve které jsou ovšem některé křižovatky neprůjezdné. K efektivnímu vyřešení této úlohy použijeme poměrně známou programátorskou techniku dynamického programování. Ukážeme si různé způsoby, jak lze takové řešení implementovat, a také skutečnost, že se tyto způsoby mohou lišit z hlediska výsledné časové složitosti. Stejné principy ovšem platí i pro řešení mnoha jiných úloh využívajících dynamické programování.Stahování
Publikováno
2021-08-31
Jak citovat
Töpfer, P. (2021). Rozkopané křižovatky (Úlohy z MO kategorie P, 42. část). Matematika–Fyzika–Informatika, 30(3), 220–227. Získáno z https://mfi.upol.cz/index.php/mfi/article/view/555
Číslo
Sekce
Informatika
Licence
Autoři, kteří publikují v tomto časopise, souhlasí s následujícími body:
- Autoři si ponechávají copyright a garantují časopisu právo prvního publikování, přitom je práce zároveň licencována pod Creative Commons Attribution licencí, která umožňuje ostatním sdílet tuto práci s tím, že přiznají jejího autora a první publikování v tomto časopisu.
- Autoři mohou vstupovat do dalších samostatných smluvních dohod pro neexkluzivní šíření práce ve verzi, ve které byla publikována v časopise (například publikovat ji v knize), avšak s tím, že přiznají její první publikování v tomto časopisu.
Obsah časopisu podléhá licenci Creative Commons Uveďte autora 3.0 Česko
