Logia 2009/10 - Etap II

Zadanie 1 (domki)

Firma architektoniczna Domlandia zaprojektowała osiedle domków stojących w jednym rzędzie zgodnie z następującymi zasadami:

• każdy domek składa się z części mieszkalnej zbudowanej na bazie kwadratu oraz spadzistego dachu w postaci trapezu równoramiennego (górna podstawa jest dwa razy krótsza od dolnej),
• część mieszkalna ma drzwi i dwa okna, ich położenie i wymiary wynikają z pomocniczego rysunku powyżej,
• ostatni domek (po prawej) ma szerokość równą połowie szerokości pierwszego domku (po lewej),
• różnica szerokości sąsiednich domków jest stała w danym osiedlu, np. przy trzech domkach środkowy ma szerokość równą ¾ szerokości lewego domku.

Napisz procedurę DOMKI :n rysującą osiedle domków według projektu Domlandii. Parametr :n określa liczbę domków i może przyjmować wartości od 2 do 20. Szerokość rysunku wynosi 450. Do kolorowania należy użyć czterech dowolnych kolorów za wyjątkiem czarnego, którym są rysowane krawędzie.

Rysunki poniżej przedstawiają efekt wywołania procedury DOMKI:

DOMKI 3

DOMKI 4

Wyliczanie szerokości

Zasadniczym problem, który powstaje podczas rozwiązywania zadania dotyczy określenia szerokości kolejnych domków. Wiadomo tylko, że różnica pomiędzy dwoma sąsiednimi domami jest identyczne, a pierwszy jest dwa razy większy niż drugi. Obie informacje pozwalają stwierdzić, że dla dowolnego n.

Przyjmijmy, że nadłuższy budynek ma długość a. Wtedy najmniejszy ma a/2. Oznacza to, że dla n = 2 zachodzi równość a + a/2 = 450 czyli a = 300. Dla n = 3 sytuacja nieco się komplikuje. Wiadomo, że różnica między kolejnymi jest równa i możemy przyjąć, że zawiera wartości od 0 (dla najkrótszego) do 0.5 (dla najszerszego). Wyliczmy r = 0.5 / (n - 1). Jest to wartość, która określa różnice pomiędzy kolejnymi bokami. Kontynuując dla n = 3 otrzymujemy a + 0.75a + 0.5a = 450. W tym przypadku a = 200.

Podsumowując strategia wyliczania najdłuższego boku polega na określeniu długości kolejnych wartości ich sumowania i na tej podstawie wyliczenia danych.

Na początku (2.) określamy szerokość rysunku, (3.) inicjalizujemy zmienną do sumowania oraz wyliczamy wartość :r. W pętli (5. - 7.) sumujemy wartości stojące po lewej stronie równania z a. (8.) Obliczamy długość na podstawie wyliczonej sumy. Dalsza część to (9. - 12.) przejście w lewy dolny róg rysunku oraz (13. - 15.) narysowanie :n domków.

W powyższym kodzie w linijce (14.) można zapisać zamiast ":n - npw" wartość "npw - 1". Wtedy program będzie rysował budynki od najmniejszego do największego.

Rysowanie budynku

Poniżej znajduje się kod rysowania domku, który pozostawiam bez komentarza:

Zmiana znaku

Rozwiązanie zadania warto rozpocząć od napisania funkcji, która dla podanego alfabetu oraz dwóch znaków a i b wyznaczy o ile trzeba będzie przesunąć. Przede wszystkim program powinien działać w pętli i jeden ze znaków tak długo cyklicznie zmieniać w obrębie alfabetu, aż jeden i drugi znak będa identyczne. Każdą próbę zmiany należy odnotować.

Na koniec uzyskany zostaje pewien wynik, który nie zawsze musi być optymalny. Znaki można zmieniać zarówno do przodu jak i do tyłu, więc należy pamiętać, że czasem druga opcja może okazać się rozsądniejsza. Nie oznacza to, że trzeba oddzielnie sprawdzać przypadki. Wiedząc, że alfabet znaków ma długość 26 to jeśli do przodu należało zrobić np. 10 zmian to do tyłu tych zmiena potrzebaby 16. Suma wartości zmian do tyłu i do przodu równa się liczbie znaków w alfabecie.

Przedstawiony poniżej funkcja ILEZMIAN_zmien przyjmuje cztery argumenty: dwa znaki :a i :b w wartościach ascii oraz zakres [:od :do] alfabetu w systemie ascii.

(2.) Początkowo ustalamy, że nie potrzeba zmian. (3.) Oblicz długość alfabetu. (4. - 10.) Dopóki znaki są różne do to zmieniaj znak :a do przodu. Bardzo ważne, aby pamiętać, że (7.) jeśli zostanie osiągnięty znak spoza alfabetu to (8.) należy wrócić na początek alfabetu. Na koniec (11. - 15.) należy wybrać w którą stronę wartość wynikowa będzie mniejsza.

Funkcja główna

W celu przekazywania wartości ascii znaków oraz alfabetu można skorzystać z funkcji ascii, który dla podanego znaku zwraca wartość liczbową zgodnie z tabelą ascii.

(2.) Zmienna :z będzie zliczać łączną liczbę potrzebnych zmian. (3. - 9.) Pierwsze trzy znaki to litery z zakresu (6.) od znaku A (7.) do znaku Z. (10. - 16.) Analogicznie należy postąpić w przypadku czterech cyfr. (17.) Na koniec wystarczy zwrócić wartość zmiennej :z.

Omówienie

Najprostsza implementacja polega na utworzeniu dwóch zmiennych do przechowywania aktualnej pozycji robota. Następnie w pętli na podstawie kolejnej wartości z trasy należy odpowiednio zmieniać wartość współrzędnych. Dodatkowo w tle powinna zostać utworzona dodatkowa lista, która będzie zawierać odwiedzone już punkty. Po każdym przesunięciu należy sprawdzić czy robot już był w tym miejscu tj. czy punkt znajduje się na liście. Jeśli się znajduje to znaczy, że należy zwiększyć liczbę punktów na któych robot był więcej niż jeden raz. Jednak jeśli pole jeszcze nie było zapamiętane to znaczy, że wystarczy je dodać na listę.

1. oto ROBOT :trasa
2.   niech "pozx 0
3.   niech "pozy 0
4.   niech "pozlista [[[0 0] [0 0]]]
5.   niech "ile 0
6.   powtórz (długość :trasa) [
7.     niech "el (element npw :trasa)
8.     niech "poz1 (lista :pozx :pozy)
9.     wybierz (:el) [
10.       N [niech "pozy :pozy + 1]
11.       E [niech "pozx :pozx - 1]
12.       W [niech "pozx :pozx + 1]
13.       S [niech "pozy :pozy - 1]
14.     ]
15.     niech "poz2 (lista :pozx :pozy)
16.     niech "poz sortuj (lista :poz1 :poz2)
17.     jeżeli (numel :poz :pozlista = 0) [
18.       niech "pozlista nak :poz :pozlista
19.     ][
20.       niech "ile :ile + 1
21.     ]
22.   ]
23.   wynik :ile
24. już

Przygotuj zmienną (2.) współrzędną X oraz (3.) współrzedną Y. Początkowo (4.) na liście punktów powinien znaleźć się punkt początkowy (0, 0), a wartość (5.) powtórzonych pól powinna być 0. (6.) W pętli dla każdego polecenia z trasy: (7.) pobierz element i (8. - 13.) wykonaj odpowiedni ruch. Nastepnie (14.) utwórz listę opisującą aktualną pozycję i (15.) sprawdź czy punkt nie został jeszcze odwiedzony. Na koniec (21.) zwróć wartość zmiennej :ile.

• Rozwiązania zadań