BEBRO konkurso užduotys 2017

 

Bebrų sodas

Taškai: 6

Ema žaidžia bebrų sode – keliauja kelmų tinkleliu. Nuo kiekvieno kelmo ji mato keturis gretimus kelmus (arba mažiau, jei ji stovi ant kraštinio kelmo) ir laikosi šių taisyklių:

1. Jei yra kelmas vienu lygiu aukštesnis už dabartinį, lipa ant to kelmo.
2. Jei tokio kelmo nėra, žengia ant tokio pat aukščio kelmo, bet tik tada, jei ten dar nėra buvusi.
3. Jei nėra kur judėti, sustoja.

Kelmų lygiai (aukščiai) ir išdėstymas rodomi pateiktoje schemoje.


Ema pradeda nuo kelmo, kuris yra 1 lygiu aukščiau žemės. Kaip aukštai ji gali užlipti, laikydamasi nurodytų taisyklių? Spustelėkite kelmus iš eilės, atkartodami Emos žingsnius.

Paaiškinimas

Matome, kad egzistuoja kelias iki 9 lygio kelmo dešiniame viršutiniame kampe, tačiau bebrė Ema per daug nesivargina ir neieško sprendimų į priekį. Informatikoje dažnai rašome programas, kurios ieško sprendinio pagal panašų algoritmą – vienas žingsnis vienu metu. Tokį algoritmą vadiname „godžiuoju“, nes pagal jį tarsi iš godumo griebiamasi varianto, kuris atrodo geriausias šiuo metu (vykdant kiekvieną žingsnį), tačiau gali nebūti pats geriausias, siekiant galutinio tikslo. Todėl šiuo algoritmu rasti sprendiniai ne visada optimalūs.

Kodėl gi taikome šį algoritmą? Kodėl „neliepus“ programoms visada žiūrėti atidžiau ir bandyti įvertinti visus žingsnius? Galimų sprendinių, kuriuos reikia ištirti, skaičius gali būti toks milžiniškas, kad joks kompiuteris negalėtų jų visų patikrinti, todėl dažnai tenka pasirinkti sprendinį, kuris yra „gana geras“.

Raktiniai žodžiai: kopimas į kalną, godžioji paieška, godusis algoritmas, komandų vykdymas.

Atsakymas

Teisingas atsakymas:

Taip, deja! Ema daro tik vieną žingsnį vienu metu, neplanuodama savo žingsnių į priekį.

Interaktyvi užduotis

 

 
Informacija atnaujinta 2017-11-13 16:52:39