Logia 2002/03 - Etap III

Zadanie 1

Zdefiniuj procedurę GWIAZDY :kod rysującą gwiazdozbiór składający się z gwiazd. Każda gwiazda składa się z pęku ramion-odcinków o tej samej długości, równomiernie rozmieszczonych wokół środka gwiazdy.

Każda gwiazda może posiadać własne gwiazdy-satelity - są one rysowane na przedłużeniu każdego ramienia gwiazdy-matki. Długość ramienia gwiazdy-satelity równa jest jednej trzeciej długości ramienia gwiazdy-matki. Odległości środków gwiazdy-matki i gwiazdy-satelity są równe podwójnej długości ramienia gwiazdy-matki.Gwiazdy-satelity mogą posiadać swoje własne gwiazdy-satelity, itd.

Centralna gwiazda układu jest rysowana na środku ekranu. Jej ramiona mają losową długość, nie mniejszą niż 20 i nie większą niż 80.

Dana :kod może być liczbą lub listą:

• gdy jest liczbą - reprezentuje pojedynczą gwiazdę bez satelitów - jej wartość określa liczbę ramion,
• gdy jest listą - reprezentuje gwiazdę z satelitami - liczba elementów listy określa wówczas liczbę ramion gwiazdy-matki (będącą jednocześnie liczbą gwiazd-satelitów); poszczególne elementy tej listy (które także są liczbami lub listami) określają wygląd gwiazd-satelitów.

Gwiazdy należy rysować w losowych kolorach, ale wszystkie ramiona danej gwiazdy muszą być rysowane tym samym kolorem. Zakładamy, że dana :kod określa rysunek, w którym poszczególne gwiazdy nie nachodzą na siebie.

Przykład pokazuje rysunek jaki może powstać po wywołaniu GWIAZDY [12 6 6 [77 5 5 5 5 [3 3 3 3 3] 4 4 4] 24]

Strategia

Podczas pisania rozwiązania należy użyć rekurencji. Jest to niezbyt efektywny, ale najprostszy sposób, aby napisać rozwiązanie, które obsłuży listę o dowolnej ilości list zagnieżdżonych w listach. Jednak w trakcie kolejnych wywołań rekurencyjnych przydałoby się przekazać długość ramienia gwiazdy, dlatego rekurencyjnie będzie wywoływana funkcja pomocnicza gwiazdy_rek, a procedura GWIAZDY jedynie uruchomi mechanizm z wstępnymi wartościami.

Rekurencja

Podczas kolejnych wywołań rozpoznawane są dwa przypadki: w przypadku napotkania listy jako element należy wywołać rekurencyjnie gwiazdy_rek i 3 razy mniejszą wartością ramienia gwiazdy :a. W przypadku liczby, a nie listy nie istnieje potrzeba kolejnego wywołania.

1. oto gwiazdy_rek :kod :a
2.   jeżeli (lista? :kod)[
3.     niech "ramion długość :kod
4.   ][
5.     niech "ramion :kod
6.   ]
7.   ukp jld
8.   powtórz (:ramion) [
9.     np :a
10.     ws :a
11.     pw 360 / :ramion
12.   ]
13.   ukp "czarny

(2.) Jeśli procedura otrzymała listę to (3.) ustal ilość ramień na długość listy, a w przypadku, gdy zostałą podana liczba to (5.) za ilość ramion wystarczy uznać przekazany :kod. (7.) Wylosuj kolor pisaka i (8. - 13.) narysuj gwiazdę o wyznaczonej ilości ramion.

14.   jeśli (lista? :kod) [
15.     powtórz (:ramion) [
16.       pod
17.       np :a*2
18.       opu
19.       gwiazdy_rek (element npw :kod) (:a / 3)
20.       pod
21.       ws :a*2
22.       pw 360/:ramion
23.       opu
24.     ]
25.   ]
26. już

W przypadku, gdy przekazany :kod (14.) to dla każdego elementu z listy (15. - 24) należy wyznaczyć środek następnej gwiazdy i wywołać jej rysowanie.

Główna procedura

W procedurze GWIAZDY wystarczy wywołać procedure gwiazdy_rek przekazując kod oraz początkową długość ramienia tak jak poniżej.

1. oto GWIAZDY :kod
2.   gwiazdy_rek :kod ((losowa 60) + 20)
3. już

Zadanie 2

Zdefiniuj procedurę DOM :a :h :kod rysującą dom składający się z parteru, pięter i dachu. Każda kondygnacja domu jest szarym prostokątem, o tej samej wysokości, zawierającym okna i drzwi (drzwi - tylko parter). Dach stanowią kominy.

Dana :a określa szerokość domu, :h - wysokość (bez dachu). Dana :kod jest listą słów złożonych z małych liter alfabetu łacińskiego (bez polskich znaków diakrytycznych). Pierwszy element listy opisuje parter, ostatni - dach, inne – piętra, w kolejności od dołu ku górze. Każde słowo opisuje wygląd jednej kondygnacji. Poszczególne litery mają następujące znaczenie:

Parter:

• spółgłoski g, j, p, q określają "drzwi zamknięte" - brązowy prostokąt,
• pozostałe spółgłoski to "okna zamknięte" - brązowe kwadraty,
• samogłoska y określa "drzwi otwarte" - żółty prostokąt,
• pozostałe samogłoski to "okna otwarte" - żółte kwadraty.

Piętro:

• wszystkie spółgłoski - "okna zamknięte",
• wszystkie samogłoski - "okna otwarte".

Dach:

• litery b, d, f, h, k, l, t - "kominy wysokie" - czarne prostokąty,
• pozostałe litery - "kominy niskie" - czarne kwadraty.

Bok kwadratu (okna, niskiego komina) powinien być maksymalnie duży, ale nie większy niż jedna trzecia wysokości kondygnacji. Okna, drzwi i kominy nie mogą nachodzić na siebie. Prostokąty reprezentujące drzwi i kominy wysokie mają być dwa razy wyższe od kwadratów. Poszczególne elementy powinny być równomiernie rozmieszczone w obrębie kondygnacji, drzwi dotykają do dołu parteru, a kominy wyrastają ponad najwyższym piętrem (patrz rysunek). Zakładamy, że :kod zawiera co najmniej dwa słowa, a więc dom składa się co najmniej z parteru i dachu.

Poniżej podany jest przykładowy rysunek, jaki może powstać dla wywołania DOM 90 86 [jan lubi lot]

Rozwiązanie niedostępne

Strategia

Jeśli pomiędzy przez dwa punkty ma przechodzić prosta równoległa do krawędzi ekranu to w obu punktach współrzędna x lub y musi być sobie równa. W przypadku wykrycia spełnienia tej zależności można zwrócić prawdę. W celu drobnej optymalizacji rozwiązania. Porównywane będą tylko współrzędne aktualnie rozpatrywanego punktu z współrzędnymi punktów wcześniej rozpatrzonych.

Rozwiązanie

Funkcja PUNKTY wygląda następująco:

1. oto PUNKTY :lp
2.   niech "x_pom []
3.   niech "y_pom []
4.   powtórz (długość :lp) [
5.     niech "el element npw :lp
6.     jeżeli ( LUB numel pierw :el :x_pom > 0
7.                             numel ost :el :y_pom > 0 )[
8.       wynik "prawda
9.     ][
10.       niech "x_pom nak pierw :el :x_pom
11.       niech "y_pom nak ost :el :y_pom
12.     ]
13.   ]
14.   wynik "fałsz
15. już

(2. - 3.) Inicjalizacja pustych list na współrzędne rozpatrzonych punktów, ale które nie znalazły punktu z którym spełniłoby zależności z zadania. (4.) Dla każdego punktu: (5.) pobierz element i zapisz do zmiennej :el. Jeśli (6.) na odpowiedniej liście jest wymieniona ta sama wartość współrzędnej to (8.) zwróć prawdę. (9.) W przeciwnym wypadku (10. - 11.) dopisz współrzędne na odpowiednie listy. Jeśli po zakończeniu pętli nie została zwrócona prawda oznacza to, że należy (14.) zwrócić fałsz.

Strategia

Tak samo jak w przypadku zadania pierwszego najlepszym rozwiązaniem jest użycie rekurencji. W tym przypadku nie istnieje potrzeba pisania dodatkowej funkcji pomocniczej, ponieważ za każdym razem będzie przekazywana jedynie lista bez dodatkowego argumentu.

Rozwiązanie

Funkcja wygląda następująco:

1. oto SUMACYFR :lp
2.   niech "w 0
3.   jeżeli(lista? :lp)[
4.     powtórz (długość :lp)[
5.       niech "w :w + SUMACYFR element npw :lp
6.     ]
7.   ][
8.     powtórz (długość :lp)[
9.       jeśli(liczba? element npw :lp)[
10.         niech "w :w + element npw :lp
11.       ]
12.     ]
13.   ]
14.   wy :w
15. już

(2.) Ustal wartość listy na 0. (3.) Jeśli argument jest lista to (4. - 6.) dodaj do zmiennej :w wartość zwróconą przez SUMACYFR dla każdego z elementów listy. (7.) W przypadku, gdy argument nie jest listą, a zestawem znaków to (8. - 12.) sprawdź każdy znak po kolei i jeśli (9.) trafi się cyfra to (10.) należy ją dodać do :w. Na koniec (14.) zwróć wartość zmiennej :w.

• Rozwiązania zadań