BEBRO konkurso užduotys 2017

 

Knygų mainų klubas

Taškai: 12

Diagrama rodo 7 knygų mainų klubo narių ryšius (nurodyti narių vardai ir amžius). Klubo nariai laikosi šių taisyklių: gaunate neskaitytą knygą, ją perskaitote, tada perduodate jauniausiam draugui, kuris dar šios knygos neskaitęs. Jei visi draugai jau skaitė šią knygą, grąžinate ją tam, kas davė.

Benas ką tik perskaitė knygą ir nori ją perduoti draugams.

Kas bus paskutinis knygos skaitytojas?

  1. Tomas
  2. Viltė
  3. Joris
  4. Kajus
Paaiškinimas

Daugybė duomenų, su kuriais dirba informatikai, yra tarpusavyje susiję. Pavyzdžiui, apie mėgstamą socialinį tinklą galime galvoti kaip apie aibę elementų (žmonių) ir ryšių (draugystės santykių). Analogiškai galime galvoti apie kelių tinklą – kaip apie aibę elementų (miestų) ir aibę ryšių (kelių). Taip pat ir maisto grandinę galime laikyti aibe elementų (gyvųjų būtybių) ir ryšių (plėšrūno–grobio santykių). Taigi gausybė realaus pasaulio sistemų gali būti suprantamos kaip tinklai.

Tinklams vaizduoti informatikai taiko grafus. Tai duomenų struktūros, vaizduojamos taškais (viršūnėmis) ir juos jungiančiomis linijomis (briaunomis). Grafams analizuoti sukurta daugybė skirtingų algoritmų. Vienas žinomiausių – paieškos gilyn algoritmas. Juo vykdoma paieška grafe arba nustatoma tam tikra tvarka, kaip keliauti grafu. Kartais labai svarbu žinoti, kiek grafe yra jungiųjų komponentų (jungusis komponentas yra aibė taškų (grafo viršūnių), kurie visi turi būti pasiekiami grafo briaunomis). Vykdydami paiešką gilyn iš vienos viršūnės, sužinome, kurias viršūnes iš jos pasiekiame. Tą patį turime kartoti ir su visomis kitomis viršūnėmis.

Šiame uždavinyje turime sekti knygos kelią draugų tinkle. Jis labai artimas paieškos gilyn tvarkai.

Plačiau galima paskaityti:

http://inf.knyga.nmakademija.lt/07_graf%C5%B3_pagrindai.html

https://en.wikipedia.org/wiki/Depth-first_search

Raktiniai žodžiai: socialiniai tinklai, paieška gilyn.

Atsakymas

Teisingas atsakymas yra Kajus.

Benas duoda knygą Tadui, Tadas – Emai, Ema – Joriui. Joris perduoda knygą Tomui, o šis grąžina ją Joriui. Joris grąžina knygą Emai, o Ema duoda Viltei. Viltė knygą grąžina Emai, o Ema ją grąžina Tadui. Tadas duoda knygą Kajui.

 

 
Informacija atnaujinta 2017-11-13 16:52:39
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.