Minimální triangulace mnohoúhelníku (Úlohy z MO kategorie P, 50. část)
Abstrakt
Dnešním jubilejním 50. dílem uzavíráme dlouhodobý seriál článků, ve kterém jsme vás postupně seznámili s vybranými soutěžními úlohami z Matematické olympiády kategorie P (programování). Zmíněných 50 článků vycházelo na stránkách našeho časopisu od roku 2000 až do současnosti, tedy po dobu plných 25 let. Tentokrát si ukážeme jednu klasickou kombinatorickou úlohu, která byla zadána v celostátním kole 39. ročníku MO kategorie P ve školním roce 1989/90. Zabývá se tzv. triangulací mnohoúhelníku, což znamená rozdělení jeho plochy na samé trojúhelníky pomocí úhlopříček, které se vzájemně nikde nekříží. Jak uvidíme, efektivní řešení této úlohy bude založeno na myšlence dynamického programování, což je metoda velmi často využívaná nejen v různých soutěžních úlohách, ale i v programování obecně.
Stahování
Publikováno
Jak citovat
Číslo
Sekce
Licence
Copyright (c) 2025 Matematika–Fyzika–Informatika
Tato práce je licencována pod Mezinárodní licencí Creative Commons Attribution 4.0 .
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
