Strona główna » Poradniki » Logomocja » LOGIA » Logia 1998/99 - Etap II

Logia 1998/99 - Etap II

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

Zadanie 1

Zdefiniuj funkcję z parametrem SUMAJEDNOCYFROWA :liczba, której wartością będzie cyfra. Funkcja powinna liczyć sumę cyfr parametru :liczba, następnie sumę cyfr policzonej sumy, itd. aż suma będzie cyfrą. Zakładamy, że parametr :liczba jest liczbą całkowitą. Oto przykładowe wyniki:

SUMAJEDNOCYFROWA 12356ma wartość 8
SUMAJEDNOCYFROWA 0ma wartość 0
SUMAJEDNOCYFROWA 123ma wartość 6
SUMAJEDNOCYFROWA 987656789ma wartość 2

Program najlepiej rozwiązać metodą rekurencji. Funkcja SUMAJEDNOCYFROWA będzie zliczać sumę cyfr, a jeśli ostateczna suma nie jest pojedynczą cyfrą to funkcja zwróci wynik jej ponownego wykonanie z tą różnicą, że za :liczba będzie podstawiona wyliczona suma.

  1. oto SUMAJEDNOCYFROWA :liczba
  2.   jeśli (:liczba < 10) [
  3.     wynik :liczba
  4.   ]
  5.   niech "s 0
  6.   dopóki [:liczba > 0][
  7.     niech "s :s +reszta :liczba 10
  8.     niech "liczba int(:liczba / 10)
  9.   ]
  10.   wynik SUMAJEDNOCYFROWA :s
  11. już

(2.) Jeśli podana :liczba jest jednocyfrowa to (3.) funkcja może zwrócić :liczba. W przeciwnym wypadku (5.) ustalamy sumę cyfr s na 0 i (6. - 10.) sumuje wszystkie cyfry. (11.) Wynikiem działania funkcji jest wywołanie funkcji SUMAJEDNOCYFROWA z argumentem :s.

Zadanie 2

Napisz procedurę z parametrem KARTKI :wyraz, która utworzy możliwie duży rysunek pliku kartek. Parametr :wyraz to słowo pisane wyłącznie małymi literami i nie dłuższe niż 32 znaki. Stosik ma mieć tyle kartek ile liter ma słowo. Pierwszej literze odpowiada kartka na wierzchu. Spółgłoski są reprezentowane przez białe kartki a samogłoski przez czarne. Odległość między skrajnymi kartkami jest stała i równa długości boku kartki. Druga krawędź kartki jest rysowana kreską tej samej długości co krawędź przednia oraz jest nachylona do linii poziomej pod kątem 45o. Oto przykładowe wyniki wywołania procedury: KARTKI "i, KARTKI "nic oraz KARTKI "abrakadabrahokuspokus.

Obrazek 1 do zadania 2

W celu zrozumienia w jaki sposób działa procedura KARTKI warto sprawdzić wyjaśnienie zadania 2 z poprzedniego etapu. Do rozwiązania bieżącego zadania należy dopisać nową funkcję samogłoska?, która zwróci czy dana :litera jest samogłoską.

  1. oto samogłoska? :litera
  2.   wynik (element? :litera [a e o u i y])
  3. już

Procedura STOSIK_karta będzie teraz przyjmowałą drugi argument :b. Jest to litera, którą ma przedstawić dana kartka. W zależności od tego czy jest samogłoską to (3. - 7.) procedura ustala kolor kartki.

  1. oto STOSIK_karta :a :b
  2.   pw 45
  3.   jeżeli (samogłoska? :b)[
  4.     ukm "czarny
  5.   ][
  6.     ukm "biały
  7.   ]
  8.   wielokąt[
  9.     powtórz 2[
  10.       np :a
  11.       pw 45
  12.       np :a
  13.       pw 135
  14.     ]
  15.   ]
  16.   lw 45
  17. już

Zmiany potrzebne też są w samej głównej procedurze KARTKI. Dany jest tym razem tylko :wyraz, dlatego, aby nie zmieniać całego kodu wystarczy (4.) zadeklarować zmienną :ilekart, która określi ile kartek trzeba narysować. (17.) Dodatkową zmianą jest przekazywanie litery jaką kartka reprezentuje. Procedura rysuje stos od dołu do góry, dlatego należy pamiętać, że trzeba pobierać kolejne litery od końca.

  1. oto KARTKI :wyraz
  2.   niech "h 460
  3.   niech "w 600
  4.   niech "ilekart długość :wyraz
  5.   niech "a :w/(1 + 0.5*pwk(2))
  6.   niech "r 0
  7.   jeśli (:ilekart <> 1)[
  8.     niech "r (:h - :a/2*pwk(2)) / (:ilekart - 1)
  9.   ]
  10.   pod
  11.   ws :h/2
  12.   pw 90
  13.   ws :w/2
  14.   lw 90
  15.   opu
  16.   powtórz :ilekart[
  17.     STOSIK_karta :a element (:ilekart - npw + 1) :wyraz
  18.     pod
  19.     np :r
  20.     opu
  21.   ]
  22. już

Zadanie 3

Dane jest co najmniej dwuliterowe słowo, w którym występują tylko litery a i b. Jeśli założymy, że długość słowa wynosi n, to w każdym takim słowie można wyodrębnić n-1 par sąsiednich liter, np. w słowie aabbab takimi parami są aa, ab, bb, ba. Napisz procedurę NAJCZPAR :wyraz, wypisującą tę parę liter (dwuznakowe słowo), która wśród par sąsiednich liter w parametrze :wyraz występuje najczęściej. Jeśli w słowie jest kilka par liter spełniających ten warunek, to wypisane mają być wszystkie z nich w dowolnej kolejności, w kolejnych wierszach. Oto przykłady:

NAJCZPAR "aabbabpowinno wypisać na ekranie słowo ab
NAJCZPAR "aaabbbaaabbbpowinno wypisać na ekranie słowo aa bb
NAJCZPAR "aapowinno wypisać na ekranie słowo aa
NAJCZPAR "babapowinno wypisać na ekranie słowo ba

Poniższe rozwiązanie działa dla dowolnego słowa tj. niekoniecznie złożonego z samych liter a i b.

  1. oto NAJCZPAR :wyraz
  2.   niech "l_wyr []
  3.   niech "l_licz []
  4.   niech "max 1
  5.   powtórz ((długość :wyraz) - 1)[
  6.     niech "wyr (słowo element npw :wyraz element npw+1 :wyraz)
  7.     niech "i numel :wyr :l_wyr
  8.     jeżeli(:i > 0)[
  9.       niech "l_licz zastąp :i :l_licz ((element :i :l_licz) + 1)
  10.       jeśli (element :i :l_licz > :max)[
  11.         niech "max element :i :l_licz
  12.       ]
  13.     ][
  14.       niech "l_wyr nak :wyr :l_wyr
  15.       niech "l_licz nak 1 :l_licz
  16.     ]
  17.   ]

Zadeklarowanie pustych list (2.) zmienna :l_wyr będzie przechowywać wszystki unikalne dotychczas znalezione pary, a (3.) i-ta wartość na liście :l_licz określi ile razy wystąpił element i-ty z :l_wyr. (4.) W trakcie zwiększania liczników program będzie na bieżąco pamiętał jaka jest maksymalna wartość wśród liczników. (5.) Dla każdej pary liter: (6.) utworzenie słowa z pary liter i (7.) sprawdzenie czy wystepuje na liście :l_wyr. (8.) Jeżeli słowo występuje to (9.) należy zwiększyć odpowiedni licznik i (10. - 12.) zmienić :max jeśli istnieje taka potrzeba. (13.) Jeśli jednak dana para liter nie występuje to (14.) należy dopisać ją na listę i (15.) utworzyć nowy licznik o poczatkowej wartości 1.

  1.   niech "o 1
  2.   powtórz (długość :l_wyr)[
  3.     jeśli ((element :o :l_licz) <> :max)[
  4.       niech "l_wyr bezElNum :o :l_wyr
  5.       niech "l_licz bezElNum :o :l_licz
  6.       zmniejsz "o
  7.     ]
  8.     zwiększ "o
  9.   ]
  10.   wy :l_wyr
  11. już

Druga część kodu polega na usunięciu wszystkich wyrazów, których liczniki nie są równe maksymalnej wartości :max. (18.) W przypadku usuwania elementów z listy nie można polegać na npw, ponieważ po usunięciu kilku elementów indeksy kolejnych się zmieniają, dlatego zadeklarowany zostaje dodatkowy licznik :o. (19.) Dla każdego wyrazu na liście :l_wyr: (20.) Jeśli licznik wskazuje inną wartość niż :max to (21.) usuwany jest element z listy :l_wyr oraz (22.) odpowiadający mu licznik. (23.) Po usunięciu elementu z listy trzeba zmniejszyć indeks :o. (25.) Na koniec każdej iteracji należy niezależnie od potrzeby usunięcia elementu zwiększyć indeks :o. Na koniec (27.) program zwraca zmienną :l_wyr.