2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Medžių grupė

Taškai: 9

Bebrė žymi medžius, kuriuos nori panaudoti užtvankai statyti. Ji apjuosia medžius virve – visi medžiai apjuostoje srityje bus jos.

Pavyzdžiui, jei medžiai, žiūrint iš viršaus, atrodytų taip, tai bebrė juos galėtų apjuosti:

Apjuostoje teritorijoje iš viso yra 6 medžiai, bet virvė liečia tik 5 medžius.

Medžiai iš viršaus atrodo štai taip:

Kelis medžius liestų virvė juos apjuosus?

A. 4 B. 5 C. 5 D. 7
Paaiškinimas

Ši problema vadinama taškų aibės iškiliojo apvalkalo (angl. convex hull) paieška. Vienas sprendimo būdų – mažiausio ploto, kuriame yra visi rinkinyje esantys taškai, daugiakampis. Žodis „iškilusis“ reiškia išgaubimą ir bet kurie du išgaubtos figūros taškai, nupiešti ant popieriaus, gali būti sujungti tiesia linija, esančia figūros viduje. Žodis „apvalkalas“ čia nusako „kevalą“, „lukštą“ arba „dėžę“,„įpakavimą“, sėklos lukšto ar kevalo atitikmenį.

Taškų aibės iškiliojo apvalkalo paieška naudojama įvairiuose skaičiavimuose:

  • atpažinimo teorija: ar paveiksliuke yra veidas?
  • rašytinio teksto apdorojimas: ar ranka parašytas rašmuo yra raidė B?
  • geografinės informacinės sistemos: koks yra salpos ar upių sistemos dydis?
  • pakavimas: koks mažiausias įpakavimo kiekis, reikalingas tvirtai įvynioti trimatį objektą?

Yra daugybė algoritmų šiai problemai spręsti, o efektyvus šios problemos sprendimas labai praktiškas ir naudingas kompiuterių algoritmų pritaikymas.

Taip pat žiūrėkite: 
https://en.wikipedia.org/wiki/Convex_hull_algorithms 
https://en.wikipedia.org/wiki/Convex_hull 
https://brilliant.org/wiki/convex-hull

Atsakymas

Teisingas atsakymas: 6

Sprendimą galima būtų pasivaizduoti taip: