BEBRO konkurso užduotys 2018

 

Bebrų ežeras

Taškai: 6

Bebrai gyvena slėnyje, apsuptame kalnų. Tame slėnyje yra ežeras. Aplink ežerą yra miško arba uolų plotai.

Kiekvieną dieną bebrai užtvindo visus miško plotus, esančius šalia ežero arba jau apsemtų plotų.

Pavyzdžiui, po vienos dienos trys plotai bus apsemti. Uolų plotai nėra apsemiami.

Po kelių dienų visi miško plotai bus užtvindyti? Įveskite dienų skaičių.

Paaiškinimas

Kompiuterių mokslininkai tiria skirtingus algoritmų tipus. Algoritmas – veiksmų seka, vykdoma norint atlikti tam tikrą užduotį ar išspręsti problemą. Ši užduotis parodo bangos algoritmą (angl. wavefront algorithm), naudojamą peržiūrėti  sritį, padalinti į laukelius.

Ši peržiūra naudoja paieškos į plotį (angl. breadth-first search, BFS) metodą. BFS paieška prasideda laukelyje, vadinamame šaknimi. Kitu žingsniu aplankomos visos jos kaimynės, po to kaimynių kaimynės ir t.t., kol randamas ieškomas tikslas arba kol aplankomi visi laukeliai. Šioje užduotyje laukeliai atitinka plotus, o jų lankymas – miško plotų užliejimą.

Kai BFS algoritmas atliekamas kruopščiai, kiekvienas laukelis aplankomas tik vieną kartą. Tai atliekama organizuotai. Iš tiesų, kaip matyti iš pateikto sprendimo, laukeliai gali būti sunumeruojami, nes yra aplankyti. Šie skaičiai nurodo, kiek visi laukeliai nutolę nuo šaknies (šiuo atveju, ežero). Tai reiškia, kad BFS algoritmas gali būti naudojamas, siekiant rasti trumpiausią kelią nuo šaknies iki visų kitų laukelių.

https://lt.wikipedia.org/wiki/Paie%C5%A1ka_%C4%AF_plot%C4%AF

Raktiniai žodžiai: bangos algoritmas, paieška į plotį.

Atsakymas

Teisingas atsakymas: po 6 dienų. Skaičiai paveikslėlyje nurodo miško plotus, kurie bus užlieti po kelių dienų. Miško plotai, esantys šalia ežero, pažymėti numeriu 1. tada visi dar nepažymėti miško plotai, esantys šalia pažymėtųjų, pažymimi numeriu 2. Šis procesas tęsiamas tol, kol sunumeruojami visi miško plotai. Kaip matome paveikslėlyje, paskutinis miško plotas bus užlietas po 6 dienų.

Interaktyvi užduotis

 

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