Logia 2012/13 Etap II
Zadanie 1 (Mozaika)
Nowe budynki w Logianowie będą ozdobione mozaikami układanymi z kwadratowych kafelków w kolorach: czerwonym (c), zielonym (z), czarnym (x), białym (b) i fioletowym (f). Mozaiki są układane na podstawie kolorowych szablonów. Twórca szablonów jest miłośnikiem Juliusza Cezara i postanowił przy ich przygotowywaniu wykorzystać szyfr Cezara, polegający na cyklicznym zastępowaniu każdej kolejnej litery w alfabecie, literą występującą dalej o określoną liczbę pozycji, przy czym jeśli wykraczamy poza alfabet, to kolejne litery bierzemy z początku alfabetu.
Napisz procedurę MOZAIKA :kolory :klucz :wiersz, po wywołaniu której na środku ekranu powstanie rysunek mozaiki, o szerokości 600 lub wysokości 300, opisanej przez parametry:
- słowo :kolory określa kolory (alfabet) używane w danym szablonie oraz ich kolejność, kolory nie powtarzają się
- liczba :klucz definiuje sposób zastępowania kolorów i może przyjmować wartości od 0 do 100
- niepuste słowo :wiersz, które opisuje dolny wiersz mozaiki i może zawierać jedynie kolory wymienione w parametrze :kolory
Każdy kolejny wiersz powstaje przez zaszyfrowanie poprzedniego wiersza. Liczba wierszy jest o jeden większa od długości parametru :kolory. Na przykład dla alfabetu "xfzb i klucza 6, wiersz "xxxfffbbbxxx przechodzi w wiersz "zzzbbbfffzzz.
W tabelce poniżej umieszczono przykłady zastępowania kolorów.
| :kolory | :klucz | przed zastępieniem | po zastąpieniu |
|---|---|---|---|
| "xfzb | 6 | czarny | zielony |
| "xfzb | 6 | fioletowy | biały |
| "xfzb | 6 | zielony | czarny |
| "xfzb | 6 | biały | fioletowy |
| :kolory | :klucz | przed zastępieniem | po zastąpieniu |
|---|---|---|---|
| "bzx | 1 | biały | zielony |
| "bzx | 1 | zielony | czarny |
| "bzx | 1 | czarny | biały |
Rozwiązanie
Na początku ustalmy wartości zmiennych pomocniczych. Po pierwsze rozpoznawanie koloru pisaka będzie odbywać się poprzez wyszukanie pozycji koloru (2.) w zmiennej :nazwyKol. Znaleziony indeks posłuży do wybrania (3.) odpowiedniej nazwy koloru z listy. Następnie (4.) tworzymy zmienną, która będzie przechowywać ile kolorów zostało wybranych (dla uproszczenia zapisu kodu) oraz to (5.) ile będzie faktycznie wierszy miał obraz wynikowy. To samo robimy dla (6.) ilości kolumn. Kolejny etap polega na (7. - 13.) dopasowaniu rozmiaru pojedynczego kwadratu do obszaru rysowania. Potem (14. - 17.) należy przesunąć żółwia w lewy dolny róg rysunku.
- oto MOZAIKA :kolory :klucz :wiersz
- niech "nazwyKol "czxbf
- niech "listaKol [czerwony zielony czarny biały fioletowy]
- niech "dlKolory długość :kolory
- niech "poziomów (długość :kolory) + 1
- niech "kolumn (długość :wiersz)
- niech "h 300/:poziomów
- niech "w 600/:kolumn
- jeżeli(:h < :w) [
- niech "a :h
- ][
- niech "a :w
- ]
- pod
- ws :a*:poziomów/2 pw 90
- ws :a*:kolumn/2 lw 90
- opu
Druga część kodu przedstawia rysowanie kolejnych poziomów rysunku. Na początku każdego poziomu (19. - 29.) rysowany jest aktualny wiersz. Potem (30. - 31.) należy przejść na następny poziom. W każdej iteracji pozostaje jeszcze (32. - 40.) przygotować następny wiersz. Początkowo jest on przechowywany w tymaczasowej zmiennej :s, aby potem go przepisać do zmiennej :wiersz na podstawie której wartości rysowane są kolejne poziomy rysunku.
- powtórz (:poziomów) [
- powtórz (:kolumn) [
- niech "nrKol numel (element npw :wiersz) :nazwyKol
- wielokąt [
- ukm (element :nrKol :listaKol)
- powtórz 4 [
- np :a pw 90
- ]
- ]
- pw 90 np :a
- lw 90
- ]
- pw 90 ws :a*:kolumn
- lw 90 np :a
- niech "s "
- powtórz (:kolumn) [
- niech "el element npw :wiersz
- niech "poz numel :el :kolory
- niech "poz reszta ((:poz - 1) + :klucz) :dlKolory
- niech "t element (:poz + 1) :kolory
- niech "s (słowo :s :t)
- ]
- niech "wiersz :s
- ]
- już
Zadanie 2 (Ślimak)
Napisz funkcję KIEDY :x :y :z, której wynikiem będzie liczba określająca, którego dnia ślimak znajdzie się na szczycie dziesięciometrowego słupa. Ślimak pierwszego dnia startuje u podstawy słupa. Każdego dnia wspina się o :x centymetrów. Każdej nocy osuwa się o :y centymetrów, chyba że natrafi na półkę - wtedy zatrzymuje się na niej. Półki znajdują się co :z centymetrów, licząc od podstawy słupa. Zakładamy, że :x jest większe od :y.
| KIEDY 300 100 100 | jest 4 |
|---|---|
| KIEDY 5 3 2 | jest 250 |
Rozwiązanie
Rozwiązanie polega na zastosowaniu nieskończonej pętli oraz liczników, które będą pamiętać (3.) ile dni już upłynęło oraz (2.) gdzie znajduje się ślimak (tj. jakiej wysokości).
- oto KIEDY :x :y :z
- niech "ile 0
- niech "dni 0
- dopóki [:ile < 1000][
- zwiększ "dni
- niech "ile :ile + :x
- niech "półka (int(:ile/:z))*:z
- niech "ile :ile - :y
- jeśli (:ile < :półka) [
- niech "ile :półka
- ]
- ]
- wynik :dni
- już
(4.) W pętli dopóki ślimak nie osiągnie szczytu: (5.) rozpoczynamy dzień i (6.) symulujemy wspinaczke do góry. Następnie (7.) obliczamy pozycje najbliższej półki. Po wyliczeniu możemy (8.) opuścić ślimaka w dół o :y cm, ale (9.) sprawdzamy czy według obliczeń ślimak nie minął półki. Jeśli tak to (10.) ustalamy jego wysokość na pozycję półki. Na koniec (13.) zwracamy ile :dni ślimak wędrował na szczyt.
Zadanie 3 (Pascal)
Trójkąt Pascala to trójkątna tablica liczb, skonstruowana w następujący sposób: na dwóch bokach trójkąta znajdują się jedynki, liczby wewnątrz trójkąta są sumą dwóch najbliższych liczb położonych w wierszu powyżej.
Ola podaje Antkowi dwie liczby: numer wiersza oraz pozycję w obrębie wiersza. Zadaniem Antka jest podanie odpowiedniej liczby w trójkącie Pascala. Pomóż Antkowi i napisz funkcję PASCAL :w :p. Parametr :w określa numer wiersza i może przyjmować wartości od 1 do 2000. Parametr :p określa pozycję liczby w wierszu i może przyjmować wartości od 1 do 4, a także od :w-3 do :w, przy czym :w nie jest mniejsze od :p.
| PASCAL 5 3 | jest 6 |
|---|---|
| PASCAL 10 7 | jest 84 |
Rozwiązanie
Wartości trójkąta Pascala można wyliczać ze wzoru rekurencyjnego. Każdy wyraz trójkąta to suma elementów znajdujących się nad nim na prawo oraz lewo. Dokładne informacje można znaleźć w artykule o Trójkącie Pascala. Poniższy kod to zastosowanie wspomnianej wskazówki:
- oto PASCAL :w :p
- jeżeli (LUB (:p = 1) (:p = :w)) [
- wynik 1
- ][
- wynik (PASCAL :w-1 :p-1) + (PASCAL :w-1 :p)
- ]
- już