2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Salės grindys

Taškai: 12

Bebrė turi iškloti plytelėmis didžiulę pokylių salę. Viena kryptimi reikia pakloti 31 plytelę ir kita kryptimi – 16 plytelių. Bebrė nekuria įdomaus rašto. Ji nusprendžia, kad raštas turi susikurti savaime, pagal tam tikrų taisyklių seką.

Norėdama nustatyti, ar klojama plytelė turi būti balta ar juoda, Bebrė įvertina tris plyteles virš jos: tiesiai virš jos, iš viršaus į dešinę ir į kairę. Jei plytelė dedama prie salės krašto, tariama, kad šalia esančios plytelės yra baltos, ir laikomasi tų pačių taisyklių.

Taisyklės, nusakančios, kaip dėti apatinę baltą ar juodą plytelę, vaizduojamos taip:

Bebrė pradėjo nuo pirmos salės eilės, kurioje telpa 31 plytelė, padėdama vieną juodą plytelę eilės viduryje:

Pokylių salės šeimininkei nepatinka toks raštas. Ji nori, kad paskutinėje grindų rašto eilėje kaitaliotųsi po vieną baltą ir juodą plyteles iš eilės. Sukurkite naujas plytelių rašto taisykles, spustelėdami kvadratėlius žaliais kraštais. Nepamirškite, kad pradedate nuo juodos plytelės pirmos eilės viduryje!

Paaiškinimas

Šis žaidimas artimas matematiko Konvėjaus (J. H. Conway) sukurtam žaidimui „Gyvenimas“. Žaidimas remiasi fon Noimano mašina, kuri pati gali kurti savo kopijas. Konvėjaus žaidimo esmė – paprastų taisyklių taikymas gretimų ląstelių apgyvendinimui. Remiantis šiomis taisyklėmis, buvo sukurta daug sudėtingų automatų. Įrodyta, kad bet kokį skaičiavimą galima atlikti, naudojantis „Gyvenimo“ žaidimo idėjomis.

Šis uždavinys – tai tik „Gyvenimo“ dvimatė versija. Čia mokinys pats kuria savo taisykles ir jas išbando.

Daugiau apie „Gyvenimo“ žaidimą:

http://web.stanford.edu/~cdebs/GameOfLife/

https://en.wikipedia.org/wiki/Cellular_automaton
https://en.wikipedia.org/wiki/Conway's_Game_of_Life

Žaidimas „Gyvenimas“ aprašytas 1986 m. išleistoje V. Dagienės, G. Grigo, K. Augučio knygoje „Šimtas programavimo uždavinių“.

Įdomus atvejis, vadinamas „Taisyklė Nr. 90“.

https://en.wikipedia.org/wiki/Rule_90

Raktiniai žodžiai: taisyklė, žaidimas, automatas.

Atsakymas

Paveikslas vaizduoja vieną iš teisingų sprendimų, kuris grindžiamas XOR funkcija. Šiuo atveju, apatinės plytelės spalva priklauso nuo viršutinės eilutės vidurinės plytelės kaimynių. Jei kaimynės skirtingų spalvų, apatinė plytelė bus juoda.

Yra daug galimų sprendimų. Galima sugalvoti 256 plytelių rašto taisykles. Plytelės spalvą nulemia 8 skirtingi plytelių elementai po tris (JJJ, JJB, JBJ, JBB, BBJ, BJB, BJJ, BBB). Jei imsime tik vieną elementą, bus du pasirinkimai, jei du – 4, ir t.t. Taigi iš viso bus 28 (256) pasirinkimų. Teisingas sprendimas tik tas, kurio paskutinė eilė bus užpildoma pasikartojančiomis juodomis ir baltomis plytelėmis.

Interaktyvi užduotis