Strona główna » Poradniki » Logomocja » LOGIA » Logia 1996/97 - Etap III
 

Logia 1996/97 - Etap III

· Etap I · Etap II · Etap III ·
iOryginalna treść zadań jest dostępna pod oficjalnym adresem konkursu LOGIA

Zadanie 1

Sieć metra w mieście Y składa się z wielu linii. Każda z nich biegnie od Centrum do pewnej końcowej stacji na peryferiach. Na każdej linii kursuje jeden pociąg, który w chwili 0 wyrusza z Centrum i pokonuje odcinki między kolejnymi stacjami w czasie 1 minuty. Na stacjach końcowych - na peryferiach i w Centrum pociąg stoi jedną minutę. Czas postoju pociągu na pośrednich stacjach jest zaniedbywalny.

Zdefiniuj funkcję dwuparametrową STACJA :n :linia, której wartością jest nazwa stacji na danej linii, na jakiej powinien znajdować się pociąg po upływie :n minut. Zakładamy, że wartością pierwszego parametru może być dowolna liczba całkowita nieujemna, a drugiego niepusta lista kolejnych stacji - zaczynając od Centrum - na dowolnej linii metra. Oto przykładowe wyniki:

STACJA 0 [Centrum Ratusz Politechnika Uniwersytet Piaski Zalesie Kamraty]ma wartość: Centrum
STACJA 2 [Centrum Ratusz Politechnika Uniwersytet Piaski Zalesie Kamraty]ma wartość: Politechnika
STACJA 15 [Centrum Ratusz Politechnika Uniwersytet Piaski Zalesie Kamraty]ma wartość: Ratusz
STACJA 8483 [Centrum Ratusz Politechnika Uniwersytet Piaski Zalesie Kamraty]ma wartość: Centrum

Jednym ze sposobów rozwiązania zadania jest przeprowadzenia symulacji: dla każdej minuty wyoknamy ruch kolejką, aż zmienna :n osiągnie 0. Należy tu zwrócić uwagę, że pociąg przemierza całą trasę, czeka 1 minutę, a następnie wraca, czeka minute i dopiero jedzie dalej. Jest to pojedynczy pełny cykl.

  1. oto STACJA :n :linia
  2.   niech "a 1
  3.   niech "k 1
  4.   dopóki[:n > 0][
  5.     niech "a :a + :k
  6.     zmniejsz "n
  7.     jeśli (lub (:a = 1) (:a = długość :linia))[
  8.       zmniejsz "n
  9.       niech "k :k*-1
  10.     ]
  11.   ]
  12.   wynik element :a :linia
  13. już

Symulację rozpoczynamy od (2.) zadeklarowania zmiennej :a, która oznacza stację na której jest pociąg oraz (3.) :k - określi w którą stronę jedzie pociąg. (4.) Dopóki :n > 0 to: (5.) przesuwamy pociąg na następną stację i (6.) odliczamy czas potrzebny na przebycie. (7.) Jeśli pociąg znajduje się na jednej ze stacji krańcowych to (8.) odliiczamy czas postoju i (9.) zmieniamy kierunek przejazdu. (12.) Na koniec zwracamy nazwę stacji wskazywanej przez zmienną :a.

Kod działa i jest w pełni poprawny. Jednak jego efektywność jest bardzo niska. Im większa wartość :n tym dłużej będą trwały obliczenia. Zadanie można wykonać inaczej. Efektywność kodu poniżej jest całkowicie niezależna od wprowadzonych danych:

  1. oto STACJA2 :n :linia
  2.   niech "a reszta :n (2 * (długość :linia))
  3.   jeśli (:a + 1 > (długość :linia)) [
  4.     niech "a (długość :linia) - (:a - (długość :linia) + 1)
  5.   ]
  6.   wynik element (:a + 1) :linia
  7. już

(2.) Obliczamy, którą stację w cyklu odwiedza aktualnie pociąg. Można to zrobić w ten sposób, ponieważ pełny cykl to dla linii [1, 2, ..., n] to [1, 2, ..., n, n, ..., 2, 1], dlatego możemy odliczyć wszystkie pełne cykle z przejazdów zawartych w :n. Jednak nie posiadamy drugiej podanej listy, dlatego (3.) sprawdzamy czy pociąg wraca ze stacji n. Jeśli tak to (4.) obliczamy, którą stację od końca odwiedza. Na koniec (6.) zwracamy stację wskazywaną przez :a. Doliczamy tutaj jeden, ponieważ funkcja reszta zwróci wartość od 0 do 2n - 1, którą później zamieniamy na zakres od 0 do n - 1, a numerowanie na liście jest od 1 do n.

Drugie rozwiązanie zadania jest dostępne w zapisie projektu pod nazwą STACJA2.

Zadanie 2

Poniższy rysunek przedstawia 13 kwadratów rozrzuconych w sposób losowy w polu ograniczonym kwadratową ramką.

Obrazek 1 do zadania 2

Napisz procedurę bez parametrów, o nazwie KWADRATY, która tworzy na ekranie komputera podobny rysunek złożony z losowej liczby od 5 do 15 kwadratów rozrzuconych w sposób losowy w kwadratowym polu ograniczonym ramką:

  • Bok kwadratowej ramki powinien być 8 razy większy od boku każdego z małych kwadratów.
  • Każdy kwadrat musi się mieścić w polu ograniczonym ramką, ale jego bok może dotykać ramki, tak że boki kwadratu i ramki nakładają się (jak kwadrat po prawej stronie powyższego rysunku).
  • Żadne dwa kwadraty nie mogą na siebie nachodzić, ale mogą stykać się ze sobą, tak że ich boki nakładają się (tak jak dwa kwadraty w lewym dolnym rogu na przykładowym rysunku).

Trudność zadania polega na odpowiednim losowaniu pozycji kwadratów tak, aby nie wyszły poza obręb większego kwadratu. Przed rozpoczęciem pisania procedury głównej warto napisać funkcję pomocniczą, która pozwoli narysować kwadrat. Będzie przyjmowała trzy argumenty: przesunięcie w poziomie, pionie oraz długość boku kwadratu.

  1. oto KWADRATY_kwa :l :d :a
  2.   pod
  3.   pw 90
  4.   np :l
  5.   lw 90
  6.   np :d
  7.   opu
  8.   powtórz 4[
  9.     np :a
  10.     pw 90
  11.   ]
  12.   pod
  13.   ws :d
  14.   pw 90
  15.   ws :l
  16.   lw 90
  17.   opu
  18. już

(1.) Przyjmowane argumenty to :l - przesunięcie w poziomie, :d - przesunięcie w pionie oraz :a - długość boku. (2. - 7.) Przesuwamy żółwia gdzie będzie narysowany kwadrat. (8. - 11.) Rysowanie kwadratu i (12. - 18.) żółw zostaje przesunięty tam gdzie był na początku rozpoczęcia funkcji.

Główna funkcja KWADRATY będzie zapisana następująco:

  1. oto KWADRATY
  2.   niech "h 400
  3.   niech "ile losowa 11 + 5
  4.   niech "a :h/8
  5.   KWADRATY_kwa :h/(-2) :h/(-2) :h
  6.   powtórz (:ile)[
  7.     KWADRATY_kwa ((losowa (:h - :a)) - :h/2) ((losowa (:h - :a)) - :h/2) :a
  8.   ]
  9. już

(2.) Ustalenie wysokości i szerokości obrazu wynikowego. (3.) Zmienna :ile określa ile kwadratów będzie w środku dużego kwadratu. (4.) Wyliiczenie długości boku mniejszego kwadratu. (5.) Narysowanie dużego kwadratu, a potem wszystkie małe kwadraty (6. - 8.). Losując pozycję (7.) należy pamiętać, że wylosowana liczba musi być zakresu [0, :h-:a]. W przypadku powyższego kodu trzeba odjąć jeszcze :h/2, aby były prawidłowo wypozycjonowane.

Zadanie 3

W arabskich budowlach można spotkać mozaiki ułożone z kwadratowych - jasnych i ciemnych kafelków, przedstawiające różne napisy. Mozaika na poniższym rysunku, ułożona z 5 wierszy po 9 ciemnych (widocznych na rysunku) i białych (niewidocznych) kwadratowych kafelków przedstawia słowo Allah, zapisane pismem kufickim.

Obrazek 1 do zadania 3

Następny rysunek przedstawia inny napis kuficki z XIV wieku, pochodzący z meczetu w Aleppo.

Obrazek 2 do zadania 3

Przyjmujemy następujący sposób kodowania mozaikowych napisów, takich jak na przedstawionych rysunkach:

  • Każdy wiersz mozaiki kolejno od góry do dołu zapisujemy w postaci odpowiedniego słowa utworzonego z cyfr dwójkowych 0 i 1, reprezentujących odpowiednio jasny i ciemny kafelek. Np. pięć kolejnych wierszy mozaiki przedstawiającej słowo Allah zapisujemy w postaci pięciu 9-cio cyfrowych słów:
    1. 111010101
    2. 101010101
    3. 111010101
    4. 001010101
    5. 001111101
  • Następnie każdy taki wiersz odczytujemy jako dwójkowy zapis pewnej liczby naturalnej i znajdujemy odpowiadający mu zapis dziesiętny tej liczby. Lista tych liczb dziesiętnych odpowiadających kolejnym wierszom mozaiki stanowi jej kod.

Na przykład:kodem słowa Allah jest lista: [469 341 469 85 125],kodem mozaiki pochodzącej z meczetu w Aleppo jest lista:[2130564575 1342525760 1568430071 1431655761 1430259159 22925317 1564542677 1411240448 2113357499 274584193 1598035643 1147138601 1459689147 1952313865 122953403 1971142664 1426137023 2004181029 1146441405 2004871808 1073745583 1566007977 1431658495 1440694272 1350571349 1440601429 1431655749 2113797501].

Napisz procedurę z jednym parametrem MOZAIKA :kod, która mając dany :kod mozaiki - w postaci listy liczb naturalnych - tworzy na ekranie możliwie duży jej rysunek. Możesz założyć, że mozaika o danym kodzie będzie prostokątem mającym nie mniej niż 4 i nie więcej niż 32 wiersze złożone z od 6 do 32 kwadratowych kafelków.

Trudność zadania polega na przeliczeniu liczb z systemu dziesiętnego na binarny. Na początek należy znaleźć największą liczbę na liście. Pozwoli to na określenie ile kwadratów na szerokość ma mieć rysunek.

  1. oto MOZAIKA :kod
  2.   niech "max 0
  3.   powtórz (długość :kod)[
  4.     jeśli (element npw :kod > :max)[
  5.       niech "max element npw :kod
  6.     ]
  7.   ]

(2. - 7.) Szukanie największego elementu na liście.

  1.   niech "w 0
  2.   niech "p 1
  3.   dopóki [:p < :max][
  4.     zwiększ "w
  5.     niech "p :p*2
  6.   ]

W celu wyliczenia szerokości należy wyliczyć, która potęga 2 jest większa od największej znalezionej wartości. (8.) Zmienna :w będzie przechowywać, którą potęgą jest aktualna wartość (9.) zmiennej :p. (10.) Dopóki wyliczona potęga jest mniejsza od :max to (11.) zwiększamy numer potęgi :w i zwiększamy wartość :p dwukrotnie.

  1.   niech "szer 600/:w
  2.   niech "wys 400/(długość :kod)
  3.   jeżeli (:szer < :wys)[
  4.     niech "a :szer
  5.   ][
  6.     niech "a :wys
  7.   ]

Znając ile kafelków jest zaszyfrowanych w każdej liczbie można obliczyć (14.) szerokość i (15.) wysokość kafelków tak, aby wypełniły cały ekran. Ze względu na fakt, że kafelki mają być kwadratowe to (16. - 20.) jako bok :a pzryjmujemy mniejszą wyliczoną wartość.

  1.   pod
  2.   ws :a*(długość :kod)/2
  3.   pw 90
  4.   ws :a*:w/2
  5.   lw 90
  6.   opu

(21. - 26.) Żółw zostaje przesunięty w lewo dolny róg obrazu.

  1.   powtórz (długość :kod)[
  2.     niech "e (element ((długość :kod) - npw + 1) :kod)
  3.     niech "t :p/2
  4.     powtórz (:w)[
  5.       jeśli (:e - :t >= 0)[
  6.         wielokąt[
  7.           ukm "czarny
  8.           powtórz 4[
  9.             np :a
  10.             pw 90
  11.           ]
  12.         ]
  13.         niech "e :e - :t
  14.       ]
  15.       niech "t :t/2
  16.       pod
  17.       pw 90
  18.       np :a
  19.       lw 90
  20.       opu
  21.     ]
  22.     pod
  23.     pw 90
  24.     ws :a*:w
  25.     lw 90
  26.     np :a
  27.     opu
  28.   ]
  29. już

(27.) W pętli żółw rysuje tyle rzędów ile jest liczb na liście. (28.) W i-tej iteracji należy pobrać i-tą liczbę od końca z listy i tymczasowej zmiennej :t przypisać połowę wyliczonej potęgi maksymalnej. (29.) Rysowanie jednego rzędu polega na: (30.) Sprawdzeniu czy aktualna wartość :t jest zawarta w :e. Jeśli tak to (31. - 37.) narysowaniu czarnego kwadratu i (38.) zmniejszeniu :e o wartość :t. Niezależnie od narysowanego kwadratu trzeba (40.) dwukrotnie zmniejszyć wartość :t, która odpowiada za wybieranie kolejnych 0 i 1 zapisu binarnego liczby :e. Po narysowaniu kwadratu (lub też nie): (41. - 45.) należy przesunąć żółwia jeden kwadrat w prawo. (47. - 53.) Na zakończenie rysowania rzędu należy przejść do rysowania następnego.