2014 2015 2016 2017 2018

Algoritmavimo menas

Taškai: 12

Rekursija – tai algoritmo kreipimasis į save patį. Gyvenimiškas rekursijos pavyzdys – du vienas prieš kitą sustatyti veidrodžiai. Jie vaizdą rekursiškai atspindi be galo daug kartų.
Štai rekursinio algoritmo pavyzdys:
Komanda Piešti kvadratą(x, y, s) nurodo kompiuteriui atlikti tokius veiksmus:
    Piešti kvadratą, kurio kraštinės ilgis yra s, o jo centro koordinatės yra x, y.
    Jei kvadrato kraštinė s ilgesnė negu 2 taškai, reikia atlikti veiksmus:
        Piešti kvadratą(x+s/2, y, s/2)   (piešti mažesnį kvadratą dešinėje);
        Piešti kvadratą(x-s/2, y, s/2)   (piešti mažesnį kvadratą kairėje).

Kuris iš žemiau pateiktų piešinių buvo sukurtas pagal komandą Piešti kvadratą?

A C
B D
Paaiškinimas

Daugelis programavimo kalbų turi rekursiją. Jų procedūros gali kreiptis pačios į save, kad galėtų išspręsti šiek tiek supaprastintą uždavinį. Tai gali būti naudinga dirbant su sudėtingomis duomenų struktūras, pavyzdžiui, struktūrinius sąrašus.
Vienas iš informatinio mąstymo rezultatų yra rekursiniai fraktalai. Tai sudėtingi ir įdomūs piešiniai, kuriems generuoti pakanka trumpų, tik kelių eilučių ilgio programų. Kai kurie tokiomis programomis sukurti piešiniai laikomi algoritmavimo menu. Štai keletas tokių piešinių:

Kocho kreivė                 Fraktalų medis Rekursiniai apskritimai

Skaitmeninėje grafikoje, naudojantis algoritmavimo menu arba fraktalų geometrija, sukuriami primenantys skaitmeniniai piešiniai. Skirtingai nuo klasikinės geometrijos, čia gaunami ne visai taisyklingi vaizdai, primenantys gamtos objektus: snaiges, medžius, lapus. Visa tai gali būti naudojama kompiuteriniuose modeliuose, kuriant dinaminius ir tikroviškus objektus.

Reikšminiai žodžiai: fraktalai, rekursija, algoritmai

Atsakymas

A – neteisingas. Kvadratai nupiešti, bet nėra kvadratų kairėje ir dešinėje.

B – teisingas. Yra vieno didelio kvadrato piešinys ir ant kiekvieno kvadrato šoninių kraštinių po vieną dvigubai mažesnį kvadratą.

C – neteisingas. Yra vieno didelio kvadrato piešinys, bet mažesni kvadratai yra ant didesniųjų kvadratų viršutinių ir apatinių kraštinių, o ne ant šoninių.

D – neteisingas. Yra vieno didelio kvadrato piešinys, bet mažesni kvadratai yra ant kiekvienos didesniojo kvadrato kraštinės, ne tik ant šoninių.