Strona główna » Poradniki » Logomocja » LOGIA » Logia 2009/10 - Etap II

Logia 2009/10 - Etap II

iOryginalna treść zadań jest dostępna pod oficjalnym adresem konkursu LOGIA

Zadanie 1 (domki)

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

Rysunek pomocniczy

  • 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.

  1. oto DOMKI :n
  2.   niech "w 450
  3.   niech "a 0
  4.   niech "r 0.5 / (:n - 1)
  5.   powtórz (:n) [
  6.     niech "a (:a + 0.5 + :r * (npw - 1))
  7.   ]
  8.   niech "a :w / :a
  9.   pod
  10.   pw 90 ws :w/2
  11.   lw 90 ws (:a+:a*(pwk(3)/4))/2
  12.   opu
  13.   powtórz (:n) [
  14.     DOMKI_dom :a * (:r * (:n - npw) + 0.5)
  15.   ]
  16. już

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:

  1. oto DOMKI_dom :a
  2.   niech "b :a/12
  3.   kwadrat :a "zielony
  4.   np :a
  5.   wielokąt [
  6.     ukm "czerwony
  7.     pw 30 np (:a/2)
  8.     pw 60 np (:a/2)
  9.     pw 60 np (:a/2)
  10.   ]
  11.   ws :b*5 pw 90
  12.   pod
  13.   np :b lw 90
  14.   kwadrat 4*:b "żółty
  15.   pod
  16.   pw 90 np :b*6
  17.   lw 90
  18.   kwadrat 4*:b "żółty
  19.   ws :b*7 pw 90
  20.   np :b
  21.   wielokąt [
  22.     ukm "jasnoniebieski
  23.     powtórz 2 [
  24.       ws (:b*4)
  25.       pw 90
  26.       ws (:b*6)
  27.       pw 90
  28.     ]
  29.   ]
  30.   np :b*4 lw 90
  31. już

Zadanie 2 (lotnisko)

W porcie lotniczym, na każdej tabliczce informującej o odlocie samolotu, jest pokazywana informacja o docelowym lotnisku i godzinie odlotu. Nazwa portu lotniczego jest kodowana w postaci trzyliterowego skrótu złożonego z wielkich liter alfabetu łacińskiego, np. WAW oznacza Warszawę, AMS - Amsterdam, BCN - Barcelonę. Godzina odlotu jest reprezentowana zawsze przez cztery cyfry, np. 0905 oznacza godzinę 9:05. Litery i cyfry można zmieniać cyklicznie (tzn. za literą Z występuje litera A, a po 9 jest 0) o jedną pozycję "do przodu" lub "do tyłu".

Zdefiniuj funkcję ILEZMIAN :lot1 :lot2, której danymi są siedmioznakowe słowa (pierwsze trzy znaki oznaczają kod portu, następne cztery godzinę odlotu), a wynikiem minimalna liczba zmian znaków, jaką należy wykonać, aby zmienić wyświetlaną informację z jednego lotu na drugi.

ILEZMIAN "WAW1230 "WAW1301jest 5
ILEZMIAN "WAW1230 "AMS1240jest 21

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.

  1. oto ILEZMIAN_zmien :a :b :od :do
  2.   niech "i 0
  3.   niech "el :do - :od + 1
  4.   dopóki [:a <> :b][
  5.     zwiększ "a
  6.     zwiększ "i
  7.     jeśli (:a > :do) [
  8.       niech "a :od
  9.     ]
  10.   ]
  11.   jeżeli (:i < :el - :i)[
  12.     wynik :i
  13.   ][
  14.     wynik :el - :i
  15.   ]
  16. już

(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.

  1. oto ILEZMIAN :lot1 :lot2
  2.   niech "z 0
  3.   powtórz 3 [
  4.     niech "a ascii (element npw :lot1)
  5.     niech "b ascii (element npw :lot2)
  6.     niech "od ascii "A
  7.     niech "do ascii "Z
  8.     niech "z :z + ILEZMIAN_zmien :a :b :od :do
  9.   ]
  10.   powtórz 4 [
  11.     niech "a element (npw + 3) :lot1
  12.     niech "b element (npw + 3) :lot2
  13.     niech "od 0
  14.     niech "do 9
  15.     niech "z :z + ILEZMIAN_zmien :a :b :od :do
  16.   ]
  17.   wynik :z
  18. już

(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.

Zadanie 3 (robot)

Robot Gerard potrafi wykonać tylko cztery polecenia, nakazujące mu przejść w jedną z czterech stron świata. Napisz funkcję ROBOT :trasa, której wartością jest liczba punktów trasy, w których robot znalazł się więcej niż jeden raz. Parametr :trasa jest słowem opisującym sekwencję poleceń, w którym mogą występować jedynie litery N, S, W oraz E. Litery te oznaczają odpowiednio polecenie ruchu w kierunku północnym, południowym, zachodnim oraz wschodnim. Zakładamy, że trasa jest tak ułożona, że każdy z jej odcinków robot przechodzi tylko raz. Gerard może wykonać maksymalnie 500 ruchów.

ROBOT "NESWjest 1
ROBOT "NNESWWSEEjest 2

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]]
  5.   niech "ile 0
  6.   powtórz (długość :trasa) [
  7.     niech "el (element npw :trasa)
  8.     wybierz (:el) [
  9.       N [niech "pozy :pozy + 1]
  10.       E [niech "pozx :pozx - 1]
  11.       W [niech "pozx :pozx + 1]
  12.       S [niech "pozy :pozy - 1]
  13.     ]
  14.     niech "poz (lista :pozx :pozy)
  15.     jeżeli (numel :poz :pozlista = 0) [
  16.       niech "pozlista nak :poz :pozlista
  17.     ][
  18.       niech "ile :ile + 1
  19.     ]
  20.   ]
  21.   wynik :ile
  22. 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.