Strona główna » Poradniki » Logomocja » LOGIA » Logia 2006/07 - Etap II

Logia 2006/07 - Etap II

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

Zadanie 1

Każdą liczbę naturalną można przedstawić jako sumę liczb 1, 2, 4 oraz 8. Opracowano następujący sposób graficznego kodowania liczb 1, 2, 4 oraz 8:

Zdefiniuj procedurę KODSUM :liczba, rysującą ciąg obrazków odpowiadający danej :liczba, przedstawionej jako najkrótsza (zawierająca najmniej składników) suma liczb 1, 2, 4 oraz 8. Obrazki reprezentujące kolejne kodowane składowe są uporządkowane od lewej do prawej - od tego który reprezentuje największą z liczb do tego który reprezentuje najmniejszą z nich. Co drugi obrazek jest obrócony o 180 stopni. Dana :liczba może przyjmować wartości z zakresu od 1 do 250. Oto przykładowe rysunki:

KODSUM 51
KODSUM 20

Rysunek powinien w całości mieścić się na ekranie, a długość odcinka stanowiącego dolną podstawę powstającej figury ma być równa 500.

Strategia

Rozwiązanie zadania zostanie rozbite na 3 procedury. Pierwsza KODSUM_trojkat będzie rysować trójkąt o zadanym boku :a w taki sposób, że żółw znajdzie się w środku figury. Druga procedura KODSUM_el na podstawie zadanego boku :a oraz wartości :n zamaluje odpowiedni trójkąt na czarno. Z kolei główna procedura wyśrodkuje obrazek i przygotuje listę elementów do narysowania.

Rysowanie trójkątów

  1. oto KODSUM_trojkat :a
  2.   niech "h (:a*pwk(3))/2
  3.   pod
  4.   ws :h/3 lw 90
  5.   ws :a/2
  6.   opu
  7.   powtórz 3 [
  8.     np :a
  9.     pw 120
  10.   ]
  11.   pod
  12.   np :a/2 pw 90
  13.   np :h/3
  14.   opu
  15. już

(2.) Wylicz wysokość w trójkącie równobocznym i (3. - 6.) cofnij się do dolnej podstawy trójkąta w prawy róg. (7. - 10.) Narysuj trójkąt i (11. - 14.) powróć do pozycji wyjściowej.

Rysowanie elementu

  1. oto KODSUM_el :a :n
  2.   niech "h (:a*pwk(3))/2
  3.   pod
  4.   ws :h/6
  5.   opu
  6.   KODSUM_trojkat :a
  7.   pw 180
  8.   KODSUM_trojkat :a/2
  9.   pw 180

(2.) Wylicz wysokość w trójkącie równobocznym. (3. - 5.) Wykonaj korektę ustawienia elementu w szeregu i (6.) narysuj duży oraz (8.) mały trójkąt. W ten sposób narysowana zostaje siatka.

  1.   jeżeli (:n <= 3) [
  2.     pod
  3.     pw (:n-2)*120
  4.     np :a/2
  5.     opu
  6.     zam
  7.     pod
  8.     ws :a/2
  9.     lw (:n-2)*120
  10.     opu
  11.   ][
  12.     zam
  13.   ]
  14.   pod
  15.   np :h/6
  16.   opu
  17. już

(10.) Na podstawie numeru zamalowanego trójkąt określ czy: (11. - 19.) zamalowany ma być jeden z narożnych trójkątów czy (21.) element w środku. (23. - 25.) Powróć tam skąd została rozpoczęta procedura.

Procedura główna

  1. oto KODSUM :liczba
  2.   niech "lista []
  3.   niech "p 4
  4.   niech "wartosc 8
  5.   dopóki [:liczba > 0][
  6.     dopóki [:liczba >= :wartosc][
  7.       niech "lista nak :p :lista
  8.       niech "liczba :liczba - :wartosc
  9.     ]
  10.     niech "p :p - 1
  11.     niech "wartosc :wartosc/2
  12.   ]

Pierwszy etap polega na znalezieniu listy kolejnych elementów, które będą rysowane. W tym celu (2.) deklarowana jest pusta lista oraz dwie zmienne: (3.) :p - służy do przechowywania numeru elementu, który odpowiada (4.) aktualnej wartości zmiennej :wartosc - ta z kolei odpowiada za przechowywanie wartości aktualnego elementu. W pętli (5.) dopóki :liczba jest większa od zera: (6. - 9.) sprawdź ile razy mieści się :wartosc w :liczba. Przy każdej iterazji wykonanej (7.) dopisz numer aktualnego elementu na listę :lista i (8.) pomniejsz liczbę o :wartosc. Kiedy już nie można zdjąć elementów o aktualnej wartości: (7.) zmniejsz numer elementu o 1 i (8.) zmniejsz wartość, której odpowiada dany element.

  1.   niech "n długość :lista
  2.   niech "a 500/((:n + 1)/2)
  3.   niech "w 500 - :a
  4.   pod
  5.   pw 90 ws :w/2
  6.   lw 90
  7.   opu
  8.   powtórz (:n)[
  9.       skieruj (reszta (npw - 1) 2) * 180
  10.       KODSUM_el :a (element npw :lista)
  11.       pod
  12.       skieruj 90 np :a/2
  13.       opu
  14.   ]
  15. już

(13.) Pobierz długość listy i zapisz od zmiennej :n. (14.) Wylicz podstawę pojedynczego elementu i (15.) faktyczną długość obrazka. (16. - 19.) Przejdź na środek lewego elementu. (20. - 26.) W pętli narysuj każdy kolejny element z :lista. W trakcie iteracji (21.) wybierz orientację elementu, (22.) narysuj go i (23. - 25.) przejdź do elementu obok.

Zadanie 2

Zdefiniuj funkcję ILEZ :słowo, której daną jest dowolne słowo.

Wynikiem funkcji jest liczba znaków znajdujących się w tym słowie pomiędzy skrajnymi samogłoskami, tj. pomiędzy pierwszą i ostatnią samogłoską, ale bez tych samogłosek. Uznajemy, że samogłoskami są jedynie znaki: a, e, i, o, u oraz y.

W przypadku braku samogłosek w danej :słowo, wartością funkcji jest -2, a w przypadku gdy w słowie jest tylko jedna samogłoska, wartością funkcji jest -1.

ILEZ "hokuspokusjest 6
ILEZ "kluczjest -1
ILEZ "xxxjest -2

Procedura główna

Strategia polega na przygotowaniu listy pozycji na których występują samogłoski. W ten sposób można łatwo sprawdzić czy występuje odpowiednia ilość samogłosek i jeśli tak to wyliczyć szukaną różnicę.

  1. oto ILEZ :słowo
  2.   niech "pozycje []
  3.   powtórz (długość :słowo) [
  4.     niech "el element npw :słowo
  5.     jeśli (numel :el [a e i o u y] >= 1) [
  6.       niech "pozycje nak npw :pozycje
  7.     ]
  8.   ]
  9.   jeżeli ((długość :pozycje) > 1)[
  10.     wynik (ost :pozycje) - (pierw :pozycje) - 1
  11.   ][
  12.     wynik (długość :pozycje) - 2
  13.   ]
  14. już

(2.) Przygotuj listę :pozycje na indeksy samogłosek w :słowo. (3. - 8.) Dla każdego znaku w :słowo: (4.) pobierz kolejny znak i (5.) sprawdź czy jest samogłoską. Jeśli tak to (6.) dopisz numer powtórzenia na listę (tj. indeks tego znaku.). Po przygotowaniu indeksów (9.) sprawdź jest więcej niż jeden element. Jeśli tak to znaczy, że są conajmniej dwie samogłoski i zwrócona wartość to (10.) ostatnia pozycja minus pierwsza pozycja pomniejszona o jeden. W przciwnym razie (12.) wystarczy zwrócić długość listy :pozycje minus dwa.

Zadanie 3

Zdefiniuj funkcję SUMAS :s1 :s2, są dwa niepuste słowa, mogące składać się tylko z 10 pierwszych małych liter alfabetu łacińskiego (tj. a, b, c, d, e, f, g, h, i, j). Poszczególne znaki danych słów są zakodowanymi cyframi dziesiętnymi, w ten sposób, że kolejnym literom alfabetu odpowiadają cyfry od 0 do 9. Wynikiem funkcji jest słowo będące kodem sumy zakodowanych liczb. Zakładamy poprawność danych :s1 i :s2.

SUMAS "j "jjest "bi
SUMAS "baab "jjjjest "caaa

Strategia

Każda litera reprezentuje inną cyfrę. Zadania można rozwiązać na dwa sposoby. Pierwszy z nich, który został przedstawiony poniżej, zamienia liczbę zapisaną literami na cyfry. Potem operacja dodawania zostaje wykonana na liczbach, a nie słowach. Suma zostaje zakodowana i zwrócona jako wynik. Drugi sposób polega na napisaniu funkcji, która potrafi dodawać litery. Tego typu rozwiązanie jest krótsze, ale może okazać się mało czytelne dla osób nie wtajemniczonych odpowiednio w algorytmy.

Rozkodowywanie

  1. oto SUMAS_rozkoduj :s
  2.   niech "znaki [a b c d e f g h i j]
  3.   niech "a 0
  4.   niech "p 1
  5.   niech "n długość :s
  6.   powtórz (:n) [
  7.     niech "el element (:n - npw + 1) :s
  8.     niech "a :a + :p * ((numel :el :znaki) - 1)
  9.     niech "p :p * 10
  10.   ]
  11.   wynik :a
  12. już

(2.) Przygotuj listę na podstawie, której będzie określana wartość znaków. Znak na i-tej pozycji ma wartość i - 1. (3.) ustal początkową wartość liczby na 0 oraz (4.) mnożnik pierwszej "cyfry" na 1. (5.) Pobierz długość cyfry. (6. - 10.) Dla każdej litery: (7.) pobierz kolejną literę od końca i (8.) dodaj jej wartość pomnożoną przez mnożnik do :a. (9.) Zwiększ mnożnik. Na koniec (11.) zwróć wyliczoną liczbę :a.

Kodowanie

  1. oto SUMAS_zakoduj :l
  2.   niech "znaki [a b c d e f g h i j]
  3.   niech "w "
  4.   dopóki[lub (:l > 0) (puste? :w)] [
  5.     niech "numer_el (reszta :l 10) + 1
  6.     niech "w nap (element :numer_el :znaki) :w
  7.     niech "l int(:l / 10)
  8.   ]
  9.   wynik :w
  10. już

(2.) Przygotuj listę na podstawie, której będzie określana wartość znaków. (3.) Przygotuj zmienną do zapisu danych. W pętli (4. - 8.) pobieraj kolejne cyfry: (5.) pobierz cyfrę z :l, (6.) dopisz odpowiednią literę do zmiennej wynikowej i (7.) usuń cyfrę z :l. Na koniec (9.) zwróć zmienną :w.

Funkcja główna

  1. oto SUMAS :s1 :s2
  2.   niech "a SUMAS_rozkoduj :s1
  3.   niech "b SUMAS_rozkoduj :s2
  4.   wynik SUMAS_zakoduj (:a + :b)
  5. już

Funkcje może nie były łatwe do napisania, ale dzięki nim napisanie funkcji głównej jest bardzo łatwo. Wystarczy wyliczyć wartość (2.) słowa pierwszego oraz (3.) drugiego. Na koniec (4) zwróć zakodowaną sumę liczb :a i :b.