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

Logia 2003/04 - Etap III

https://mattomatti.com/li033
· Etap I · Etap II · Etap III ·
iOryginalna treść zadań jest dostępna pod oficjalnym adresem konkursu LOGIA

Zadanie 1

Zdefiniuj procedurę KWADRATY :lista rysującą na ekranie ciąg kwadratów. Dana :lista jest listą list. Każdy element danej :lista jest listą pustą lub listą jednoelementową zbudowaną analogicznie, tj. też jest listą pustą lub jednoelementową. Liczba elementów danej :lista określa liczbę rysowanych kwadratów. Każdy kwadrat może zawierać wewnętrzne kwadraty, zależnie od poziomu zagłębień listy opisującej kwadrat. Odstępy pomiędzy współśrodkowymi kwadratami są takie same i równe długości boku najmniejszego z nich. Długości boków wszystkich zewnętrznych kwadratów są takie same i możliwie duże, tak żeby wszystkie kwadraty mieściły się na ekranie. Odstępy pomiędzy sąsiednimi zewnętrznymi kwadratami są równe jednej piątej długości boku zewnętrznych kwadratów.

Przykładowe wywołania:

Strategia

Zadanie zostanie podzielone na trzy mniejsze zadania. Pierwsze z nich będzie dotyczyć rysowania kwadratu o zadanym boku o środku tam gdzie stoi żółw. Drugą funkcją pomocniczą będzie funkcja, która policzy ile razy jest lista zagnieżdżona w liście. Innymi słowy ile będzie kwadratów do narysowania w danej iteracji. Z kolei główna funkcja korzystając z obydwu narysuje wskazany w zadaniu rysunek.

Rysowanie wyśrodkowanego kwadratu

Poniższą funkcję pozostawiam bez komentarza, ponieważ składa się z elementarnych części rysowania.

  1. oto KWADRAT_srodek :a
  2.   pod
  3.   ws :a/2 pw 90
  4.   ws :a/2 lw 90
  5.   opu
  6.   powtórz 4 [
  7.     np :a
  8.     pw 90
  9.   ]
  10.   pod
  11.   np :a/2 pw 90
  12.   np :a/2 lw 90
  13.   opu
  14. już

Liczenie list w liście

Do rozwiązania tego problemu warto wykorzystać rekurencję.

  1. oto KWADRATY_glebokosc :el
  2.   jeśli (puste? :el) [
  3.     wynik 1
  4.   ]
  5.   wynik 1 + KWADRATY_glebokosc pierw :el
  6. już

(2.) Po wywołaniu sprawdzamy przekazany argument. Jeśli element jest pusty to znaczy, że dana lista nie ma już więcej podlist. (3.) Wtedy należy zwrócić jeden. (5.) Jednak jeśli przekazany argument ma chociaż jeden element to zwracamy sumę 1 oraz głębokość przekazując do kolejnego wywołania pierwszy element listy :el.

Główna procedura

  1. oto KWADRATY :lista
  2.   niech "w 700
  3.   niech "h 420
  4.   niech "dl długość :lista
  5.   niech "a :w / (:dl + (:dl - 1) / 5)
  6.   jeśli (:a > :h) [
  7.     niech "a :h
  8.   ]

Określ maksymalną (2.) szerokość i (3.) wysokość rysunku. (4.) Pobierz długość listy - wygodniej będzie dalej używać dwuliterej zmiennej niż całego sformułowania. (5.) Oblicz długość na podstawie maksymalnej szerokości. Należy pamiętać, żeby uwzględnić przerwy pomiędzy kwadratami równymi szerokości kwadratu podzielonej na pięć. (6.) Upewnij się, że bok kwadratu nie wszedł większy niż maksymalna wysokość rysunku. Jeśli tak to (7.) zmień długość kwadratu na wysokość rysunku.

  1.   pod
  2.   pw 90 ws ((:dl - 1) / 2) * :a * 1.2
  3.   lw 90
  4.   opu
  5.   powtórz długość :lista [
  6.     niech "n KWADRATY_glebokosc (element npw :lista)
  7.     niech "b :a / (2*:n - 1)
  8.     powtórz :n [
  9.       KWADRAT_srodek :b * (2*npw - 1)
  10.     ]
  11.     pod
  12.     pw 90 np :a * 1.2
  13.     lw 90
  14.     opu
  15.   ]
  16. już

(9. - 12.) Rysowanie rozpoczynamy od przejścia na środek lewego kwadratu. (13.) Dla każdego elementu na liście głównej: (14.) policz ile pobrany element ma list w liście. (15.) Na tej podstawie wylicz szerokość najmniejszego kwadratu. (16. - 18.) Narysuj wszystkien :n kwadratów. Na koniec każdej iteracji (19. - 22.)przesuń na środek kwadratu obok.

Zadanie 2

Zdefiniuj funkcję KK :gra, której daną jest niepusta lista dziewięcioliterowych słów. Każde słowo opisuje układ kółek i krzyżyków w popularnej grze "kółko i krzyżyk" na planszy 3 na 3 pola - wierszami (tzn. trzy pierwsze znaki opisują pierwszy wiersz planszy, itd.). W słowach 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 - wolne pole. Zakładamy poprawność danych słów, tzn. każde z nich opisuje możliwy układ w czasie gry. Zakładamy także, że żadne ze słów nie opisuje sekwencji wygrywającej.

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

KK [xwxoxooww]prawda
KK [xwxoxooww xwxoxooxw xwxoxooxo]prawda
KK [wwxoxooww xwxoxooxw]fałsz
KK [wwwwwwwww wwwwxwwww owwwxwwww oxwwxwwww]prawda

Strategia

Początkowo zadanie może wydawać się nieco skomplikowane, ale warto zauważyć, że wymienione układy są poprawne. Potem warto się zastanowić kiedy kolejne układy na planszy będą prawidłowe. Najprostszy warunek jest taki, że pomiędzy dwoma kolejnymi układami na planszy zaszła dokładnie jedna zmiana wartości pól. Drugi warunek polega na sprawdzeniu, który z graczy się ruszył. Jeśli ten sam gracz wykonał dwa razy z rzędu ruch to układy nie mogą opisywać realnego stanu gry.

W rozwiązaniu nie zostały ujęte jeszcze dwa warunki: przede wszystkim należałoby sprawdzić czy w każdym następnym układzie zmniejsza się liczba wolnych pól. Jeśli nie to znaczy, że przy przejściu do kolejnego układu zmieniany jest znak na zajętym polu.

Szukanie różnic

Funkcja KK_roznic szuka różnic pomiędzy przekazanymi argumentami :a i :b jako wynik zwraca listę elementów różnych elementów dodają na listę tylko element z listy :b.

  1. oto KK_roznic :a :b
  2.   niech "lista []
  3.   powtórz (długość :a) [
  4.     jeśli (element npw :a <> element npw :b) [
  5.       niech "lista nak element npw :b :lista
  6.     ]
  7.   ]
  8.   wynik :lista
  9. już

(2.) Początkowo lista musi być pusta. (3.) Dla każdego elementu w układzie planszy: (4.) Jeśli elementy są różne to (5.) dodaj do listy element z listy :b. (8.) Na koniec zwróć utworzoną listę.

Główna funkcja

  1. oto KK :gra
  2.   niech "ostatni "
  3.   powtórz ((długość :gra) - 1) [
  4.     niech "lista KK_roznic (element npw :gra) (element (npw + 1) :gra)
  5.     jeśli (długość :lista <> 1) [
  6.       wynik "fałsz
  7.     ]
  8.     jeśli (pierw :lista = :ostatni) [
  9.       wynik "fałsz
  10.     ]
  11.     niech "ostatni pierw :lista
  12.   ]
  13.   wynik "prawda
  14. już

(2.) Na początek należy stwierdzić, że niewiadomo kto ostatni wykonał ruch. (W niektórych układach początkowych można to stwierdzić porównując ilość x oraz o). (3.) Dla każdej kolejnej pary układów na podanej liście :gra: (4.) pobierz listę różnych elementów. Następnie (5.) sprawdź czy lista ma długość 1. Fałsz będzie oznaczał, że nie doszło do jakiejkolwiek zmiany na planszy, albo więcej niż jedno pole zostało zmienione. W takim przypadku (6.) przerwij funkcję zwracając fałsz. (8.) Fałsz należy też (9.) zwrócić jeśli w poprzedniej kolejce ten sam gracz wykonał ruch. (11.) Na koniec każdej iteracji zamień, który gracz ostatnio wykonał ruch. (13.) Jeśli funkcja nie zostanie przerwana to zwróć prawdę.

Zadanie 3

Zdefiniuj funkcję DESZYFR :zaszyfr :klucz1 :klucz2, której danymi są:

  • :zaszyfr - poprawnie zaszyfrowane słowo, składające się z małych liter alfabetu łacińskiego (bez polskich znaków diakrytycznych), nie dłuższe niż siedmioliterowe,
  • :klucz1 - jednocyfrowa liczba określająca klucz szyfrowania samogłosek,
  • :klucz2 - jednocyfrowa liczba określająca klucz szyfrowania spółgłosek.

Wynikiem funkcji jest lista zawierająca wszystkie możliwe słowa, które po zaszyfrowaniu dają :zaszyfr. Kolejność słów w wyniku jest nieistotna. Przyjęty sposób szyfrowania 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 DESZYFR.

DESZYFR "fycmqva 2 2[dwakoty]
DESZYFR "epi 4 3[ame amf bme bmf]

Strategia

Na początek warto dokładnie przeanalizować skąd biorą się wyrazy, które po zaszyfrowaniu mogą być podanym wyrazem. Przede wszystkim każdy znak mógł zostać zaszyfrowany po zamiania samogłoski lub spółgłoski, dlatego istnieje możliwość, że są dwa różne sposoby zapisu danej pozycji szyfrowanego słowa. Jednak jeśli litera została zaszyfrowana poprzez zamianę samogłoski to po deszyfrowaniu kluczem musi być samogłoską, a nie spółgłoską. Analogiczne rozumowanie dla spółgłosek.

Czy samogłoska

Funkcja sprawdzająca czy znak jest samogłoską wygląda następująco:

  1. oto samogłoska? :znak
  2.   wynik (numel :znak [a o e u i y] > 0)
  3. już

Deszyfrowanie

W celu usprawnienia działania fłównej funkcji warto napisać funkcję, która będzie deszyfrować znak na podstawie klucza:

  1. oto DESZYFR_znak :znak :klucz
  2.   niech "wartosc ascii(:znak)
  3.   niech "wartosc :wartosc - 97 - :klucz
  4.   jeśli (:wartosc < 0) [
  5.     niech "wartosc :wartosc + 26
  6.   ]
  7.   wynik znak(:wartosc + 97)
  8. już

Główna funkcja

Początkowo rozwiązanie może wydawać się nieuintycyjne, ale uwzględnia wiele różnych przypadków, które mogłoby dać nieprzewidziane wyniki w innych implementacjach:

  1. oto DESZYFR :zaszyfr :klucz1 :klucz2
  2.   niech "lista []
  3.   powtórz (długość :zaszyfr) [
  4.     niech "listael []
  5.     niech "el element npw :zaszyfr
  6.     jeśli (samogłoska? DESZYFR_znak :el :klucz1) [
  7.       niech "listael nak DESZYFR_znak :el :klucz1 :listael
  8.     ]
  9.     jeśli nie (samogłoska? DESZYFR_znak :el :klucz2) [
  10.       niech "listael nak DESZYFR_znak :el :klucz2 :listael
  11.     ]
  12.     jeśli(długość :listael = 0) [
  13.       wynik []
  14.     ]
  15.     niech "lista_nowa []
  16.     jeżeli (puste? :lista) [
  17.       powtórz (długość :listael) [
  18.         niech "el element npw :listael
  19.         niech "lista_nowa nak :el :lista_nowa
  20.       ]
  21.     ][
  22.       powtórz (długość :listael) [
  23.         niech "el element npw :listael
  24.         powtórz (długość :lista) [
  25.           niech "sł (słowo (element npw :lista) (:el))
  26.           niech "lista_nowa nak :sł :lista_nowa
  27.         ]
  28.       ]
  29.     ]
  30.     niech "lista :lista_nowa
  31.   ]
  32.   wynik :lista
  33. już

(2.) Na początek deklarujemy pustą liste. (3.) Dla każdej litery w zaszyfrowanym słowie: (4.) deklarujemy kolejną pustą listę, która przechowa wszystkie możliwe wyjściowe znaki danego znaku. (5.) Pobieramy kolejny element z słowa i zapisujemy do zmiennej :el. (6.) Jeśli po deszyfrowaniu :klucz1 wyjdzie samogłoska to (7.) należy ją dopisać na listę :listael. (9.) Analogicznie dla spółgłosek: jeśli po deszyfrowaniu :el :klucz2 wyjdzie spógłoska (czyli nie samogłoska) to (10.) należy ją dodać na :listael.

Na tym etapie :listaael może pusta. (12.) W takim przypadku należy: (13.) zwrócić pustą listę jako wynik całej funkcji, ponieważ dany znak nie mógł zostać zaszyfrowany przy pomoc ani jednego klucza. (15.) Jeśli jednak istnieje choć jeden znak na liście to (15.) deklarujemy pustą nową listę wynikową. (16.) Jeśli dotychczasowa lista wynikowa była pusta to oznacza, że dopiero sprawdzamy pierwszy znak. Wtedy (17. - 20.) wystarczy przepisać elementy z :listaael do :lista_nowa.

Jednak, gdy już lista coś zawiera to znaczy, że przeglądamy nie pierwszy znak. Wtedy (22.) dla każdej możliwej litery przy deszyfrowaniu: (23.) pobieramy ten element i (24. - 27) tworzymy z nim wszystkie możliwe teksty z tekstami na dotychczasowj liście wynikowej. (30.) Na koniec nową listę ustlamy jako końcową listę :lista. Po przejrzeniu wszystkich elementów (32.) należy zwrócić :lista.

Zadanie 4

Zdefiniuj funkcję LKS :słowo, której daną jest słowo składające się z małych liter alfabetu łacińskiego i cyfr. Wynikiem funkcji jest lista, której kolejne elementy odpowiadają kolejnym znakom danej. Litery kodujemy listami: literę a - listą pustą, literę b - listą składającą się z listy pustej, literę c - listą [[[]]], itd. według pozycji poszczególnych liter w alfabecie. Cyfry danej :słowo są bezpośrednio umieszczane w wyniku - bez kodowania.

Oto przykładowe wyniki:

LKS "c3ba[[[[]]] 3 [[]] []]
LKS "a37ba[[] 3 7 [[]] []]
LKS "d[[[[[]]]]]

Główna funkcja

  1. oto LKS :słowo
  2.   niech "w (lista)
  3.   powtórz (długość :słowo) [
  4.     niech "el (element npw :słowo)
  5.     jeśli nie(liczba? :el)[
  6.       niech "el LKS_pom :el
  7.     ]
  8.     niech "w nak :el :w
  9.   ]
  10.   wynik :w
  11. już

(2.) Początkowo lista wynikowa jest pusta. Potem (3.) dla każdego elementu słowa: (4.) pobieramy kolejny element. (5.) Jeśli nie jest cyfrą to (6.) zamieniamy go na listę list przy pomocy funkcji pomocniczej. (8.) Niezależnie od tego co znajduje się w :el dopisujemy go na listę wynikową. Po zakończeniu pętli (10.) zwracamy listę :w.

Generowanie listy list

Funkcja działa rekurencyjnie. (2.) Jeśli wykryje, że kodowany jest znak "a to zwróci (3.) pustą listę. Jednak dla każdej innej litery (5.) zwróci listę, która będzie zawierać listę dla znaku wcześniejszego w alfabecie. W ten sposób rekurencja zawsze będzie zbiegać do litery "a, a więc będzie skończona. W przypadku wywołania procedury dla znaku o numerze ASCII poniżej 97 program może zwrócić różne wyniki.

  1. oto LKS_pom :znak
  2.   jeśli (:znak = "a) [
  3.     wynik (lista)
  4.   ]
  5.   wynik (lista LKS_pom znak((ascii(:znak))-1))
  6. już