Logia 1995/96 - Etap II

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.

15.   dopóki[:n > 0][
16.     niech "wyraz nak "A :wyraz
17.     zmniejsz "n
18.   ]
19.   dopóki[:m > 0][
20.     niech "wyraz nak "B :wyraz
21.     zmniejsz "m
22.   ]
23.   wynik :wyraz
24. 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

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.

11.   jeżeli (:licznikB = :licznikA)[
12.     niech "h_max 400
13.     niech "h :h_max / :licznikA
14.     pod
15.     ws :h_max/2
16.     pw 90
17.     ws :h_max/2
18.     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.

19.     powtórz (:licznikA + 1)[
20.       powtórz (:licznikA)[
21.           kropka 4
22.           np :h
23.       ]
24.       kropka 4
25.       ws :h_max
26.       pw 90
27.       np :h
28.       lw 90
29.     ]
30.     pw 90
31.     ws :h+:h_max
32.     lw 90
33.     opu

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

34.     powtórz (długość :wyraz)[
35.       jeżeli (element npw :wyraz = "A)[
36.         np :h
37.       ][
38.         pw 90
39.         np :h
40.         lw 90
41.       ]
42.     ]
43.   ][
44.     pisz "Błąd
45.   ]
46. 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:

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:

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:

28.   lw 90
29.   np :a*(:n+1)
30.   opu
31.   niech "trasa TRASA_REG_pom :n
32.   powtórz 4[
33.     powtórz (długość :trasa)[
34.       jeżeli (element npw :trasa = "P)[
35.         np :a
36.       ][
37.         pw 90
38.         np :a
39.         lw 90
40.       ]
41.     ]
42.     pw 90
43.   ]
44. 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.

• Rozwiązania zadań