BEBRO konkurso užduotys 2017

 

Kirminas

Taškai: 9

Ant didžiulio medžio – obels – šakos galo įsitaisęs kirminas. Jis nori sugraužti visus obuolius, šliauždamas obels šakomis. Kiekviena šakos atkarpa yra 1 metro ilgio.

Kiek metrų kirminas turės įveikti, norėdamas sugraužti visus obuolius?

  1. 4
  2. 9
  3. 13
  4. 15
Paaiškinimas

Informatikoje siekiama ne šiaip surasti problemos sprendimą. Dažniausiai norima rasti sprendimą, reikalaujantį mažiausiai darbo. Tai kompiuterininkai vadina sprendinio optimizavimu. Be to, šiame uždavinyje kirminas šliaužia medžio – obels – šakomis. Medis čia vaizduoja išskirtinę diagramų rūšį, kur tam tikri jo taškai yra sujungti šakų atkarpomis. Tokios diagramos vadinamos grafais. Tad iš tiesų šis uždavinys yra trumpiausio kelio paieška grafe. Kelio, kuris prasideda kirmino pradinėje vietoje ir veda per visus obuolius.

Raktiniai žodžiai: trumpiausias kelias, grafas, medis, optimizacija.

Atsakymas

Teisingas atsakymas yra C – 13.

Kirminas turi pasiekti visus obuolius. A (4) ir B (9) nėra teisingi atsakymai, nes neįmanoma pasiekti visų obuolių, įveikiant tik 4 ar 9 šakų atkarpas. 4 arba 9 metrų ilgio keliai leistų kirminui pasiekti ir sugraužti tik vieną arba tik tris obuolius. Kirminui reikia nušliaužti 13 metrų, kad sugraužtų visus obuolius. Pirmiausia jis turi pasiekti artimiausią obuolį, tada – likusius tris. Atkreipkite dėmesį, kad nėra svarbu, kokia eile kirminas pasieks likusius obuolius. 15 metrų kelias (D) yra per ilgas.

 

 
Informacija atnaujinta 2017-11-13 16:52:39