Strona główna » Poradniki » Logomocja » LOGIA » Logia 2005/06 - Etap III
 

Logia 2005/06 - Etap III

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

Zadanie 1 (pary liczb trójkątnych)

Na II etapie konkursu jedno z zadań dotyczyło liczb trójkątnych. Dla przypomnienia, rysunki obok przedstawiają graficzną ilustrację kolejnych liczb trójkątnych.

Obrazek 1 do zadania 1

Napisz funkcję NATR :ll, której daną jest lista dodatnich liczb całkowitych nie większych niż 200. Wynikiem funkcji jest lista par liczb przedstawiających liczby danej :ll jako sumy dwóch liczb trójkątnych. Nie każda liczba da się przedstawić jako suma dwóch liczb trójkątnych, wówczas takiej liczbie odpowiada lista pusta. Dla niektórych liczb istnieje więcej niż jedna taka para, wówczas na liście wynikowej może wystąpić dowolna z tych par. Kolejność liczb w obrębie pary jest także dowolna.

NATR [94 2 3 4 5 30 81]powinno dać wynik [[3 91][1 1][][1 3][][15 15][78 3]]
lub [[66 28][1 1][][3 1][][15 15][66 15]]
lub [[66 28][1 1][] [3 1][][15 15][45 36]]

Strategia

Algorytm tworzy listę liczb trójkątnych, a następnie próbuje znaleźć dwie liczby, których suma wynosi tyle co zadana liczba. Początkowo (2.) lista liczb trójkątnych zawiera tylko pierwszą z nich 1.

  1. oto NATR :ll
  2.   niech "wartosci [1]
  3.   niech "w []
  4.   powtórz (długość :ll) [
  5.     niech "el element npw :ll
  6.     dopóki[ost :wartosci < :el][
  7.       niech "dl (długość :wartosci) + 1
  8.       niech "wartosci nak (trojkatna (:dl)) :wartosci
  9.     ]
  10.     niech "w nak (szukajTrojki :el :wartosci) :w
  11.   ]
  12.   wynik :w
  13. już

Następnie inicjalizowana jest (3.) lista do której będą dopisywane kolejne wyniki. (4.) Dla każdej liczby: (5.) pobieramy element (jedynie w ramach uproszczenia kodu) i (6. - 9.) w pętli dodawane są kolejne liczby trójkątne tak, aby ostatnia z nich była większa od ostatniej liczby trójkątnej na liście :wartosci. Na koniec każdej iteracji (10.) wywoływana jest funkcja szukajTrojki, a jej wynik dopisywany na koniec listy wynikowej, która (12.) jest zwracana na koniec.

Kolejna liczba trójkątna

Pierwsza funkcja pomocnicza trojkatna :n zwraca n-tą liczbę trójkątną. Jej działanie polega na sumowaniu liczb od 1 do n.

  1. oto trojkatna :n
  2.   niech "s 0
  3.   powtórz (:n) [
  4.     niech "s :s + npw
  5.   ]
  6.   wynik :s
  7. już

Poszukiwanie pary liczb

Utworzona tablica liczb trójkątnych w głównej funkcji jest wykorzystywana w funkcji pomocniczej szukajTrojki :liczba :dane, która przyjmuje dla jakiej liczby :liczba jest szukany rozkład na parę liczb trójkątnych oraz :dane - lista liczb trójkątnych.

  1. oto szukajTrojki :liczba :dane
  2.   niech "i 1
  3.   dopóki[(element :i :dane) < :liczba][
  4.     niech "a element :i :dane
  5.     niech "b :liczba - :a
  6.     jeśli (numel :b :dane > 0) [
  7.       wynik (lista :a :b)
  8.     ]
  9.     zwiększ "i
  10.   ]
  11.   wynik (lista)
  12. już

(2.) Algorytm przeszukuje kolejne indeksy i, dopóki (3.) i-ta wartość na liście jest mniejsza od :liczba, ponieważ para liczb [a b] spełnia a, b < n. W każdej iteracji: (4.) przyjmujemy, że a to i-ta liczba trójkątna i na tej podstawie (5.) wyliczane jest b. Pozostaje sprawdzić teraz (6.) czy :b jest liczbą trójkątną - jeśli jest to musi być na liście, bo a, b < n < max(:dane). W przypadku spełnienia warunku (7.) natychmiast jest zwracana odpowiednia lista. Jeśli nie to (9.) zwiększany jest indeks i i wykonywana jest kolejna iteracja. W przypadku, gdy pętla zostanie zakończona i wcześniej nie zostanie zwrócony żaden wynik to (11.) zwracana jest pusta lista.

Zadanie 2

Haft krzyżykowy - rodzaj haftu, w którym na materiale w formie siatki o jednakowej na całej powierzchni gęstości oczek (kanwie) wykonuje się tzw. "krzyżyki". Są to podstawowe elementy haftu krzyżykowego. Powstają one przez przeplecenie kolorowej nici przez oczko kanwy, a następnie wykonanie tego samego w taki sposób, aby kolejna część nitki pokryła poprzednią, przecinając ją pod kątem prostym (krzyżyk).

Napisz procedurę HAFT :ll, której daną jest niepusta lista nieujemnych liczb całkowitych. Procedura tworzy rysunek kwadratowego elementu wyszywanego w dwóch kolorach - czerwonym i czarnym; miejsca niewyszywane przedstawiamy za pomocą jasnoszarych krzyżyków. Przyjrzyj się poniższym przykładom i wywnioskuj, jaka reguła rządzi powstawaniem rysunków.

Są to wyniki wywołania HAFT [0 1 2 3 4 5 6 7 8], HAFT [26 16 3] oraz HAFT [1512 18168 50288 49532 49208 18600 16728 49640 50324 13128]

Obrazek 1 do zadania 2

Każda liczba na liście jest zaszyfrowanym opisem jednego wiersza krzyżyków. Wielkość kwadratowego motywu jest określona przez długość listy :ll. Rysunek musi mieścić się w całości na ekranie i wykorzystywać co najmniej 3/4 wysokości ekranu. Maksymalna długość listy wynosi 50, wartości liczb zależą od długości listy i zawsze są prawidłowe.

Reguła

W zadaniu można zauważyć, że każdy krzyżyk występuje w trzech stanach. Każdy wiersz opisuje liczba, więc prawdopodobne, że liczbę należy przeliczyć na odpowiedni system. W tym przypadku jest to system trójkowy. Wtedy cyfra 0 to kolor szary, 1 czerwony, a 2 czarny.

Mylący może okazać się fakt, że po przeliczeniu np. liczby 710 na system trójkowy otrzyma się 213, a taka liczba ma tylko dwie cyfry. Należy jednak pamiętać, że w dowolnym systemie dopisanie nieskończonej ilości zer na początku nie zmienia jej wartości, więc dla pierwszego przykładu z przodu 213 można dopisać siedem zer, aby otrzymać liczbę dziewięcio cyfrową opisującą przedostatni wiersz: 0000000213.

W rozwiązaniu zostało przyjęte, że liczba podczas przeliczania jest zamieniana na listę cyfr co upraszcza proces odczytywania danych o liczbie. Funkcja naTrojkowa :wartosc :dl przyjmuje dwa argumenty: :wartosc, która określa przeliczaną wartość oraz :dl - jak długa ma być lista wynikowa tj. ile cyfr opisuje wiersz.

  1. oto naTrojkowa :wartosc :dl
  2.   niech "p 1
  3.   powtórz (:dl - 1) [
  4.     niech "p :p * 3
  5.   ]
  6.   niech "lista []
  7.   powtórz (:dl) [
  8.     niech "w int(:wartosc / :p)
  9.     niech "wartosc :wartosc - :w * :p
  10.     niech "lista nak :w :lista
  11.     niech "p :p / 3
  12.   ]
  13.   wynik :lista
  14. już

(2. - 5.) Oblicz maksymalną potęge. (6.) Przygotuj pustą listę do której dopisywane będą cyfry. (7. - 12.) W celu wyliczenia cyfr: (8.) sprawdź ile razy mieści się potęga, (9.) pomniejsz pozostałą wartość do przeliczenia, (10.) dopisz na koniec listy wyliczoną cyfrę i (11.) zmniejsz stopień potęgi liczby. Na koniec (13.) zwróć wyliczoną listę cyfr.

Rysowanie

Zadanie tego nie stwierdza, ale w rozwiązaniu pisak zostaje specjalnie pogrubiony, aby kreski były widoczne.

  1. oto HAFT :ll
  2.   ugp 4
  3.   niech "dl długość :ll
  4.   niech "a 420 / :dl
  5.   pod
  6.   np :a * ((:dl - 1) / 2) pw 90
  7.   ws :a * ((:dl - 1) / 2) lw 90
  8.   opu

(2.) Powiększ pisak. (3.) Pobierz długość listy i (4.) oblicz szerokość kwadratu w który będzie wpisany krzyżyk. (5. - 8.) Przejdź do lewego górnego rogu, aby rozpocząć rysowanie.

  1.   powtórz (:dl) [
  2.     niech "wiersz (naTrojkowa (element npw :ll) (:dl))
  3.     powtórz (:dl) [
  4.       niech "wartosc (element npw :wiersz)
  5.       ukp (element (:wartosc + 1) ["szary11 "czerwony "czarny])
  6.       lw 45
  7.       powtórz 4 [
  8.         np (:a * pwk(2)) / 2
  9.         ws (:a * pwk(2)) / 2
  10.         pw 90
  11.       ]
  12.       pw 135
  13.       pod
  14.       np :a lw 90
  15.       opu
  16.     ]
  17.     pod
  18.     pw 90 ws :a * :dl
  19.     lw 90 ws :a
  20.     opu
  21.   ]
  22.   ugp 1
  23. już

(9.) Dla każdego kolejnego wiersza: (10.) oblicz listę cyfr i (11.) przejdź do rysowania krzyżyków. (12.) Pobierz cyfre z odpowiedniej pozycji i (13.) na tej podstawie określ kolor pisaka. (14. - 20.) Narysuj krzyżyk i (20. - 23.) przejdź do rysowani kolejnego. Po narysowaniu wiersza (25. - 28.) wróć do pierwszego krzyżyka od lewej wiersz niżej. (30.) Na koniec przywróć domyślny rozmiar pisaka.

Zadanie 3

Na kwadratowym trawniku o rozmiarach 20×20 położono prostokątne maty. Ułożenie każdej maty i jej rozmiar opisujemy za pomocą czterech liczb całkowitych z zakresu od 0 do 20: [x1 y1 x2 y2], gdzie [x1 y1], [x2 y2] to współrzędne dwóch przeciwległych wierzchołków prostokąta. Zakładamy, że x1 ≤ x2 oraz y1 ≤ y2. Mata [0 0 20 20] pokrywa cały trawnik, mata [10 10 20 20] - jego "górną prawą" ćwiartkę. Układ mat można zapisać w postaci listy opisów mat, np. [[10 10 20 20] [0 0 20 10] [8 8 12 12]].

Zdefiniuj funkcję NIEPOKRYTE :um, której wynikiem - dla danego układu mat :um - jest liczba określająca pole powierzchni nieprzykrytej części trawnika.

NIEPOKRYTE [[10 10 20 20] [0 0 20 10] [8 8 12 12]]96

Strategia

Strategia w rozwiązaniu polega na utworzeniu dużej tablicy 20x20, a następnie zaznaczaniu pól, któe już zostało odliczone. W ten sposób unikany jest problem z liczeniem podwójnie zajętego obszaru.

  1. oto NIEPOKRYTE :um
  2.   niech "mapa []
  3.   powtórz (20) [
  4.     niech "wiersz []
  5.     powtórz 20 [
  6.       niech "wiersz nak 0 :wiersz
  7.     ]
  8.     niech "mapa nak :wiersz :mapa
  9.   ]
  10.   niech "niepokryte 400

(2. - 9.) Pierwsza część kodu polega na utworzeniu mapy terenu, gdzie będą odznaczane odwiedzone pola. Poczatkowo wszystkie pola mają wartość 0. Przed przystąpieniem do odznaczania (10.) wiadomo, że niepokrytych jest 400 pól.

  1.   niech "niepokryte 400
  2.   powtórz (długość :um) [
  3.     niech "mata (element npw :um)
  4.     niech "y (element 2 :mata) + 1
  5.     dopóki [:y <= (element 4 :mata)][
  6.       niech "wiersz :y
  7.       niech "x (element 1 :mata) + 1
  8.       dopóki [:x <= (element 3 :mata)][
  9.         jeśli (element :x (element :wiersz :mapa) = 0) [
  10.           zmniejsz "niepokryte
  11.           niech "mapa zastap :mapa :y :x 1
  12.         ]
  13.         zwiększ "x
  14.       ]
  15.       zwiększ "y
  16.     ]
  17.   ]
  18.   wynik :niepokryte
  19. już

(11.) Dla każdego elementu listy: (12.) pobierany jest element i na jego podstawie: (13.) określana pozycja Y obszaru wyjściowego oraz (14.) ile wynosi pozycja Y końcowa dla danej maty. (15.) Podczas odznaczania każdego wiersza pobierz go i określ (16. - 17.) współrzędne X po jakich należy odznaczać pola. (18. - 21.) Jeśli dane pole o współrzędnych (:x, :y) nie zostało jeszcze odkryte (czyli wartość wynosi 0) to (19.) zmniejsz liczbę nieodkrytych pól i (20.) odznacz pole. Na koniec (27.) zwróć ile jest niepokrytych pól.

Funkcja pomocnicza

W funkcji NIEPOKRYTE wykorzystana jest funkcja zastap :mapa :y :x :naco, która zastępuje pozycję w punkcie (:x, :y) w :mapa na :naco. Ma to na celu uproszczenie zapisu kodu.

  1. oto zastap :mapa :y :x :naco
  2.   niech "wiersz element :y :mapa
  3.   niech "wiersz zastąp :x :wiersz :naco
  4.   niech "mapa zastąp :y :mapa :wiersz
  5.   wynik :mapa
  6. już

Zadanie 4

Szyfr Cezara polega na zastąpieniu każdego kolejnego znaku szyfrowanego tekstu znakiem występującym w alfabecie o określoną liczbę pozycji dalej, cyklicznie (tj. jeśli wykraczamy poza alfabet, to kolejne znaki bierzemy z początku alfabetu). Nasz alfabet będzie składał się z małych liter alfabetu łacińskiego oraz spacji. Przyjmujemy, że spacja jest następnym znakiem po literze z.

Napisz funkcję SZYFR :ls :klucz, której danymi są :ls - lista słów składających się z małych liter alfabetu łacińskiego oraz liczba naturalna :klucz. Wynikiem funkcji jest lista słów składających się z małych liter alfabetu łacińskiego powstała po zaszyfrowaniu danej :ls szyfrem Cezara o kluczu :klucz. Kodowaniu podlegają także odstępy pomiędzy słowami. Dwa sąsiednie znaki szyfrowanego tekstu nie mogą być identyczne. Gdyby skrajne (pierwszy bądź ostatni) znaki kodowanego tekstu miały być zaszyfrowane jako spacja, to są pomijane w wyniku.

SZYFR [hokus pokus abrakadabra] 26[gnjtrzonjtrz aq j c aq]
SZYFR [zuzia je szczaw] 1[v jbakfat d bx]

Strategia

Szyfr Cezara jest tematem bardzo często poruszanym i bardzo często pojawia się w zadaniach konkursowych. W tym przypadku dodanie znaku spacji do alfabetu nie powinno stanowić problemu. Trudnością może okazać się tutaj podzielenie zaszyfrowanego słowa na listę.

Po pierwsze algorytm wstępna listą powinien zamienić na słowo i to słowo zaszyfrować. W celu podzielenia na listę wystarczy zczytywać kolejne znaki szyfrogramu, aż do napotkania znaku spacji. Wtedy zczytane dotychczas znaki, pomijając znak spacji, należy dołączyć jako element do listy wynikowej. Oczywiście przed dodaniem należy upewnić się, że aktualnie odczytany ciąg znaków nie jest pusty.

Problem może pojawić się kiedy na końcu nie wystąpi spacja. Wtedy ostatnie znaki nie zostna odczytane i należałoby to obsłużyć dodatkowo po zakończeniu odczytywania znaków. Rozwiązaniem tego problemu jest dodanie na koniec szyfrowanego tekstu znaku, który zamieni się na spację. Zgodnie z treścią zadania taki znak i tak nie powinien być uwzględniany, więc i tak zostanie usunięty.

Kod

Pierwsz etap działania funkcji polega na przygotowania alfabetu i zamianie listy na słowo ze spacjami.

  1. oto SZYFR :ls :klucz
  2.   niech "alfabet (słowo "abcdefghijklmnopqrstuvwxyz (znak 32))
  3.   niech "klucz reszta :klucz (długość :alfabet)
  4.   niech "s pierw :ls
  5.   powtórz ((długość :ls) - 1) [
  6.     niech "s (słowo :s (znak 32) (element (npw + 1) :ls))
  7.   ]
  8.   niech "s (słowo :s (element ((długość :alfabet) - :klucz) :alfabet))
  9.   niech "bufor "
  10.   niech "w []

(2.) Określ alfabet i (3.) uprość klucz tak jak to tylko możliwe. (4. - 7.) Połącz wszystkie słowa na liście tak, aby razem utworzyły jedno słowo. (8.) Dopisz na końcu znak, który zamieni się na spację po zaszyfrowaniu. Przed kolejnym etapem (9.) utwórz :bufor, któy przechowa odczytywane kolejne znaki oraz listę :w, która będzie przechowywać kolejne odczytane słowa.

  1.   niech "w []
  2.   powtórz (długość :s) [
  3.     niech "pos (numel (element npw :s) :alfabet) - 1
  4.     niech "pos :pos + :klucz
  5.     niech "pos (reszta :pos (długość :alfabet)) + 1
  6.     jeżeli ((element :pos :alfabet) = (znak 32)) [
  7.       jeśli (nie puste? :bufor) [
  8.         niech "w nak :bufor :w
  9.         niech "bufor "
  10.       ]
  11.     ][
  12.       niech "bufor (słowo :bufor (element :pos :alfabet))
  13.     ]
  14.   ]
  15.   wynik :w
  16. już

(11.) Dla każdego kolejnego znaku w wyznaczonym słowie: (12.) sprawdź pozycję elementu na liście, (13.) dodaj przesunięcie i (14.) oblicz pozycję w alfabecie zaszyfrowanego znaku. (15.) W przypadku, gdy zaszyfrowany znak to spacja to (16. - 19.) dopisz :bufor na listę pod warunkiem, że nie jest pusty. (20. - 22.) W przeciwnym razie odczytany znak dopisz do buforu. Na koniec (24.) zwróć utworzoną listę :w.