2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Labirintas su rodyklėmis

Taškai: 9

Žaidimo tikslas – padėti jaustukui  grįžti namo. Kai jaustukas yra langelyje su rodykle, jis turi judėti į gretimą langelį rodyklės rodoma kryptimi. Jaustukas gali pradėti kelią eidamas į vieną iš žalių langelių.

Tačiau judant šiame paveiksle nurodytomis kryptimis, neįmanoma pasiekti langelio su namu. Pakeiskite VIENOS rodyklės kryptį taip, kad būtų įmanoma pasiekti langelį su namu.

Norėdami pakeisti rodyklės kryptį, spustelėkite rodyklę keletą kartų, kol atsiras tinkama kryptis.

 

Paaiškinimas

Uždaviniui išspręsti reikia suprasti, kaip elgtis labirinte ir ką reiškia rodyklės.

Net jei rasti teisingą kelią paprasta, žymiai sudėtingiau įrodyti, kad nėra kito sprendinio, . Šiuo atveju, grįžimų metodas efektyviai patikrina visas galimas judėjimo krypčių kombinacijas. Galima įsivaizduoti, kad visi galimi labirinto keliai sudaro medį, kurio tik viena šaka veda tikslo link. Grįžimų metodu tikrinami visi galimi sprendiniai, net ir tie, kurie yra neteisingi.

Raktiniai žodžiai: labirintas, teisingo kelio paieška, grįžimų metodas.

Atsakymas

Rodyklė, kurios kryptį reikia pakeisti, pažymėta raudonai. Jaustuko kelias paryškintas: A1 (pradžia) –A2 – B2 – B3 – C3 – C4 (tikslas).

Įrodymas, kad šis sprendinys vienintelis, pateikiamas žemiau.

Pradėsime nuo tikslo langelio C4 ir judėsime atgal. Į C3 langelį galima patekti dviem būdais: iš langelio B3 arba iš langelio C2.

C2 langelio rodyklė nerodo į tikslo langelį, todėl tam, kad sprendinys būtų teisingas, šios rodyklės kryptį reikia pakeisti. Kadangi nei viena iš kaimyninių langelių rodyklių į C2 langelį nerodo, reikia keisti dar vienos rodyklės kryptį. O pagal sąlygą galima keisti tik vienos rodyklės kryptį. Taigi tikslo langelis C4 gali būti pasiektas tik iš langelio C3.

Nėra nei vienos rodyklės, kuri rodytų į C3 langelį, todėl turime keisti rodyklės B3 arba C2 langelyje kryptį. Rodyklės, rodančios į C2 langelį taip pat nėra, patekti į C2 langelį per B3 langelį neįmanoma, nekeičiant dar vienos rodyklės krypties.

Langelis B3 pasiekiamas iš pradinio langelio, nekeičiant rodyklės krypčių: A2 – B2 – B3 . Taigi keliui labirinte rasti reikia pakeisti tik vieną rodyklę B3 langelyje.

Interaktyvi užduotis