Tiltai (2014)

Taškai: 9

Tarp salų ežere nutiesti tiltai. Kaip parodyta paveiksle, vieni tiltai yra viešieji (ištisinė linija), kiti yra mokami (brūkšninė linija).

Sandra nori iš savo namų nukeliauti į miškingąją salą. Ji ieško kelio, kuriame būtų mažiausiai tiltų. Tačiau Sandra turi nedaug pinigų ir gali užmokėti ne daugiau kaip už du mokamus tiltus.

Kiek mažiausiai tiltų reikės Sandrai pereiti, jei mokamų tiltų gali būti ne daugiau kaip du?

A. 4

B. 5

C. 6

D. 7

Paaiškinimas

Šis paveikslas – tai grafo modelis. Prašoma surasti kelią iš vienos viršūnės (Sandros namų) į kitą (mišką). Apsiribojama tam tikru mokamų tiltų skaičiumi ir ieškoma pigiausio galimo kelio.

Yra daug būdų išspręsti tokius uždavinius; vienas įdomiausių ir iššūkius keliančių informatikos aspektų – galimybė susidurti su gerai žinomų problemų variantais.

Atsakymas

Teisingas atsakymas – B: reikės pereiti 5 tiltus.

Iš Sandros namų nėra nei vieno kelio, kuris turėtų mažiau negu 4 tiltus. Visi keliai, kurie turi 4 tiltus, apima 3 mokamus tiltus. Yra keli keliai, kurie apima 5 tiltus, iš kurių 2 yra mokami.

 

 
Informacija atnaujinta 2015-10-16 15:36:59
Informuojame, kad nuo 2019 m. rugsėjo 2 d. Ugdymo plėtotės centro veiklas vykdo Nacionalinė švietimo agentūra. Ši interneto svetainė toliau nebus atnaujinama, tačiau visa informacija išliks aktyvi ir prieinama tol, kol bus perkelta į Nacionalinės švietimo agentūros interneto svetainę www.nsa.smm.lt.