Strona główna » Poradniki » Logomocja » LOGIA » Logia 2003/04 - Etap II
 

Logia 2003/04 - Etap II

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

Zadanie 1 (Domki)

Zdefiniuj procedurę DOMKI :liczba rysującą na ekranie ciąg domków. Kolejne domki mają wspólną ścianę i opisują kolejne cyfry nieujemnej całkowitoliczbowej danej :liczba. W zależności od wartości cyfry zamalowany jest odpowiedni trójkąt domku. Ponadto, dla cyfr parzystych, zamalowana jest na szaro lewa połowa dachu. Poniżej pokazane są domki odpowiadające poszczególnym cyfrom: 0, 1, 2, ..., 9:

Dla danej liczby każdy domek jest tej samej wielkości. Wszystkie domki powinny mieścić się na ekranie. Odległości skrajnych domków od, odpowiednio, lewej i prawej krawędzi ekranu, powinny być identyczne.Poniżej widać efekty wywołań, kolejno: DOMKI 1000, DOMKI 4545 oraz DOMKI 2468.

Strategia

Przed rozpoczęciem pisania procedur warto zauważyć, że dla przypadków od 1 - 8 zamalowywane są kolejne trójkąty. Wyjątkiem jest tutaj przypadek 0 (nic zamalowanego) oraz 9 (zamalowany prawy górny trójkąt). Nie należy też pominąć faktu, że dla parzystych cyfr malowany jest górny lewy trójkąt na szaro. Wypisane zależności pozwolą napisać funkcję domek, która narysuje domek dla konkretnej cyfry :n i boku :a.

Wybór koloru

Jednak przed przystąpieniem do rysowania domku warto zauważyć, że jeśli dany trójkąt nie jest zamalowywany na konkretny kolor to jego kolor jest biały. Poniższa funkcja wybierzKolor przyjmuje trzy argumenty: :warunek oraz :kolor. Jej działanie polega na ustawienie koloru malowania na :kolor jeśli spełniony jest :warunek. W przeciwnym razie ustawiony jest kolor biały. Tego typu procedura pozwoli na uproszczenie ustawiania koloru danego elementu domku.

  1. oto wybierzKolor :warunek :kolor
  2.   jeżeli (:warunek)[
  3.     ukm :kolor
  4.   ][
  5.     ukm "biały
  6.   ]
  7. już

Rysowanie domku

Procedura rysowania domku wyśrodkuje go w punkcie w którym zostanie rozpoczęta procedura i pozwoli na dostosowanie jego wielkości.

  1. oto domek :n :a
  2.   ws :a/2
  3.   powtórz (8) [
  4.     wybierzKolor (npw = :n) "czarny
  5.     jeżeli (reszta npw 2 <> 0) [
  6.       wielokąt [
  7.         np :a
  8.         pw 90
  9.         np :a
  10.         pw 135
  11.       ]
  12.     ][
  13.       wielokąt [
  14.         np (:a * pwk(2))
  15.         pw 135
  16.         np :a
  17.         pw 90
  18.       ]
  19.     ]
  20.     pw 45
  21.   ]

Rysowanie rozpocznij od (2.) wyśrodkowania żółwia pośrodku głównego kwadratu domku i (3. - 21.) narysuj wszystkie osiem trójkątów. W każdej iteracji (4.) wybierz kolor malowania na podstawie porównania numeru iteracji z :n oraz (5.) wybierz sposób rysowania trójkąta. Po zakończeniu iteracji (20.) obróć żółwia o 45°.

  1.   np :a
  2.   lw 90
  3.   wybierzKolor (reszta :n 2 = 0) "jasnoszary
  4.   wielokąt [
  5.     np :a
  6.     pw 135
  7.     np (:a * pwk(2))
  8.   ]
  9.   pw 90
  10.   wybierzKolor (:n = 9) "czarny
  11.   wielokąt [
  12.     np :a
  13.     pw 135
  14.     np (:a * pwk(2))
  15.   ]
  16.   ws :a/2
  17.   ukm "biały
  18. już

Żółw znajduje się teraz w takiej pozycji jak po linijce (2.). (22. - 23.) Przejdź do rysowania ostatnich dwóch trójkątów. (24.) Wybierz kolor malowania w zależności od parzystości :n i (25. - 29.) narysuj lewy trójkąt. (30. - 36.) Analogicznie dla prawego trójkąta. (37.) Wróć żółwiem do pozycji w której została rozpoczęta procedura i (38.) zresetuj kolor malowania.

Rysowanie domków

Procedura DOMKI wyliczy najpierw krótszy bok trójkątów :a, a następnie narysuje domki dla każdej kolejnej cyfry w przekazanej liczbie :liczba.

  1. oto DOMKI :liczba
  2.   niech "w 780
  3.   niech "h 460
  4.   niech "n długość :liczba
  5.   niech "a :w / (:n * 2)
  6.   niech "ah :h / 3
  7.   jeśli (:a > :ah) [
  8.     niech "a :ah
  9.   ]

Ustal (2.) szerokość i (3.) wysokość obszaru roboczego. (4.) Pobierz ile jest cyfr i (5.) oblicz długość :a. (6. - 9.) Jeśli rysunek miałby się nie zmieścić to dokonaj korekty boku.

  1.   pod
  2.   pw 90 np :a * (:n - 1)
  3.   lw 90
  4.   opu
  5.   powtórz (:n)[
  6.     domek reszta :liczba 10 :a
  7.     pod
  8.     lw 90 np :a * 2
  9.     pw 90
  10.     opu
  11.     niech "liczba int(:liczba / 10)
  12.   ]
  13. już

(10. - 13.) Przejdź do pierwszego domu od prawej, ponieważ wybieranie kolejnych cyfr będzie odbywać się poprzez pobieranie ostatniej cyfry. (14.) Dla każdej kolejnej cyfry: (15.) Narysuj domek, (16. - 19.) przesuń żółwia na pozycję kolejnego domku i (20.) usuń ostatnią cyfrę liczby.

Zadanie 2 (Kółko i krzyżyk)

Zapewne wiele razy grałeś(aś) w kółko i krzyżyk. Klasyczna wersja tej gry polega na stawianiu naprzemian przez graczy, na planszy 3x3 pola, swojego znaku: krzyżyka lub kółka. Wygrywa ten z graczy, który jako pierwszy uzyska trzy swoje znaki w jednej linii: w poziomie, w pionie lub na skos. Nie wiemy, który z graczy rozpoczął grę, ani do którego gracza należy teraz ruch. Zakładamy, że na planszy nie ma sekwencji wygrywającej.

Zdefiniuj funkcję KK :gra, której daną jest dziewięcioliterowe słowo, opisujące układ krzyżyków i kółek na planszy - wierszami (tzn. trzy pierwsze znaki opisują pierwszy wiersz planszy, itd.). W danej :gra mogą występować tylko małe litery x, o oraz w. Oznaczają one: x - krzyżyk na danym polu, o - kółko na danym polu, zaś w oznacza wolne pole.

Wartością funkcji KK jest prawda, jeśli dana :gra opisuje możliwy układ w czasie gry, zaś fałsz - w przeciwnym przypadku.

KK "xwxoxoowwjest prawda
KK "xxwowowwojest prawda
KK "xxoowoowwjest fałsz

Strategia

Zadanie choć może wydawać się trudne takie nie jest. Przede wszystkim należy zdać sobie sprawę, że jeśli w każdej turze każdy z graczy dokłada po jednym swoim symbolu to różnica ilości symboli x i o może wynosić 0 (tyle samo) lub 1 (jednego więcej). Jednak niewiadomo kto zaczął, dlatego niekoniecznie więcej może być x-ów, dlatego należy pobrać wartość absolutną z różnicy ilości symboli. Wtedy podany wcześniej warunek jest prawdziwy dla każdego prawidłowego ustawienia planszy.

Kod

Funkcja KK realizuje wygląda następująco:

  1. oto KK :gra
  2.   niech "x 0
  3.   niech "o 0
  4.   powtórz (długość :gra)[
  5.     niech "el element npw :gra
  6.     jeśli (:el = "x) [
  7.       zwiększ "x
  8.     ]
  9.     jeśli (:el = "o) [
  10.       zwiększ "o
  11.     ]
  12.   ]
  13.   wynik (abs (:x - :o) <= 1)
  14. już

(2. - 3.) Ustaw liczniki symboli na 0. (4.) Dla każdego pola: (5.) pobierz element i zapisz do zmiennej :e. W zależności od symbolu (6. - 8.) zwiększ licznik :x lub (9. - 11.) licznik :o. (13.) Na koniec zwróć wynik porównania wartości absolutnej różnicy liczników czy jest mniejszy, równy 1.

Zadanie 3

Zdefiniuj funkcję SZYFR :słowo :klucz1 :klucz2, której danymi są:

  • :słowo - słowo do zaszyfrowania składające się z małych liter alfabetu łacińskiego (bez polskich znaków diakrytycznych),
  • :klucz1 - jednocyfrowa liczba określająca klucz szyfrowania samogłosek,
  • :klucz2 - jednocyfrowa liczba określająca klucz szyfrowania spółgłosek.

Wynikiem funkcji jest zakodowane :słowo.

Przyjęty sposób kodowania to modyfikacja jednego z najstarszych znanych systemów kodowania, przypisywanego Juliuszowi Cezarowi. Polega on na zastąpieniu każdej kolejnej litery - literą występującą w alfabecie o określoną liczbę pozycji dalej, cyklicznie (tj. jeśli wykraczamy poza alfabet, to kolejne litery bierzemy z początku alfabetu). W naszym zadaniu tę liczbę pozycji, oddzielnie dla samogłosek i spółgłosek, określają klucze szyfrowania funkcji SZYFR.

SZYFR "abrakadabra 1 2jest "bdtbmbfbdtb
SZYFR "axeyiz 2 4jest "cbgakd

Strategia

W celu uproszczenia kodu warto napisać funkcję szyfr_oblicz, która dla podanego znaku :znak oraz klucz :klucz obliczy znak po przesunięciu. W ten sposób kod funkcji SZYFR stanie się bardziej przejrzysty.

Przesunięcie znaku

Funkcja szyfr_oblicz wygląda następująco:

  1. oto szyfr_oblicz :znak :klucz
  2.   wynik znak((reszta (((ascii :znak) - 97) + :klucz) 26) + 97)
  3. już

Oczywiście funkcję można zapisać w postaci kolejnych instrukcji, ale to jest najkrótszy zapis, który powinno się napisać bez problemu jeśli wcześniej już się pisało kod dotyczący szyfrowania Cezara. Algorytm kolejno wykonuje następuje czynności:

  1. Zamień :znak na kod ascii - otrzymana zostanie wtedy liczba z przedziału [97, 122], gdzie 97 odpowiada literze a, a 122 z
  2. Od kodu znaku odejmij 97 - otrzymana wartość jest z przedziału od [0, 25]
  3. Dodaj przesunięcie :klucz - otrzymana wartość może być z przedziału [0, 50] w zależności od klucza
  4. Pobierz resztę z dzielenia przez 26 (ilość liter od a do z) wtedy z powrotem otrzymana zostanie wartość od [0, 25]
  5. Dodaj do wartości 97 i skonwertuj liczbę na znak

Szyfrowanie

Teraz funkcja SZYFR musi jedynie wywołać odpowiednio funkcję szyfr_obliczenia i otrzymaną wartość dołączyć do wyniku.

  1. oto SZYFR :słowo :klucz1 :klucz2
  2.   niech "w "
  3.   powtórz (długość :słowo) [
  4.     niech "e element npw :słowo
  5.     jeżeli(numel :e [a o e u i y] > 0) [
  6.       niech "w nak szyfr_oblicz :e :klucz1 :w
  7.     ][
  8.       niech "w nak szyfr_oblicz :e :klucz2 :w
  9.     ]
  10.   ]
  11.   wynik :w
  12. już

(2.) Przygotuj zmienną wynikową. (3.) Dla każdej litery: (4.) pobierz znak i zapisz do zmiennej :e. (5.) Jeśli :e jest samogłoską to (6.) szyfruj kluczem :klucz1. W przeciwnym razie (8.) kluczem :klucz2. Otrzymane znaki dopisz na koniec zmiennej :w. Na koniec (11.) zwróć zmienną :w.