Strona główna » Poradniki » Logomocja » LOGIA » Logia 1995/96 - Etap II
 

Logia 1995/96 - Etap II

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

Zadanie 1

Zdefiniuj dwuparametrową funkcję AB :n :m, której wartością jest losowo utworzone słowo, złożone z :n liter A i :m liter B. Wywołanie funkcji AB z parametrami odpowiednio :n równym 2 i :m równym 3 zwróci jako wartość jedno z dziesięciu słów, jakie można utworzyć z dwóch liter A i trzech liter B, np. AABBB lub BABAB.

Funkcję AB podzielimy na dwa etapy. W etapie pierwszym będziemy losować literę, którą dopisujemy na koniec wyniku. W każdej iteracji zliczamy ile razy wylosowaliśmy którą litere. Pętle kończymy, gdy licznik którejś litery osiągnie swoje maksimum. Wtedy w ramach drugiego etapu wynik uzupełnimy literą, której licznik jeszcze nie osiągnął maksimum.

  1. oto AB :n :m
  2.   niech "wyraz "
  3.   dopóki [
  4.     I (:n > 0) (:m > 0)
  5.   ][
  6.     niech "los losowa 2
  7.     jeżeli (:los = 0)[
  8.       niech "wyraz nak "A :wyraz
  9.       zmniejsz "n
  10.     ][
  11.       niech "wyraz nak "B :wyraz
  12.       zmniejsz "m
  13.     ]
  14.   ]

(2.) Deklarujemy zmienną :wyraz. Jest to zmienna do której będziemy dopisywać A i B. Następnie (3.) rozpoczynamy pierwszy etap. W pętli dopóki (4.) obydwa liczniki są większe od zera: (6.) losujemy, którą literę dopisujemy. (7.) W zależności od wylosowanej liczby: (8.) dopisujemy A i (9.) zmniejszamy zmienną :n. W przeciwnym wypadku (11.) dopisujemy B i (12.) zmniejszamy licznik :m.

  1.   dopóki[:n > 0][
  2.     niech "wyraz nak "A :wyraz
  3.     zmniejsz "n
  4.   ]
  5.   dopóki[:m > 0][
  6.     niech "wyraz nak "B :wyraz
  7.     zmniejsz "m
  8.   ]
  9.   wynik :wyraz
  10. już

Po wyjściu z pętli nie wiemy, której litery mamy już nie dopisywać. Istnieje możliwość, aby to sprawdzić i dopisać odpowiednią ilość wystąpień drugiej litery. Jednak o wiele prostszym sposobem jest (15. - 18.) dopisywanie A dopóki licznik nie osiągnie 0 oraz (19.- 22.) B póki licznik nie osiągnie 0. (23.) Na koniec zwracamy :wyraz.

Zadanie 2

Każdą trasę na kwadratowej siatce (n+1)*(n+1), która:

  • składa się z poziomych i pionowych odcinków łączących sąsiednie punkty na siatce,
  • zaczyna się od lewego dolnego i kończy w prawym górnym rogu siatki,
można zakodować za pomocą odpowiedniego słowa złożonego z n liter A i m liter B. Przyjmujemy, że litera A jest kodem odcinka trasy biegnącego pionowo z dołu do góry, zaś litera B kodem odcinka biegnącego poziomo w prawo.

Poniższe rysunki przedstawiają wywołania POPRZEK "ABAABBBAAABBBBAA oraz POPRZEK "ABBBBAAAAABBABBA

Obrazek 1 do zadania 2

Sprawdzanie poprawności wprowadzonego wyrazu polega na sprawdzeniu czy jest tyle samo wystąpień litery A i B:

  1. oto POPRZEK :wyraz
  2.   niech "licznikA 0
  3.   niech "licznikB 0
  4.   powtórz (długość :wyraz)[
  5.     jeżeli (element npw :wyraz = "A)[
  6.       zwiększ "licznikA
  7.     ][
  8.       zwiększ "licznikB
  9.     ]
  10.   ]

Deklarujemy liczniki występień (2.) litery A i (3.) B. (4.) Dla każdej litery w :wyraz: (5.) sprawdzamy czy jest A. Jeśli jest to (6.) zwiększamy :licznikA w przeciwnym wypadku (8.) :licznikB.

  1.   jeżeli (:licznikB = :licznikA)[
  2.     niech "h_max 400
  3.     niech "h :h_max / :licznikA
  4.     pod
  5.     ws :h_max/2
  6.     pw 90
  7.     ws :h_max/2
  8.     lw 90

(11.) Mapę rysujemy tylko wtedy, gdy oba liczniki są równe. (12.) Ustalamy maksymalną wysokość rysunku. (13.) Obliczamy odległość pomiędzy dwoma kropkami w pionie bądź poziomie. (14. - 18.) Przesuwamy pisak w lewy dolny róg rysunku.

  1.     powtórz (:licznikA + 1)[
  2.       powtórz (:licznikA)[
  3.           kropka 4
  4.           np :h
  5.       ]
  6.       kropka 4
  7.       ws :h_max
  8.       pw 90
  9.       np :h
  10.       lw 90
  11.     ]
  12.     pw 90
  13.     ws :h+:h_max
  14.     lw 90
  15.     opu

(19. - 29.) Rysujemy siatkę złożoną z kropek i (30. - 33.) wracamy z powrotem w lewy dolny róg rysunku.

  1.     powtórz (długość :wyraz)[
  2.       jeżeli (element npw :wyraz = "A)[
  3.         np :h
  4.       ][
  5.         pw 90
  6.         np :h
  7.         lw 90
  8.       ]
  9.     ]
  10.   ][
  11.     pisz "Błąd
  12.   ]
  13. już

Przechodzimy do rysowania trasy na wykropkowanej mapie. (34.) Dla każdego elementu z podanego wyrazu :wyraz: w przypadku (35.) wystąpienia litery A (36.) rysujemy pionową kreske. Jeśli jednak litera to B to (38. - 40.) rysujemy kreske poziomą. Pozostaje nam teraz rozpatrzeć przypadek kiedy dane są niepoprawne. Wtedy (44.) wypisujemy tylko odpowiedni komunikat.

Zadanie 3

Poniższy rysunek przedstawia mapę rzędu 3:

Obrazek 1 do zadania 3

Mapa rzędu n jest kwadratową siatką kropek, utworzoną z 2n+1 poziomych rzędów po 2n+1 kropek w każdym rzędzie. Środkowe punkty na zachodniej, północnej, wschodniej i południowej krawędzi mapy oznaczamy odpowiednio literami W, N, E oraz S.

Trasa WNESW nazywamy każdą trasę na mapie spełniającą trzy warunki:

  1. składa się z jednostkowych poziomych i pionowych odcinków, łączących sąsiednie punkty na mapie,
  2. zaczyna się w punkcie W, następnie biegnie do N, do E, do S i wraca do W,
  3. ma minimalną długość.

Mówimy, że trasa WNESW jest regularna, jeśli po jej obrocie o 90o dookoła środka mapy otrzymamy tę samą trasę. Poniższy rysunek przedstawia przykładowe regularne trasy na mapie rzędu 3:

Obrazek 2 do zadania 3

Napisz procedurę TRASA_REG :n, która dla dowolnej wartości parametru :n, nie mniejszej niż 1 i nie większej niż 6:

  • rysuje na ekranie mapę rzędu :n,
  • wykreśla na niej w sposób losowy regularną trasę WNESW.
Procedurę należy napisać w taki sposób, aby każda regularna trasa WNESW mogła być efektem jej wywołania.

Losowanie trasy

W celu napisania funkcji TRASA_REG warto napisać funkcję pomocniczą TRASA_REG_pom, która wylosuje trasę. Ze względu na fakt, że trasa ma być regularna to wylosowany ślad będzie powtórzony 4 razy. Podczas losowania trasy należy na bieżąco sprawdzać ile zostało wylosowanych kresek pionowych, a ile poziomych. Jeśli już jednego typu kresek jest maksymalna ilość to losowaną listę należy uzupełnić tylko kreskami drugiego typu.

Wylosowany kod będzie składał się z dwóch literek S i P. W przyjętym zapisie literka P oznacza kreskę naprzód, a literka S kreskę w bok.

  1. oto TRASA_REG_pom :max
  2.     niech "P 0
  3.     niech "S 0
  4.     niech "lista []
  5.     dopóki[(I nie (:P = :max) nie (:S = :max) )][
  6.       jeżeli ((losowa 2) = 0)[
  7.         niech "lista nak "P :lista
  8.         zwiększ "P
  9.       ][
  10.         niech "lista nak "S :lista
  11.         zwiększ "S
  12.       ]
  13.   ]
  14.   dopóki[:P < :max][
  15.     niech "lista nak "P :lista
  16.     zwiększ "P
  17.   ]
  18.   dopóki[:S < :max][
  19.     niech "lista nak "S :lista
  20.     zwiększ "S
  21.   ]
  22.   wynik :lista
  23. już

Rysowanie trasy

Rysowanie trasy najlepiej rozpocząć od narysowania siatki i napisaniu literek kierunku:

  1. oto TRASA_REG :n
  2.   niech "a 400 / (:n*2)
  3.   pod
  4.   ustalPoz (lista 0 (:a*:n+20))
  5.   piszTekst "S
  6.   ustalPoz (lista 0 (-:a*:n-20))
  7.   piszTekst "N
  8.   ustalPoz (lista (:a*:n+20) 0)
  9.   piszTekst "E
  10.   ustalPoz (lista (-:a*:n-20) 0)
  11.   piszTekst "W
  12.   wróć
  13.   ws :a*:n
  14.   pw 90
  15.   ws :a*:n
  16.   lw 90
  17.   powtórz (:n*2 + 1)[
  18.     powtórz (:n*2)[
  19.       kropka 1
  20.       np :a
  21.     ]
  22.     kropka 1
  23.     ws :a*:n*2
  24.     pw 90
  25.     np :a
  26.     lw 90
  27.   ]

(2.) Dostosuj długość odcinka do rysowanej mapy. (3. - 11.) Napisz kierunki świata. (12. - 27.) Narysuj siatkę po której będzie rysowana mapa.

Drugi etap rysowania mapy polega na (31.) wylosowaniu mapy i jej narysowaniu. Należy pamiętać, że raz wylosowana trasa ma zostać narysowana cztery razy:

  1.   lw 90
  2.   np :a*(:n+1)
  3.   opu
  4.   niech "trasa TRASA_REG_pom :n
  5.   powtórz 4[
  6.     powtórz (długość :trasa)[
  7.       jeżeli (element npw :trasa = "P)[
  8.         np :a
  9.       ][
  10.         pw 90
  11.         np :a
  12.         lw 90
  13.       ]
  14.     ]
  15.     pw 90
  16.   ]
  17. już

(28. - 30.) Ustaw odpowiednio żółwia. (31.) Wylosuj trasę. (32. - 43.) Cztery razy narysuj wylosowaną trasę. (34.) W zależności od pobranej literki kodu narysuj odpowiedni odcinek.