Takie pooenie przyjmujemy jako niezmienni!
procedur.
- Po narysowaniu dywanu ABFA przesuwamy wia do punktu C i obracani
w kierunku punktu E. W dwch pozostaych wierzchokach (C i E) czynim
podobnie.
Oto zapowiedziany program.
Przykad 3.6. Rysowanie dywanu Sierpiskiego.
Procedura gwna uwzgldniajca czynnoci organizacyjne:
TO DywanSierpiskiego :n :a
CS HT
{pocztkowe ustawienie wia}
Hop -:a / 2 (-:a / 3)
FILLPATTERN [#ff #ff #ff #ff #ff #ff #ff #ff]
RT 30
RysujDywanSierpiskiego :n :a
LT 30
END
Procedura rekurencyjna:
TO RysujDywanSierpiskiego :n :a
IF -ii = 0 [Trjkt :a STOP]
REPEAT 3 [RysujDywanSierpiskiego
ZamalujTrjkt :a
END
Pozostae procedury:
TO Trjkt :a
REPEAT 3 [FD :a RT 120]
END
:n -
:a / 2 FD :a RT
3.7. Struktury danych - listy
93
TO Zamaluj Trj kt :a
PU RT 30 FD :a / 2 PD
FILL
PU BK :a / 2 LT 30 PD
END
Uwaga: Zestaw procedur rysujcych trjktny dywan Sierpiskiego znajduje si na dys- [~T1
kietce w pliku DYWAN.LOG umieszczonym w kartotece R0ZDZ3. _
Przykady innych rysunkw definiowanych rekurencyjnie podano w zadaniach
3.12 - 3.14.
3.7. Struktury danych - listy
Opisywane dotd procedury, za pomoc ktrych sporzdzalimy rysunki, albo
nie miay parametrw, albo jako dane najczciej przyjmoway liczby (oglniej -
wartoci wyrae arytmetycznych). Dane liczbowe okrelay na przykad dugoci
bokw prostokta, wielkoci ktw obrotu wia podczas rysowania spirali lub
stopie rekurencyjnie definiowanego dywanu Sierpiskiego.
W jzyku Logo mog wystpowa nie tylko dane proste, np. liczby, ale rwnie
dane zoone, czyli struktury danych, reprezentowane przez listy. Stosowalimy
ju procedury z parametrami zapisywanymi jako listy. Byy to listy liczb, np.
SETCURSOR [30 13], Zamaluj [#40 #40 #f f 2 2 2 #f f #40], lub listy sw,
np. PR [TRZY PROSTOKTY] (zob. p. 3.4 i 3.5). W tym punkcie listy omwimy
dokadniej. Rozpocznijmy od definicji.
Lista w jzyku Logo jest ujtym w nawiasy kwadratowe cigiem sw lub list;
cig ten moe by pusty. Jest to definicja rekurencyjna. Lista pusta, tj. [ ],
ma zero elementw. Lista niepusta ma co najmniej jeden element. Moe nim by
sowo lub lista.
Sowem w jzyku Logo okrela si dowolny cig znakw zakoczony separa-
torem (zob. p. 3.3). Std wynika, e - poza tradycyjnymi sowami zaczerpnitymi
z jzyka naturalnego - sowami w jzyku Logo s rwnie pojedyncze znaki (np.:
=, /), liczby (np.: 3, i20), a take cigi liter i cyfr, np. Al, 2b itp.
Oto przykady list, ktre wczeniej wystpoway w instrukcjach REPEAT (zob.
p. 3.2 i 3.3).
[FD 35 RT 90 FD 10 RT 90]
[REPEAT 3 [FD 30 RT 120] RT 36]
[FD :Bok RT 360 / :n]
94
3. Grafika wia
i
3.7.1. Przegldanie listy danych
Listy mona przeglda. Tablica 3.5 zawiera przykadowe wywoania najwaniej-
szych jednoargumentowych funkcji pierwotnych sucych do tego celu. Warto-
ciami tych funkcji s albo sowa, albo listy.
Tablica
i.5. Funkcje przegldania listy
Wywoanie funkcji
Wynik
Warto funkcji
FIRST [a b c]
a
Pierwszy element listy
FIRST [[a] b c]
[a]
BF [a b c]
[b c]
Lista bez pierwszego elementu
BF [a]
[ ]
LAST [a b c]
c
Ostatni element listy
BL [a b c]
[a b]
Lista bez ostatniego elementu
Wymienione funkcje wykorzystamy do rozwizania nastpujcego zadania:
Napisa procedur sterujc ruchem wia zgodnie z danymi z listy L. Liczby
w licie danych L oznaczaj ruchy wia zakodowane w nastpujcy sposb:
liczba 1 oznacza ruch do przodu o 50 jednostek, liczba 2 - ruch po okrgu o pro
mieniu 30 jednostek, kada inna liczba - obrt w prawo o 10 stopni.
Algorytm 3.4. Odtworzenie zakodowanych ruchw wia.
1. Jeli L jest list pust, to zakocz algorytm.
2. Jeli pierwszy element listy L jest rwny 1, to wykonaj ruch wia do
przodu o 50 jednostek i przejd do kroku 5.
3. Jeli pierwszy element listy L jest rwny 2, to wykonaj ruch wia p:
okrgu o promieniu 30 jednostek i przejd do kroku 5.
4. Wykonaj obrt wia o 10 stopni w prawo.
5. Wykonaj ten algorytm od pocztku dla listy L bez pierwszego elementu.
Procedur realizujc algorytm 3.4 nazwiemy Ruchwia. Wykorzystam
w niej sprawdzanie, za pomoc operatora = , czy lista danych jest pusta.
TO Ruchwia :L
IF :L = [ ] [STOP] ?
IF (FIRST :L) = 1 [FD 50] ELSE
[IF (FIRST :L) = 2 [Okrg 30] ELSE [RT 10]]
Ruchwia BF :L
END
Nawiasy w zapisach warunkw ustalaj kolejno dziaa (zob. p. 3.4.1) - iu
pierw jest brany pierwszy element z listy L, a pniej porwnywany z liczb.
3.7. Struktury danych - listy
95
,
Sposoby rysowania okrgw o zadanym promieniu s omwione w rozwizaniu
zad. 3.6 (zob. El-II). Procedura rysujca okrg o promieniu r moe mie nast-
pujc posta:
TO Okrg :r
RT 5
REPEAT 36 [FD 3.14 * :r / 18 RT 10]
LT 5
END
Dziaanie procedury Ruchwia mona przetestowa wywoujc j na przy-
kad tak:
CS ST
Ruchwia [1213112323 1]
Uwaga: Procedury Ruchwia i Okrg znajduj si na dyskietce w pliku RUCH-Z.LOG
umieszczonym w kartotece R0ZDZ3.
Z powyszego zadania wynika oglny schemat rekurencyjnego przeglda-
nia list (podobny do schematu procedury rekurencyjnej - zob. p. 3.6):
1. Jeli lista jest pusta, to zakocz algorytm.
2. Wykonaj jakie czynnoci (bez rekurencji) dla pierwszego elementu listy.
3. Wykonaj ten sam algorytm (czyli rekurencja) dla listy danych bez pierw-
szego elementu.
W powyszym schemacie zwroty: pierwszego i bez pierwszego mona zastpi
odpowiednio przez ostatniego i bez ostatniego.
3.7.2. Pamitanie informacji
Wprowadzimy teraz now instrukcj, ktra pozwala upraszcza zapis niektrych
algorytmw.
W drugim i w trzecim kroku algorytmu 3.4 jest sprawdzany pierwszy element
listy L otrzymywany za pomoc funkcji FIRST. Jeli nie jest on rwny 1, to po raz
drugi jest liczona ta sama warto funkcji FIRST. Moemy nieco zmodyfikowa
realizacj algorytmu 3.4 - raz policzy i zapamita pierwszy element listy L,
nastpnie dwukrotnie z niego skorzysta.
W jzykach programowania do pamitania informacji uywa si zmien-