Strona główna » Poradniki » Logomocja » LOGIA » Logia 1999/00 - Etap III
 

Logia 1999/00 - Etap III

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

Zadanie 1

MAZOWIECKI URZĄD SZYFRÓW posługuje się (do zapisywania tajnych informacji) alfabetem składającym się tylko z 16 znaków - małych liter od a do p. W celu usprawnienia przetwarzania dokumentów utworzył własny system cyfrowego kodowania znaków, tzw. kod MKI, w którym każdej literze odpowiada czterobitowe słowo (patrz tabela).

Ustalano następujący system szyfrowania znaków, słów oraz zdań:

  1. Szyfrem znaku x (gdzie x oznacza dowolny znak od a do p) jest taki znak, którego kod MKI jest symetrycznym odbiciem (przestawieniem wspak) kodu znaku x.
  2. Szyfrem słowa s jest takie słowo, którego każdy znak jest szyfrem odpowiedniego znaku słowa s.
  3. Szyfrem zdania z (listy słów) jest takie zdanie, którego każde słowo jest szyfrem odpowiedniego słowa zdania z.

Znakabcdefghijklmnop
Kod0000000100100011010001010110011110001001101010111100110111101111

Zdefiniuj funkcję SZYFR :zd, której wynikiem dla dowolnego zdanie utworzonego ze słów w alfabecie od a do p jest szyfr tego zdania utworzony zgodnie z ustalonymi wyżej zasadami.

Przykładowe wyniki:

SZYFR [ala nie ela]powinno dać wynik [ana lbc cna]
SZYFR [moja lalka]powinno dać wynik [dhja nanfa]

Strategia

Jak można zuważyć każda kolejna litera odpowiada jej pozycji zapisanej przy pomocy kodu binarnego. Przedstawione poniżej rozwiązanie omija to poprzez zadeklarowanie dwóch list, które odpowiadają dwóm wierszom tabeli. Należy jednak pamiętać, że takie rozwiązanie choć szybsze w napisaniu to okazuje się mało praktyczne jeśli zmieni się polecenie zadania.

  1. oto SZYFR :zd
  2.   niech "l1 "abcdefghijklmnop
  3.   niech "l2 [0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111]
  4.   niech "w []
  5.   powtórz (długość :zd) [
  6.     niech "s element npw :zd
  7.     powtórz (długość :s) [
  8.       niech "kod element (numel (element npw :s) :l1) :l2
  9.       niech "s zastąp npw :s element (numel (wspak :kod) :l2) :l1
  10.     ]
  11.     niech "w nak :s :w
  12.   ]
  13.   wynik :w
  14. już

Zapamiętaj (2.) kolejne litery oraz (5.) ich binarną reprezentację. (4.) Przygotuj listę wynikową. (5.) Dla każdego słowa: (6.) pobierz zamieniany element ze zdania, a następnie (7.) dla każdej litery w słowie: (8.) znajdź jego kod, a następnie (9.) zastąp kolejną literą odpowiednim elementem. (11.) Zmodyfikowane słowo dopisz na listę wynikową. (13.) Zwróć wynik.

Uwagi do rozwiązania

Nietrudno zauważyć, że listy :l1 i :l2 są niepotrzebne. Wystarczy dodatkowo funkcja, która zwróci numer pozycji pobranego znaku w alfabecie oraz zwróci k-ty znak. W celu uniknięcia korzystania z listy :l2 należałoby napisać funkcje, która zamienia liczbę na postać binarną i dekoduje postać binarną.

Zadanie 2

Dwie przekątne kwadratu dzielą go na cztery ćwiartki. Zamalowując różne kombinacje tych ćwiartek możemy otrzymać 16 różnych wzorów, których możemy używać jako wizualnych kodów flagowych 16 elementowego alfabetu od a do p. Ustalamy następujący system wizualnego kodowania liter alfabetu od a do p w postaci flag.

Obrazek 1 do zadania 2

Kodem flagowym słowa będzie odpowiednia sekwencja kodów flagowych kolejnych znaków. Kodem flagowym zdania będzie sekwencja, umieszczonych kolejno jeden pod drugim i wyrównanych do lewego brzegu kodów słów tworzących zdanie.

Zdefiniuj procedurę FLAGI :zd, która dla dowolnego danego zdania :zd wyświetla na środku ekranu jego kod na tle szarego prostokąta. Zakładamy, że dane zdanie będzie się składać z co najmniej jednego i co najwyżej ośmiu słów, a każde słowo z co najmniej jednej i co najwyżej 12 liter z alfabetu od a do p.

Poniższy rysunek przedstawia wynik wywołania FLAGI [ola ma domek].

Obrazek 2 do zadania 2

Strategia

Na poczatek warto przyjrzeć się użytym znaczkom do reprezentacji poszczególnych liter. Warto zauważyć, że jeśli podzieli się kwadrat na ćwiartki i odczyta się kod zaczynając od górnej ćwiartki dookoła w prawo to powstanie np. dla litery d: ccbb (c - czarny, b - biały). Jeśli teraz zamienić białe na 0, a czarne na 1 to otrzymamy 1100 to jest to binarny zapis wstecz numeru pozycji litery f. Warto zauważyć, że w takim razie można napisać funkcję FLAGI_kwa, która przyjmie argument :s, który określi kod obrazka. W ten sposób łatwiej będzie przechować jak ma wyglądać rysunek poszczególnego znaku.

  1. oto FLAGI_kwa :s :a
  2.   powtórz (długość :s)[
  3.     ukp element ((element npw wspak :s) + 1) [biały czarny]
  4.     ukm kolPis
  5.     wielokąt[
  6.       lw 45
  7.       np (:a/2*pwk(2))
  8.       pw 135
  9.       np :a
  10.       pw 135
  11.       np (:a/2*pwk(2))
  12.       pw 135
  13.     ]
  14.     pw 90
  15.   ]
  16. już

(1.) Ze względu na różną wielkość obrazka prócz kodu :s procedura przyjmuje argument :a, który określa szerokość i wysokość elementu. (2.) Dla każdego 0 oraz 1. (Oczywiście prawidłowy kod ma 4 znaki i składa się z 0 i / lub 1.) (3.) Ustal odpowiedni kolor pisaka i (4.) malowania. (5. - 13.) Narysuj odpowiednią ćwiartkę i (14.) przejdź do rysowania następnej.

Rysowanie flagi

Procedura FLAGI można podzielić na trzy etapy: wyliczenie rozmiaru oraz przygotowanie list wartości. Następnie rysowanie składa się z narysowania tła, a następnie poszczególnych linijek flagi.

  1. oto FLAGI :zd
  2.   niech "max_wys 400
  3.   niech "max_szer 600
  4.   niech "l1 "abcdefghijklmnop
  5.   niech "l2 [0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111]
  6.   niech "max 0
  7.   niech "margin 4
  8.   powtórz (długość :zd) [
  9.     jeśli (:max < długość element npw :zd)[
  10.       niech "max długość element npw :zd
  11.     ]
  12.   ]
  13.   niech "rozmiarX (:max_szer - :margin * (:max + 1)) / :max
  14.   niech "rozmiarY (:max_wys - :margin * ((długość :zd) + 1)) / (długość :zd)
  15.   jeżeli (:rozmiarX < :rozmiarY) [
  16.     niech "rozmiar :rozmiarX
  17.   ][
  18.     niech "rozmiar :rozmiarY
  19.   ]
  20.   niech "wys (długość :zd) * (:margin + :rozmiar) + :margin
  21.   niech "szer (:max) * (:margin + :rozmiar) + :margin

(2. - 3.) Maksymalne wymiary rysunku oraz (4.) użyty alfabet i (5.) zakodowane reprezentacje graficzne znaków. (i-tej literze odpowiada i-ty kod.) (6.) Zadeklaruj zmienną :max na 0 i (8. - 12.) znajdź nadłuższe słowo i zapamiętaj jego długość. (7.) Ustal margines między kwadratami na 4. Wyliczyć szerokość kwadratu na podstawie (13.) szerokości oraz (14.) wysokości. (15. - 19.) Jako ostateczny rozmiar przyjmij mniejszą z wyliczonych wartości. Dopiero na podstawie szerokosci kwadratu wylicz (20.) wysokość i (21.) szerokość tła.

  1.   pod
  2.   ws :wys/2
  3.   pw 90
  4.   ws :szer/2
  5.   lw 90
  6.   opu
  7.   wielokąt [
  8.     ukp "szary
  9.     ukm "szary
  10.     powtórz 2[
  11.       np :wys
  12.       pw 90
  13.       np :szer
  14.       pw 90
  15.     ]
  16.   ]

(22. - 27.) Przejdź do lewego, dolnego rohu szarego tła i (28. - 37.) je narysuj.

  1.   pod
  2.   np :rozmiar/2 + :margin
  3.   pw 90
  4.   np :rozmiar/2 + :margin
  5.   lw 90
  6.   opu
  7.   powtórz (długość :zd) [
  8.     niech "s element npw wspak :zd
  9.     powtórz (długość :s) [
  10.       FLAGI_kwa element (numel (element npw :s) :l1) :l2 :rozmiar
  11.       pod
  12.       pw 90
  13.       np :rozmiar + :margin
  14.       lw 90
  15.       opu
  16.     ]
  17.     pod
  18.     pw 90
  19.     ws (długość :s) * (:rozmiar + :margin)
  20.     lw 90
  21.     np :rozmiar + :margin
  22.     opu
  23.   ]
  24. już

(38. - 43.) Z lewego, dolnego rogu rysunku przejdź do lewego, dolnego rogu lewego, dolnego kwadratu. Następnie: (44.) Dla każdego słowa: (45.) pobierz je i przechowaj w zmiennej :s. (46.) Dla każdej litery w pobranym słowie: (47.) narysuj kwadrat i (48. - 52.) przejdź do lewego, dolnego rogu następnego rysowanego kwadratu. (54. - 59.) Po narysowaniu całej lini wróć na początek i przejdź jeden wiersz wyżej.

Uwagi do rozwiązania

Listy :l1 i :l2 tak jak w zadaniu 1 nie są potrzebne, ale znacząco przyśpieszają pisanie kodu. Listy te można zastąpić specjalnymi funkcjami.

Zadanie 3

Jeśli mamy po jednym odważniku o masie 1 kg, 3 kg, 9 kg itd. aż do 3n kg, to możemy na wadze szalkowej odważyć każdy ciężar, którego masa w kg jest liczbą całkowitą z zakresu od 0 do 1 + 3 + .. + 3n i to w dodatku tylko w jeden sposób.

Na przykład, żeby zrównoważyć ciężar 11 kg, trzeba na jednej szali położyć dany ciężar i odważnik 1 kg., a na drugiej szali - odważniki 9 kg i 3 kg.

Zdefiniuj funkcję ZRW :mc, która dla danej masy ciężaru, będącej liczbą całkowitą dodatnią, wyznacza odważniki, które trzeba położyć na szalach wagi, żeby zrównoważyć dany ciężar.Wynikiem funkcji ma być dwuelementowa lista. Pierwszym jej elementem powinna być lista mas odważników, które należy położyć na jednej szali z odmierzanym ciężarem, a drugim elementem - lista mas odważników, które należy położyć na przeciwnej szali. Obie te listy powinny być uporządkowane malejąco.

Oto przykładowe wyniki:

ZRW 101powinno dać wynik [[9 1][81 27 3]]
ZRW 282powinno dać wynik [[][243 27 9 3]]
ZRW 3295powinno dać wynik [[2187 729 243 81 27][6561 1]]
ZRW 243powinno dać wynik [[][243]]

Rozwiązanie niedostępne