2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Roboto kelias

Taškai: 12

Robotas gali keliauti grindų tinklu, žingsniuodamas šiaurės arba rytų kryptimis. Diagramomis (pavaizduotomis žemiau) aprašomi galimi roboto judesiai. Pavyzdžiui, ši diagrama nurodo, kad roboto kelias yra žingsnių seka šiaurės (N) ir rytų (E) kryptimis.

Galimi keliai konstruojami pagal diagramą tokiu būdu:

  • rodyklė N nurodo, kad robotas turi žengti žingsnį šiaurės kryptimi;
  • rodyklė E nurodo, kad robotas turi žengti žingsnį rytų kryptimi;
  • nuspalvintas apskritimas nurodo pradinį tašką;
  • dvigubas apskritimas nurodo galimą galutinį tašką;
  • jei robotas yra dvigubame apskritime, iškurio išeina rodyklė, jis gali judėti toliau.

Kelionę pagal šią diagramą robotas pradeda žingsniu šiaurės kryptimi, tada kelis kartus gali žengti rytų ir šiaurės kryptimis ir sustoti (po paskutinio žingsnio šiaurės kryptimi). Taigi NENENEN, NEN ir NENENENENENEN yra galimi keliai, bet NENNE, NENE arba ENE tokie nėra.

Robotas keliauja pagal šią diagramą. Užbaikite teiginius, pasirinkdami teisingą variantą.

1. Visi keliai ___________________

  • privalo baigtis E
  • tik tam tikrais atvejais baigiasi E
  • negali baigtis E

2.Kelias - _________________ yra negalimas

  • ENNE
  • ENEENE
  • NEENENNE

3. Bet kuriame kelyje skirtumas tarp atliktų E ir N žingsnių yra _________________.

  • lygus 2
  • lygus 3
  • daugiausiai 2
Paaiškinimas

Šios diagramos yra baigtinio būsenos automato (dar vadinamo baigtine būsenos mašina, baigtiniu automatu, būsenos mašina) diagramos. Šiuo automatu informatikoje aprašomos sistemos, kurios gali būti baigtinėje aibėje būsenų ir keisti būsenas. kai atliekamas baigtinis veiksmų skaičius (nauja būsena priklauso tik nuo dabartinės būsenos ir atlikto veiksmo). Dažniausiai taip pat būna nurodomos sistemos pradinė būsena ir baigtinės būsenos.

Baigtinio automato būsenų diagramoje galimos būsenos reprezentuojamos apskritimais (pradinė būsena vaizduojama spalvotu apskritimu, galutinė – dvigubu apskritimu), būsenų kaita atvaizduojama rodyklėmis, o veiksmai įvardijami kokios nors abėcėlės raidėmis (šiame pavyzdyje N ir E).

Būsenos taip pat gali būti sunumeruotos arba kaip nors pavadintos, kad būtų lengviau jas atskirti:

Kitaip tariant, šioje sistemoje robotas gali turėti 5 būsenas:

  1. Robotas dar nežengė jokio žingsnio.
  2. Robotas kelis kartus įvykdė N ir E žingsnius paeiliui, pradėdamas nuo N.
  3. Robotas kelis kartus įvykdė E ir N žingsnius paeiliui, pradėdamas nuo E.
  4. Robotas paeiliui atliko lygiai 2 N žingsnius , o likusioje kelio dalyje atliko N ir E žingsnius.
  5. Robotas paeiliui atliko lygiai 2 E žingsnius , o likusioje kelio dalyje atliko N ir E žingsnius.

Sistemos elgsena aprašoma baigtiniui automatui suprantama kalba, t. y. aibe sekų, kurios gali būti sudaromos keliaujant diagramos rodyklėmis. Pavyzdžiui, automato suprantama kalba šiame pavyzdyje aprašo visus galimus roboto kelius.

Raktiniai žodžiai: baigtinis automatas, kalba, kelias.

Atsakymas

Akivaizdu, kad bet kuriam keliuibūdingos šios savybės:

  • jo pradžia yra E arba N (kadangi iš užpildyto apskritimo išeina 2 rodyklės – E ir N);
  • jo pabaiga yra E (kadangi į dvigubą apskritimą galima patekti tik E rodyklėmis);
  • N visada eina po E, išskyrus vieną kartą;
  • visada yra pora vienos krypties žingsnių, einančių vienas po kito (EE arba NN)

Taigi teisingi atsakymai yra šie:

  1. Visi keliai baigiasi E.
  2. Kelias NEENENNE yra negalimas, nes po dviejų iš eilės einančių E rodyklių, pasiekiamas dvigubas apskritimas, o iš jo galima judėti tik pasikartojančiais N ir E žingsniais.
  3. Bet kuriame kelyje skirtumas tarp atliktų E ir N žingsnių yra daugiausiai 2. Tai galima suprasti iš aukščiau aprašytų kelio savybių. Kraštutiniu atveju kelias prasideda ir baigiasi E bei turi EE porą, t. y. atitinka šabloną E…NEEN…E, kur taškai vaizduoja vieną ar kelis (arba nė vieno) pasikartojančius NE.
Interaktyvi užduotis