Logia 1998/99 - Etap II

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.

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ż

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.

18.   niech "o 1
19.   powtórz (długość :l_wyr)[
20.     jeśli ((element :o :l_licz) <> :max)[
21.       niech "l_wyr bezElNum :o :l_wyr
22.       niech "l_licz bezElNum :o :l_licz
23.       zmniejsz "o
24.     ]
25.     zwiększ "o
26.   ]
27.   wy :l_wyr
28. 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.

• Rozwiązania zadań