Bebro draugai (2014)
Taškai: 12
Devyni tvenkiniai sujungti vienas su kitu kanalais. Bebras Bronius gyvena centriniame tvenkinyje, o jo draugai kituose tvenkiniuose. Skaitmuo kiekviename tvenkinyje nurodo, kiek Broniaus draugų čia gyvena.
Bronius nusprendžia aplankyti draugus. Kiekvieną dieną jis gali perplaukti tik vieną kanalą, jungiantį du tvenkinius, todėl turi likti nakvoti šiame tvenkinyje, į kurį atplaukė. Kitą dieną jis gali tęsti kelionę iš šio tvenkinio.
Bronius nori aplankyti kiek galima daugiau draugų. Kiek skirtingų draugų gali aplankyti Bronius per keturias dienas, pradėdamas nuo namų? Jam nesvarbu, kur baigti kelionę.
A. 23 draugus
B. 24 draugus
C. 25 draugus
D. 30 draugų
Šioje užduotyje supažindinama su grafais. Tvenkiniai ir kanalai – tai grafas, kuriame ieškomas mums reikalingas kelias (kur gyvena daugiausia draugų), Tvenkiniai yra grafo viršūnės, o kanalai – grafo briaunos.
Mūsų ieškomas kelias turės turėti keturias viršūnes (tvenkinius). Kelio vertė gali būti nustatoma pagal viršūnių vertes. Sprendžiant uždavinį patogu taikyti medžio pavaizdavimą, kai keliai formuojami pagal visas galimas lankyti viršūnes ir taip einama žemyn medžio šakomis. Tai yra mūsų pateiktas antrasis sprendimo būdas. Grafo vaizdavimas medžiu yra labai svarbus informatikoje, medžio apdorojimui sukurta daugybė algoritmų ir programų.
Teisingas atsakymas: bebras gali aplankyti 25 draugus.
Paveiksle parodytas optimalus šio uždavinio sprendimo kelias:
Puikus uždavinio sprendimas gali būti pagrįstas keturių gretimų skaitmenų suma. Pastebėsime, kad grįždami atgal į tą patį tvenkinį tik gaištume laiką, nes sąlygoje reikalaujama aplankyti kuo daugiau skirtingų draugų. Vadinasi, galima suskaičiuoti 8 skirtingas sumas (žr. paveikslą) ir rasti didžiausią sumą:
Pateiktas klaidingas atsakymas „30 draugų” yra 4 didžiausių skaitmenų (tvenkinių) suma, kai neatsižvelgiama į juos jungiančius kanalus.