2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Stulpeliai ir eilutės

Taškai: 9

Duota žaidimo lenta, kurioje stovi figūros. Lentą bandoma pavaizduoti diagrama taip:

  • Kiekvienai figūrai lentoje nupiešiamas apskritimas.
  • Jei dvi figūros lentoje yra toje pačioje eilutėje ar tame pačiame stulpelyje, tarp jų diagramoje nubrėžiama linija (kitais atvejais linijos nebrėžiamos).

Figūros pažymėtos raidėmis tik tam, kad būtų lengviau patikrinti, ar diagrama teisinga.

Kuri diagrama nupiešta šiai lentai?

A B C D
 
Paaiškinimas

Informatikos moksle diagramos, kaip šiame uždavinyje, vaizduoja esminę uždavinio informaciją. Tokios diagramos vadinamos grafais. Diagramoje apskritimais vaizduojamos grafo viršūnės, o juos jungiančios atkarpos, – briaunomis.

Svarbu, ar grafo viršūnės yra sujungtos, ar ne. Tas pats grafas dažnai gali būti vaizduojamas skirtingais būdais, kaip pavaizduota anksčiau: atsakymas A ir paskutinio paaiškinimo paveikslėlio diagramos yra teisingos ir vaizduoja tą patį grafą.

Informatikos uždaviniuose grafai naudojami informacijos vaizdavimui ir priklauso nuo uždavinio. Pavyzdžiui, jei norite žinoti, ar balta figūra lentoje yra toje pačioje eilutėje ar stulpelyje kaip juoda, tada duomenų vaizdavimas grafu nėra geras būdas: viršūnės nevaizduojamos figūros spalvomis. Jei norime žinoti, ar lentoje liko pakankamai figūrų, kad laimėtume žaidimą, tai grafas „perkrautas“: turi sekti, kiek liko figūrų lentoje kiekvienu momentu ir nėra prasmės įrašyti, kuri figūra yra toje pačioje eilutėje ar langelyje kaip kitos figūros. Kita vertus, grafas –geras būdas pavaizduoti atsakymus į klausimą, koks yra minimalus figūrų skaičius, kurį turi pašalinti, kad nebūtų figūros tame pačiame eilutės stulpelyje, kaip bet kurios kitos figūros.

Teisingas duomenų vaizdavimo būdas yra vienas iš iššūkių programuotojui ar informatikos mokslininkui.

Raktiniai žodžiai: grafas, diagrama, vaizdavimas.

Atsakymas

Surašius figūroms raides, nesunku patikrinti, kad duotai lentai tinka diagrama A.
 
Lengviausia patikrinti, kad kitos trys diagramos netinka, pastebėjus, kad lentoje kiekviena figūra toje pačioje eilutėje sujungta su dviem kitomis figūromis ir tame pačiame stulpelyje su dar viena. Taigi, diagramoje kiekvienas apskritimas turi būti sujungtas su 3 kitais apskritimais. (Atsakyme C yra vienu apskritimu per daug.)
Diagrama B atrodo panaši į teisingą, bet kairiausi ir dešiniausi apskritimai sujungti tik su dviem kitais apskritimais, todėl ji negali būti teisinga. Norint ją ištaisyti, užtenka pridėti dvi linijas taip: