Pėdavimas (2014)
Taškai: 12
Tik pažiūrėkite – bebrai žemėje išpėdavo medžius!
Šis raštas buvo piešiamas laikantis tam tikrų taisyklių. 1-ojo lygio medžiui išpėduoti taikomas štai toks algoritmas:
|
Ženk 1 žingsnį į priekį ir prispausk pėdutę. Ženk 1 žingsnį atgal. |
 |
| 1-ojo lygio medis |
Kas suprato, kaip išpėduoti 1-ojo lygio medį, nesunkiai supras, kaip išpėduoti 2-ojo lygio medį:
|
Ženk 2 žingsnius į priekį ir kiekvienu žingsniu prispausk pėdutę. Pasisuk į dešinę ir išpėduok 1-ojo lygio medį. Pasisuk į kairę ir išpėduok 1-ojo lygio medį. Ženk 2 žingsnius atgal. |
 |
| 2-ojo lygio medis |
3-ojo lygio medis pėduojamas naudojant 2-ojo lygio medžio algoritmą:
|
Ženk 3 žingsnius į priekį ir kiekvienu žingsniu prispausk pėdutę. Pasisuk į dešinę ir išpėduok 2-ojo lygio medį. Pasisuk į kairę ir išpėduok 2-ojo lygio medį. Ženk 3 žingsnius atgal. |
 |
| 3-ojo lygio medis |
Kaip atrodys 4-ojo lygio medis, sukurtas pagal pateiktą algoritmą?
| A. | B. |
 |
 |
| C. | D. |
 |
 |
Ši (pėdavimo) schema paprasta ir aiški. Ji galioja bet kokio lygio medžiui. Jeigu norėtume išpėduoti x-ojo lygio medį, reiktų paeiti x žingsnių į priekį ir išpėduoti x-1 lygio medį. Išpėduojant x-1 lygio medį reikėtų paeiti x-1 žingsnį į priekį ir išpėduoti x-2 lygio medį. Ir taip toliau, kol pasieksime 1-ojo lygio medį. Reikia tik prisiminti, kaip gauti x lygio medį naudojant x-1 lygio medžius ir kaip gaunamas1-ojo lygio medis.
Informatikoje toks procesas, kai funkcija kartojama su mažesniais parametrais, vadinamas rekursija.
Rekursiniai algoritmai paprastai būna labai elegantiški, kita vertus, jie gali būti labai painūs ir neefektyvūs.
Ši užduotis yra nuostabiųjų fraktalų pavyzdys.
Teisingas atsakymas – A.
- Šis medis yra pėduojamas paeinant 4 žingsnius į priekį ir pėduojant du 3-čio lygio medžius.
- Šis medis pėduojamas paeinant 4 žingsnius į priekį ir pėduojant tris 3-čio lygio medžius. Pradiniuose raštuose naudojama po du žemesnio lygio medžius.
- Šis medis yra pėduojamas paeinant 3 žingsnius į priekį ir pėduojant du 3-čio lygio medžius. Pradiniuose raštuose į priekį einama tiek žingsnių, kurio lygio medis pėduojamas.
- Medis neužbaigtas – viršūnėse nėra 1-mo lygio medžio! Raštas visuomet turi baigtis 1-mo lygio medžiu.