Strona główna » Poradniki » Logomocja » LOGIA » Logia 2016/17 Etap II
 

Logia 2016/17 Etap II

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

Zadanie 1

Szyfr Bacona polega na zastępowaniu liter alfabetu łacińskiego pięcioznakowymi ciągami złożonymi z liter a i b zgodnie z poniższą tabelą:

ABCDEFGHI, JKLM
aaaaaaaaabaaabaaaabbaabaaaababaabbaaabbbabaaaabaabababaababb
NOPQRSTU, VWXYZ
abbaaabbababbbaabbbbbaaaabaaabbaababaabbbabaabababbabbababbb

Adaś postanowił szyfrować kolejne litery słowa. Zamiast liter a i b użył odpowiednio zamalowanych kwadratów:

Napisz jednoparametrową procedurę/funkcję szyfruj, po wywołaniu której na środku ekranu powstanie rysunek zaszyfrowanego słowa (od lewej do prawej). Parametrem jest niepuste słowo złożone z wielkich liter alfabetu łacińskiego o maksymalnej długości 70. Szerokość rysunku wynosi 700 lub wysokość wynosi 400. Do zamalowania użyj dwóch dowolnych kolorów różnych od koloru krawędzi kwadratów.

szyfruj ″ GODZINAKODOWANIA

Strategia

Przyjmijmy, że litera a oznacza cyfrę 0, a litera b cyfrę 1. Wtedy każdej literze przyporządkowywujemy jej pozycję w alfabecie pomniejszona o jeden zapisaną binarnie. Przykładowo litera C ma 00010 co w zapisie binarnym to liczba dziesiętna 2, a litera C to trzecia litera alfabetu. W myśl tej zasady litera A ma indeks 0. Oczywiście należy pamiętać, że dla liter położonych dalej niż I zmniejszać indeks o 1, a od litery V pomniejszyć o jeszcze jeden.

Rozwiązanie

Litera na kod

Każda rysowana litera zostaje zamieniona wpierw na kod zero jedynkowy, a dopiero na podstawie kodu wartości są rysowane. W celu zamiany

  1. oto szyfruj_kod :znak
  2.   niech "wartosc (ascii :znak) - (ascii "A)
  3.   jeśli ((ascii :znak) > (ascii "I)) [ zmniejsz "wartosc ]
  4.   jeśli ((ascii :znak) > (ascii "U)) [ zmniejsz "wartosc ]
  5.   niech "s "
  6.   niech "p 16
  7.   dopóki [:p >= 1][
  8.     niech "r int(:wartosc/:p)
  9.     niech "s (słowo :s :r)
  10.     niech "wartosc :wartosc - :r*:p
  11.     niech "p :p / 2
  12.   ]
  13.   wynik :s
  14. już

(2.) Sprawdź pozycję litery w alfabecie i (3. - 4.) skoryguj jej wartość jeśli istnieje taka potrzeba. Następnie (5. - 12.) przelicz liczbę dziesiętną na postać binarną i (13.) zwróć zapis jako tekst. Warto tutaj zauważyć, że niezależnie od wartości zawsze zwracane jest pięć cyfr.

Funkcja główna

Funkcja główna szyfruj początkowo ustala rozmiar pojedynczego kwadracika, a następnie dla każdej litery generuje kod i na jego podstawie rysuje obrazek.

  1. oto szyfruj :słowo
  2.   niech "n (długość :słowo)
  3.   niech "a 80
  4.   niech "w 700/:n
  5.   jeśli (:w < :a) [ niech "a :w ]
  6.   pod
  7.   ws :a*5/2 pw 90
  8.   ws :a*:n/2 lw 90
  9.   opu
  10.   powtórz (:n) [
  11.     niech "el szyfruj_kod element npw :słowo
  12.     powtórz (5) [
  13.       jeżeli (element npw :el = "1) [
  14.         ukm "niebieski
  15.       ][
  16.         ukm "żółty
  17.       ]
  18.       wielokąt [ powtórz 4 [ np :a pw 90 ] ]
  19.       np :a
  20.     ]
  21.     pod
  22.     ws :a*5 pw 90
  23.     np :a lw 90
  24.     opu
  25.   ]
  26. już

(2.) Sprawdź ile jest liter i (3. - 5.) określ rozmiar najmniejszego kwadratu tj. bok :a. (6. - 9.) Przejdź do lewego, dolnego rogu. Następnie (10.) dla każdej litery: (11.) określ jej kod, (12. - 21.) narysuj kolumnę i (22. - 25.) przejdź do następnej.

Zadanie 2

Logolandia ma tylko jedną owalną ulicę, przy której stoją domy podzielone na osiedla. Dwa domy stojące obok siebie są w jednym osiedlu, jeśli różnica ich numerów jest nie większa niż 3. Dom o największym numerze jest w tym samym osiedlu, co dom o numerze 1, 2 lub 3 (o ile istnieje). W Logolandii stoją co najmniej 2 domy, ale nie więcej niż 10 000. Największy numer domu jest nie większy niż 30 000. Numery domów nie powtarzają się.

Napisz jednoparametrową funkcję maksos, której parametrem jest uporządkowana rosnąco lista numerów domów. Wynikiem jest liczba domów w osiedlu składającym się z największej liczby domów.

maksos [1 4 7 11 13 14 15 16 20]jest 5 (osiedle 11-13-14-15-16)
maksos [1 4 7 13 14 15 20]jest 4 (osiedle 20-1-4-7)

Strategia

W celu powiązania ze sobą domów najlepiej, aby lista numerów domu była uporządkowana (rosnąco lub malejąco). Wtedy kolejne domy powinny zostać dokładne na listę tak długo, aż numer poprzedniego domu nie różni się o więcej niż 3. Jeśli się różni to licznik należy zapamiętać i rozpocząć nowe liczenie od aktualnego domu. Na koniec należy wybrać licznik, który ma największą wartość. Uwaga: należy pamiętać, aby sprawdzić czy do pierwszego osiedla pasują domy z końca listy (planasza ma kształt owalu).

Rozwiązanie

W funkcji maksos osiedle o (2.) największej ilości domów jest umieszczone w zmiennej :max, a (3.) w zmiennej :ile aktualna wartość domów w osiedlu.

  1. oto maksos :lista
  2.   niech "max 0
  3.   niech "ile 0
  4.   jeśli ((pierw :lista) <= 3) [
  5.     zwiększ "ile
  6.     niech "lista bo :lista
  7.   ]
  8.   niech "lista nak 0 :lista
  9.   niech "ost pierw :lista
  10.   powtórz (długość :lista) [
  11.     niech "el element npw :lista
  12.     niech "w :el - :ost
  13.     jeżeli (I (:w >= 0) (:w <= 3)) [
  14.       zwiększ "ile
  15.     ][
  16.       jeśli (:ile > :max) [
  17.         niech "max :ile
  18.       ]
  19.       niech "ile 1
  20.     ]
  21.     niech "ost :el
  22.   ]
  23.   wynik :max
  24. już

Zadanie 3

Staś układa na stole sześcienne klocki tej samej wielkości. Na każdym widnieje jedna z wielkich liter alfabetu łacińskiego. Klocki układane są rzędami (wierszami). Każdy rząd rozpoczyna się przy lewej krawędzi stołu. Pierwszy rząd zawiera jeden klocek, drugi – dwa, trzeci – trzy, …, itd. Ostatni rząd może być krótszy.

Napisz jednoparametrową funkcję kolit, której parametrem jest niepuste słowo długości co najwyżej 1 000, zawierające litery widniejące na kolejnych klockach. Wynikiem funkcji jest liczba tych kolumn w układance Stasia, w których wszystkie litery są identyczne.

kolit "ABCDEFGHjest 1 (ostatnia kolumna)
kolit "ALAMAKRABYjest 2 (druga i ostatnia)

Strategia

Zadanie zostanie podzielone na kilka etapów. Pierwszy będzie polegał na podzieleniu słowa na listę znaków w następujący sposób: przygotuj pustą listę. W liście umieść nową pustą listę. Następnie dla każdej listy w głównej liście dopisz kolejny znak ze słowa. Czynność tę powtarzaj dopóki pozostaną niewybrane znaki z słowa. W ten sposób w i-tej liście znajdą się znaki z i-tej kolumny. Następnie wystarczy sprawdzić ile jest list, które mają wszystkie znaki identyczne.

Rozwiązanie

Identyczne elementy?

Do sprawdzenia czy na liście wszystkie elementy są identyczne służy funkcja kolit_sprawdz. Zwraca ona wartość logiczną.

  1. oto kolit_sprawdz :lista
  2.   jeśli (puste? :lista)[ wynik "fałsz ]
  3.   niech "el pierw :lista
  4.   powtórz (długość :lista) [
  5.     jeśli (:el <> element npw :lista) [
  6.       wynik "fałsz
  7.     ]
  8.   ]
  9.   wynik "prawda
  10. już

(2.) Dla pustej liście nie ma żadnego elementu, więc nie mogą być identyczne. Należy wtedy zwrócić fałsz. W przeciwnym wypadku (3.) pobierz pierwszy znak i (4. = 8.) porównaj go z każdym pozostałym elementem. Jeśli choć raz elementy będą się różnić to zwróć fałsz w przeciwnym wypadku (9.) zwróć prawdę.

Funkcja główna

Przed przystąpieniem do obliczeń należy: (2.) przygotować pustę listę i (3.) określić, który znak zostaje wybrany (tj. od pierwszego). Następnie (4. - 14.) podziel słowo na listę elementów w każdej z kolumn i (15. - 20.) policz ile jest list na których elementy są identyczne. Na koniec (21.) zwróć wartość zmiennej :licznik.

  1. oto kolit :słowo
  2.   niech "lista []
  3.   niech "i 1
  4.   dopóki [:i <= (długość :słowo)][
  5.     niech "lista nak [] :lista
  6.     powtórz (długość :lista) [
  7.       jeśli (:i <= (długość :słowo)) [
  8.         niech "el element npw :lista
  9.         niech "znak element :i :słowo
  10.         niech "lista zastąp npw :lista (zd :el :znak)
  11.         zwiększ "i
  12.       ]
  13.     ]
  14.   ]
  15.   niech "licznik 0
  16.   powtórz (długość :lista) [
  17.     jeśli (kolit_sprawdz element npw :lista) [
  18.       zwiększ "licznik
  19.     ]
  20.   ]
  21.   wynik :licznik
  22. już

(2.) Dla pustej liście nie ma żadnego elementu, więc nie mogą być identyczne. Należy wtedy zwrócić fałsz. W przeciwnym wypadku (3.) pobierz pierwszy znak i (4. = 8.) porównaj go z każdym pozostałym elementem. Jeśli choć raz elementy będą się różnić to zwróć fałsz w przeciwnym wypadku (9.) zwróć prawdę.