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

Logia 2006/07 - Etap III

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

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.

  1.   niech "a 400
  2.   niech "elw :a/(długość :lista)
  3.   niech "elh :a/:max
  4.   pod
  5.   ws :a/2 pw 90
  6.   ws :a/2 lw 90
  7.   opu
  8.   powtórz (długość :lista) [
  9.     niech "w element npw :lista
  10.     powtórz (:max) [
  11.       jeżeli(npw <= :w) [
  12.         ukm "szary
  13.       ][
  14.         ukm "biały
  15.       ]
  16.       wielokąt [
  17.         powtórz 2 [
  18.           np :elh pw 90
  19.           np :elw pw 90
  20.         ]
  21.       ]
  22.       np :elh
  23.     ]
  24.     ws :elh*:max pw 90
  25.     np :elw lw 90
  26.   ]
  27. 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.

Zadanie 2 (liczby palindromiczne)

Liczba palindromiczna - jest to taka liczba, która po odczytaniu zarówno od lewej, jak i prawej strony daje tę samą wartość. Liczbami palindromicznymi są na przykład liczby 7, 121, 5445.

Napisz funkcję LICZPAL :liczby, gdzie parametr :liczby jest listą liczb całkowitych z zakresu od 0 do 88. Wartością funkcji jest lista list składających się z liczby palindromicznej oraz liczby dodawań prowadzących do jej otrzymania.

Liczby palindromiczne dla każdej liczby z listy :liczby otrzymujemy w następujący sposób: znajdujemy zapis wspak danej liczby i dodajemy do niej. Proces dodawania powtarzamy do otrzymania liczby palindromicznej (np. dla liczby 37: 37+73=110, 110+11=121). Zakładamy, że parametr :liczby nie jest pustą listą.

LICZPAL [76 28 87 88][[484 2][121 2][4884 4][88 0]]

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ż

Zadanie 3 (trójkąty)

Napisz funkcję ILEMAX :liczby, gdzie parametr :liczby jest dowolną listą liczbową, zawierającą co najmniej trzy liczby dodatnie. Wynikiem funkcji jest liczba elementów najliczniejszego z podzbiorów danej listy, spełniającego warunek, że z odcinków o długościach określonych przez trzy dowolne elementy tego podzbioru można zbudować trójkąt.

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

ILEMAX [1 1 3]0
ILEMAX [2 789 5 3 3237 4]3

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:

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).