Logia 1996/97 - Etap III

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

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.

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.

8.   niech "w 0
9.   niech "p 1
10.   dopóki [:p < :max][
11.     zwiększ "w
12.     niech "p :p*2
13.   ]

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.

14.   niech "szer 600/:w
15.   niech "wys 400/(długość :kod)
16.   jeżeli (:szer < :wys)[
17.     niech "a :szer
18.   ][
19.     niech "a :wys
20.   ]

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ść.

21.   pod
22.   ws :a*(długość :kod)/2
23.   pw 90
24.   ws :a*:w/2
25.   lw 90
26.   opu

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

27.   powtórz (długość :kod)[
28.     niech "e (element ((długość :kod) - npw + 1) :kod)
29.     niech "t :p/2
30.     powtórz (:w)[
31.       jeśli (:e - :t >= 0)[
32.         wielokąt[
33.           ukm "czarny
34.           powtórz 4[
35.             np :a
36.             pw 90
37.           ]
38.         ]
39.         niech "e :e - :t
40.       ]
41.       niech "t :t/2
42.       pod
43.       pw 90
44.       np :a
45.       lw 90
46.       opu
47.     ]
48.     pod
49.     pw 90
50.     ws :a*:w
51.     lw 90
52.     np :a
53.     opu
54.   ]
55. 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.

• Rozwiązania zadań