Rozkopané křižovatky (Úlohy z MO kategorie P, 42. část)

Autoři

  • Pavel Töpfer Matematicko-fyzikální fakulta UK, Praha

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://www.mfi.upol.cz/index.php/mfi/article/view/555

Číslo

Sekce

Informatika