Jak skáče žabka
Abstrakt
Další článek ze série věnované úlohám matematické olympiády – kategorie P (programování) popisuje jednu praktickou soutěžní úlohu domácího kola ze školního roku 2015/16. Naším úkolem je nalézt co nejdelší posloupnost skoků žabky po kamenech ze startovního na cílový kámen. Jednotlivé skoky se během této cesty musí stále zkracovat. Ukážeme si tři různé způsoby řešení. Nejjednodušší verze je založena na zkoušení všech možných posloupností, lepší řešení využívá techniky dynamického programování a nejlepší pak ještě navíc vhodného předvýpočtu, který spočívá v seřazení všech možných skoků podle jejich délky.Stahování
Publikováno
2016-11-01
Jak citovat
Töpfer, P. (2016). Jak skáče žabka. Matematika–Fyzika–Informatika, 25(5), 376–383. Získáno z https://mfi.upol.cz/index.php/mfi/article/view/299
Čí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
