2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Araboto kelias

Taškai: 12

Arabotas yra popieriaus lape vaikštantis robotas. Jis visada eina lape nupiešta juoda linija. Linijoje įrašyta raidė rodo, kur artimiausioje linijų sankirtoje  reikia sukti: į kairę (K) ar į dešinę (D). Kai kurios linijos jau sužymėtos raidėmis, kitas dar reikia sužymėti. Jonukas paleidžia Arabotą iš pradinės vietos A, B arba C.

Arabotui gana dažnai reikia įsikrauti, todėl, kur jis bepradėtų savo kelią, baigti jį turi įkrovimo stotyje ( ). Jei Arabotas baigia kelią vietose, pažymėtose A, B ar C, tai nežino, ką toliau daryti, ir išsijungia.

Sužymėk linijas taip, kad Arabotas pasiektų įkrovimo stotį, pradėjęs bet kurioje vietoje.

Paaiškinimas

Šis uždavinys – tai skirtingų kelių (iš A į , iš B į  ir iš C į ) kodavimo į bendrą sužymėtą struktūrą (šiuo atveju – grafą) uždavinys. Informatikoje tokia struktūra vadinama duomenų struktūra. Einant keliu (pvz., iš A į ), kiekvienas Araboto žingsnis – tai komandų skaitymas ir interpretavimas: kur pasukti kitoje sankirtoje, o po kiekvieno posūkio – naujos komandos vykdymas. Tai panašu į kompiuterio aparatinės įrangos darbą elektronikos lygmenyje.

Tokie galvosūkiai kelia nemažai įdomių matematinių klausimų apie struktūros žymėjimo sudėtingumą. Dalis šių klausimų dar neturi atsakymų, todėl jie yra informatikos mokslininkų algoritmų ir skaičiavimų srities tyrimų objektas. Panašūs galvosūkiai taikomi bioinformatikoje, medicinoje.

Raktiniai žodžiai: dinaminis programavimas, grįžties metodas.

Atsakymas

Teisingas atsakymas yra:

Dviejose kairėje esančiose linijose reikia nurodyti, kad Arabotas tęstų kelią, už sankirtos pasukdamas į dešinę. Todėl viršutinę liniją reikia pažymėti „K“, o apatinę – „D“.

Dešiniau esančiame trikampyje vienintelis būdas priartėti prie įkrovimo stoties – tai judėti apatine linija į dešinę, nes kelias viršutine linija grąžintų robotą atgal į B. Taigi vidurinis stačiakampis žymimas „D“ apatinėje linijoje ir „D“ viršutinėje linijoje. Reikia numatyti, kad stačiakampio kairėje esančia kraštine robotas nenueitų į vietą C. Todėl linija žymima „D“.