2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Savanaudės voverės

Taškai: 12

Medyje yra penkios viena virš kitos išsidėsčiusios drevės, kuriose gyvena 16 savanaudžių voverių. Kasdien kiekviena voverė apžiūri, kiek turi kaimynų drevėje, kurioje gyvena, viena dreve virš (jei yra) ir viena dreve žemiau (jei yra). Tada nustato, kurioje iš šių drevių yra mažiausias kaimynų skaičius. Naktį kiekviena voverė persikelia į atrinktą drevę (arba lieka savoje), kurioje kaimynų skaičius mažiausias. Jei tokių drevių ne viena, voverė pirmenybę teikia savo drevei, tada viršiau esančiai drevei ir galiausiai – žemiau esančiai drevei.

Pavyzdžiui, voverės drevėse gyvena šitaip: 5, 0, 0, 4, 7 (pradedant nuo viršaus ir einant žemyn). Rytoj visos 5 viršutiniojo aukšto voverės apsigyvens viena dreve žemiau (0 kaimynų yra geriau nei 4), 7 voverės iš apatinės drevės persikels viena dreve aukščiau (4 kaimynai yra geriau negu 6) ir 4 voverės iš antrosios drevės nuo apačios persikels dreve aukščiau (0 kaimynų yra geriau nei 3).

Tarkime, kad voverės drevėse gyvena šitaip:

Kiek dienų reikės, kad visos voverės atsidurtų vienoje ir toje pačioje drevėje?


Atsakymų variantai:

A) 2
B) 3
C) 4
D) Tai neįmanoma

Paaiškinimas

Tai skruzdžių kolonijos elgseną imituojantis uždavinys. Šio algoritmo idėja remiasi tuo, kad bet kas gali išspręsti problemas net naudodamas paprastus įrenginius, jei tų įrenginių yra labai daug. Pavyzdžiui, skruzdės juda pagal elementarias taisykles ir nepriklausomai viena nuo kitos. Tačiau kai skruzdžių daug, jos gali padaryti įspūdingus dalykus, pavyzdžiui, sulipdyti skruzdėlynus, surasti optimalų kelią grafe, išspręsti keliaujančio pirklio uždavinį ar nuskabyti lapus.
Šiame uždavinyje voverių drevių pasirinkimas pagrįstas paprastomis taisyklėmis. Tačiau čia jų elgesys toli gražu ne sumanus. Jos norėtų gyventi kuo erdviau, tačiau paprastai jos susigrūda į vieną drevę. Taigi šis uždavinys gana pamokantis: skruzdžių kolonijos algoritmą reikia taikyti apdairiai, pamatuotai, atsiminti, kad kartais geriau veikti bendradarbiaujant, o ne būti savanaudiškam.

Atsakymas

B) 3