Logia 2006/07 - Etap III

Zadanie 1 (wykres słowa)

Napisz procedurę WYKS :wyraz, która rysuje na środku ekranu wykres słowa w postaci kwadratu o boku długości 400, składającego się z pewnej liczby prostokątów o tych samych wymiarach. Parametr :wyraz jest niepustym słowem składającym się z małych liter alfabetu łacińskiego, mającym nie więcej niż 40 znaków.

Liczbę prostokątów w poziomie wyliczamy znajdując tę literę słowa :wyraz, która zajmuje najdalszą pozycję w alfabecie (dla litery a jest to 1, dla litery b - 2, dla litery c - 3, ..., dla litery z - 26). Liczba prostokątów w pionie jest równa liczbie wystąpień tej litery słowa :wyraz, która najwięcej razy występuje w tym słowie.

Każde wystąpienie litery jest reprezentowane przez zamalowanie prostokąta. Jeśli litera występuje wielokrotnie, to jest reprezentowana przez ciąg zamalowanych prostokątów w pionie. Skrajny lewy pion odpowiada literze a, skrajny prawy - literze o najdalszej pozycji w alfabecie występującej w słowie :wyraz. W pionie, powyżej pustego prostokąta nie może wystąpić zamalowany.

Poniższe rysunki przedstawiają efekty wywołania dla wybranych wartości:

WYKS "alabama

WYKS "baba

WYKS "celnik

Rozwiązanie

Zadanie można podzielić na dwa główne etapy. Pierwszy z nich polega na przygotowaniu listy danych na podstawie których, w trakcie drugiego etapu, zostanie narysowany wykres słowa.

1. oto WYKS :wyraz
2.   niech "lista []
3.   niech "max 0
4.   powtórz (długość :wyraz) [
5.     niech "poz (ascii (element npw :wyraz)) - 96
6.     dopóki [długość :lista < :poz] [
7.       niech "lista nak 0 :lista
8.     ]
9.     niech "w (element :poz :lista) + 1
10.     niech "lista zastąp :poz :lista :w
11.     jeśli (:w > :max) [
12.       niech "max :w
13.     ]
14.   ]

(2.) Przygotuj pustą listę danych oraz, że (3.) największa ilość wśród wszystkich liter to 0. (4.) W pętli rozpocznij zliczanie kolejnych liter: (5.) określ jej pozycję w alfabecie. (6.) Jeśli lista danych jest za krótka to (7.) dodaj tyle zer, aż będzie istniał licznik dla aktualnej litery. Następnie (9.) pobierz licznik danej litery i zwiększ go. (10.) Zastąp licznik nową wartością. Na koniec każdej iteracji (11.) sprawdź czy dana litera nie ma więcej wystąpień niż obecne maksimum. Jeśli tak to (12.) przypisz maksimum nową wartość.

W tym momencie zmienna :lista przechowuje k elementów, gdzie i-ta wartość odpowiada i-tej literze alfabetu. Tak przygotowana lista może posłużyć do narysowania wykresu. Dodatkowo w trakcie zliczania zmieniana była zmienna :max, więc znana jest ilość wierszy wykresu.

15.   niech "a 400
16.   niech "elw :a/(długość :lista)
17.   niech "elh :a/:max
18.   pod
19.   ws :a/2 pw 90
20.   ws :a/2 lw 90
21.   opu
22.   powtórz (długość :lista) [
23.     niech "w element npw :lista
24.     powtórz (:max) [
25.       jeżeli(npw <= :w) [
26.         ukm "szary
27.       ][
28.         ukm "biały
29.       ]
30.       wielokąt [
31.         powtórz 2 [
32.           np :elh pw 90
33.           np :elw pw 90
34.         ]
35.       ]
36.       np :elh
37.     ]
38.     ws :elh*:max pw 90
39.     np :elw lw 90
40.   ]
41. już

Na podstawie (15.) podanego boku w zadaniu oblicz (16.) szerokość i (17.) wysokość pojedynczego prostokątu na rysunku. Następnie (18. - 21.) przejdź do lewego dolnego rogu planszy. Narysuj (22.) k kolumn. Na początku każdej iteracji (23.) zapamiętaj wartość licznika dla rysowanej kolumny. (24.) Narysuj :max wierszy w kolumnie. (25. - 29.) W trakcie rysowania określ kolor zamalowania na podstawie numeru powtórzenia oraz zapamiętanej wartości licznika. (30. - 35.) Narysuj prostokąt i (36.) przejdź do następnegow górę. Po narysowaniu całej kolumny: (38. - 39.) w przejdź w lewy dolny róg kolumny obok.

Strategia

W celu uproszczenia kodu warto opracować dwie funkcje pomocnicze: palindrom?, która sprawdzi czy dane wyrażenie jest palindromem oraz odwróćLiczba, która odwróci podaną liczbę.

Czy palindrom?

Funkcja palindrom? przyjmuje jeden argument :liczba, którym powinna być liczba do sprawdzenia czy jest palindromem. Poniższy kod sprawdza każdą parę cyfr i zwraca prawdę tylko, gdy dana liczba jest palindromem.

1. oto palindrom? :liczba
2.   niech "dl długość :liczba
3.   powtórz (int(:dl / 2)) [
4.     niech "elL element npw :liczba
5.     niech "elP element (:dl - npw + 1) :liczba
6.     jeśli (:elL <> :elP) [
7.       wynik "fałsz
8.     ]
9.   ]
10.   wynik "prawda
11. już

W powyższym kodzie sprawdzany jest pierwszy element z ostatnim, drugi z przedostatnim itd. W przypadku liczb o nieparzystej ilości cyfr cyfrę w środku można pominąć (jej wartość nie wpływa na palindromiczność wyrażenia).

Odwracanie liczby

Funkcja odwróćLiczba przyjmuje jeden argument :liczba, a następnie zwraca daną liczbę zapisaną wspak. Działanie funkcji opiera się na pobieraniu ostatniej cyfry z podanej liczby dopisaniu jej po prawej stronie nowej liczby, a następnie usunięciu pobranej cyfry z :liczba.

1. oto odwróćLiczba :liczba
2.   niech "a 0
3.   dopóki[:liczba > 0][
4.     niech "a :a * 10
5.     niech "a :a + reszta :liczba 10
6.     niech "liczba int(:liczba / 10)
7.   ]
8.   wynik :a
9. już

Funkcja główna

Działanie głównej funkcji opiera się o pętle dla każdej liczby na liście. W każdej iteracji (4.) pobierana jest liczba i (5.) przyjmuje się, że jest palindromem. Następnie (6. - 9.) należy to sprawdzić. Jeśli nie jest to palindrom to (7.) należy zwiększyć liczbę operacji i (8.) wykonać odpowiednią operację dopóki nie zostanie otrzymana liczba palindromiczna. (10.) Na koniec wystarczy wstawić kolejny zestaw danych na :lista. Wynikiem działania funkcji jest (12.) :lista.

1. oto LICZPAL :liczby
2.   niech "lista []
3.   powtórz (długość :liczby) [
4.     niech "a element npw :liczby
5.     niech "ile 0
6.     dopóki [nie palindrom? :a][
7.       zwiększ "ile
8.       niech "a :a + odwróćLiczba :a
9.     ]
10.     niech "lista nak (lista :a :ile) :lista
11.   ]
12.   wynik :lista
13. już

Warunek trójkąta

Kluczem do wykonania zadania jest przypomnienie sobie warunku trójkąta. Dla dowolnych trzech długości boków trójkąta a, b, c muszą zachodzić następujące nierówności:

• a + b > c
• a + c > b
• b + c > a

W przypadku niespełnienia którejkolwiek z nich dana trójka liczb nie spełnia warunku trójkąta.

Wszystkie kombinacje

Przedstawiony w zadaniu problem polega na znalezieniu podlisty danej listy o największej długości, której dowolna trójka liczb spełnia warunek trójkąta. W przypadku listy trzy elementowej jest tylko jedna trójka do sprawdzenia. W przypadku czteroelementowej są cztery trójki, ale już dla pięcioelementowej jest 10. Później jest 20, 35, ... itd.

Zadanie można bardzo wygodnie rozwiązać przy pomocy rekurencji metodą dziel i zwyciężąj. Przede wszystkim otrzymana liczba jest sprawdzana pod kątem ilości elementów. Jeśli ma tylko trzy to od razu można wypisać wynik sprawdzając warunek trójkąta dla podanych trzech liczb. Jednak w przypadku, gdy elementów jest więcej niż 3 to należy w pętli sprawdzić każdą listę o n - 1 elementach. Można to zrobić pisząc pętle, która n razy wywowała funkcje sprawdzającą warunek, ale w i-tym wywołaniu nie będzie i-tej wartości listy.

Poniższy kod przedstawia funkcję, która sprawdza wszystkie trójki danej listy:

1. oto sprawdzKombinacje :lista
2.   jeżeli ((długość :lista) = 3) [
3.     niech "a pierw :lista
4.     niech "b element 2 :lista
5.     niech "c ost :lista
6.     jeżeli (I :a + :b > :c
7.                     I :a + :c > :b
8.                         :b + :c > :a)[
9.       wynik "prawda
10.     ][
11.       wynik "fałsz
12.     ]
13.   ][
14.     powtórz(długość :lista) [
15.       niech "w sprawdzKombinacje bezElnum npw :lista
16.       jeśli(:w = "fałsz) [
17.         wynik "fałsz
18.       ]
19.     ]
20.     wynik "prawda
21.   ]
22. już

(2.) W przypadku listy trzyelementowej: (3. - 5.) pobierane są elementy listy i (6. - 8.) sprawdzany jest warunek. Na podstawie tego (9. - 12.) zwracana jest odpowiednia wartość logiczna. W przypadku jednej większej listy: (14.) sprawdzana jest każda lista o jeden element mniejsza. (16.) W przypadku, gdy chociaż jedna podlista dowolnej podlisty nie spełnia warunku trójkąta to (15.) należy przerwać sprawdzanie dalszych kombinacji i zwrócić, że nie wszystkie trójki danej :lista spełniają warunek trójkąta.

Funkcja główna

W zasadzie funkcja główna jak i pomocnicza opierają się na tym samym szablonie, ale głóna potrafi zinterpretować wynik obliczeń i przedstawić go jako liczbę. Jest to również funkcja rekurencyjna, która (2. - 4.) w przypadku podania listy, której wszystkie trójki spełniają warunek trójkąta to zwracana jest długość listy.

1. oto ILEMAX :liczby
2.   jeśli ((sprawdzKombinacje :liczby) = "prawda) [
3.     wynik (długość :liczby)
4.   ]
5.   niech "m 0
6.   jeśli ((długość :liczby) > 3) [
7.     powtórz (długość :liczby) [
8.       niech "w ILEMAX bezElnum npw :liczby
9.       jeśli (:w > :m) [
10.         niech "m :w
11.       ]
12.     ]
13.   ]
14.   wynik :m
15. już

Jednak, gdy wszystkie trójki danej listy nie spełniają to należy przejść do szukania podlisty, która będzie spełniać. W tym celu (5.) potrzebny jest licznik, który zapamięta maksymalną długość znalezionej podlisty. (6.) Warunkiem rozpoczęcia poszukiwań jest długość listy większa od trzech (powstrzymuje to program od sprawdzania list długości mniejszej od 3). (7.) Pętla wywoływana jest k razy: (8.) szuka w liście bez i-tego elementu ile wynosi najdłuższa podlista, a następnie (9. - 11.) sprawdza czy znaleziona podlista jest dłuższa niż dotychczas znaleziona. (14.) Niezależnie od sprawdzenia podlist zawsze zwracana jest wartość :m, która wynosi 0 jeśli żadna podlista nie spełnia warunku trójkąta, albo dana lista 3 elementowa też nie spełnia warunku (przypadek szczególny).

• Rozwiązania zadań