2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Šuoliai lentoje

Taškai: 6

Lentoje yra 8 langeliai, sužymėti numeriais nuo 1 iki 8. Kiekvienam langeliui priskiriama viena iš trijų judėjimo taisyklių. Kiekvienos taisyklės pavyzdys pateikiamas žemiau:

1. Judėti į kairę

Pavyzdžiui, 2K reiškia, kad reikia judėti per du langelius į kairę:

2. Judėti į dešinę.

Pavyzdžiui, 3D reiškia judesį per tris langelius į dešinę:

3. Nejudėti

Taisyklė „0“ reiškia, kad iš šio langelio judėti nereikia.

Įsivaizduokite tokią lentą:

Iš kurio langelio reikia pradėti, kad judant pagal nurodytas taisykles būtų aplankytas kiekvienas langelis?

  1. 2
  2. 3
  3. 5
  4. Neįmanoma aplankyti kiekvieno langelio.
Paaiškinimas

Apie judesį „3D“ iš 2 į 5 langelį galime galvoti kaip apie rodyklę. Tokių rodyklių rinkinyje, kuris yra orientuotas grafas, ieškoma viršūnės arba aukštesnio lygio mazgo.

Laikytis rodyklių sekos labai svarbu, pavyzdžiui, tvarkant operacinės sistemos atmintį arba įgyvendinant Javos programavimo kalbos šiukšlių surinkimo mechanizmą, kad galėtų būti atlaisvinta nebenaudojama vieta atmintyje. Daug programinės įrangos klaidų gali būti rasta analizuojant problemines komandas, kai grįžtamaatgal iki jų aukštesnio lygio, pradinės priežasties.

Šiuo žaidimu gali būti modeliuojamas nukreipimo sakinys programavime. Nukreipimo sakinys nurodo, kad užuot vykdžiusiš eilės einančią gretimą komandą, reikia eiti į visai kitą programos vietą ir nuo tos vietos toliau vykdyti komandas. Šiame uždavinyje „programa“ – tai nukreipimo sakinių seka su vienintele baigimo komanda 4 langelyje.

Raktiniai žodžiai: Tiuringo juosta, rodyklė, kelias.

Atsakymas

Teisingas atsakymas: 3.

Analizuodami sprendinį nuo galinio taško (langelio su taisykle „0“), matome, kad tas taškas gali būti pasiektas iš 7 langelio, į kurį patenkama iš 6 langelio, o šis pasiekiamas iš 8 langelio, į kurį patenkama iš 5 langelio, šis pasiekiamas iš 2 langelio, į kurį ateinama iš 1 langelio, o pastarasis pasiekiamas iš 3 langelio.

Visa tai galima pavaizduoti grafu, kurio viršūnės sužymėtos langelių numeriais, o briaunos – taisyklėmis, kaip judėti tarp šių langelių. Šis grafas gali būti konstruojamas, pradedant bet kuria viršūne, ir baigiamas tada, kai surašyti visi langelių numeriai.