Strona główna » Poradniki » Logomocja » LOGIA » Logia 1994/95 - Etap III
 

Logia 1994/95 - Etap III

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

Zadanie 1

Napisz jednoparametrową funkcję SAMOMAX :zdanie. Wartością parametru :zdanie jest dowolna lista słów. Wartością funkcji powinna być lista składająca się z tych słów w danym zdaniu, które mają najwięcej samogłosek. Zakładamy, że słowa składają się z małych liter alfabetu łacińskiego (bez polskich liter), a samogłoskami są a, e, i, o, u, y.

Oto przykładowe wyniki:

SAMOMAX [abrakadabra hokus pokus]ma wartość [abrakadabra]
SAMOMAX [ala ma kota]ma wartość [ala kota]

Podczas rozwiązywania zadania do pokonania są dwa punkty: pierwszy to napisanie pętli zliczającej samogłoski w danym wyrazie oraz pętla, która wywoła wspomnianą poprzednio pętle i odpowiednio zinterpretuje wyniki.

  1. oto SAMOMAX :lista
  2.   niech "max 0
  3.   niech "wynik []
  4.   niech "samogloski [a e i o u y]
  5.   powtórz (długość (:lista)) [
  6.       niech "sam 0
  7.       niech "wyr element npw :lista
  8.       powtórz (długość(:wyr))[
  9.           jeśli (nie (numel (element npw :wyr) :samogloski = 0))[
  10.             zwiększ "sam
  11.           ]
  12.       ]
  13.       jeśli (:sam > :max)[
  14.         niech "max :sam
  15.         niech "wynik []
  16.       ]
  17.       jeśli (:sam = :max)[
  18.         niech "wynik nak :wyr :wynik
  19.       ]
  20.   ]
  21.   wynik :wynik
  22. już

(1.) Funkcja SAMOMAX przyjmuje jeden argument :lista. (2.) Początkowo ustawiamy maksymalną ilość samogłosek na 0 i (3.) deklarujemy pustą listę wynikową :wynik. Do sprawdzania czy dana litera jest samogłoską posłuży nam lista :samogloski. (4.) Dla każdego elementu na liście: (5.) ustawiamy licznik samogłosek :sam na 0. (6.) Następnie rozpatrywany wyraz zapisujemy do zmiennej tymczasowej :wyr - jest to konieczność wynikająca z faktu, że w kolejnej pętli powtórz nie mamy dostępu do numeru powtórzenia z poprzedniej. (8.) Dla każdej litery w wyrazie :wyr: (9.) sprawdzamy czy każda kolejna litera znajduje się na liście :samogloski - (10.) jesli tak to zwiększamy licznik :sam. (13.) Jeśli licznik :sam jest większy od :max to znaczy, że wszystkie poprzednie wyrazy miały mniej samogłosek, dlatego (14.) ustalamy wartość :max na :sam i (15.) czyścimy listę wynikową :wynik. Oczywiście (17.) sprawdzamy potem czy licznik samogłosek ma taką samą wartość co :max. (18.) Jeśli tak to dodajemy na koniec listy wyraz :wyr. Na koniec (21.) zwracamy listę :wynik.

Zadanie 2

Napisz jednoparametrową funkcję CYFRYNAJ :liczba. Wartością parametru :liczba jest dowolna liczba całkowita. Wartością funkcji powinna być dwuelementowa lista składająca się z najmniejszej i największej cyfry parametru :liczba.

Oto przykładowe wyniki:

CYFRYNAJ 6387644ma wartość [3 8]
CYFRYNAJ 6212777ma wartość [1 7]
CYFRYNAJ 666ma wartość [6 6]
CYFRYNAJ 3ma wartość [3 3]

W rozwiązaniu zadania napisze pętle, która będzie pobierała kolejne cyfry od końca liczby i na ich podstawie stwierdzi jaki jest min i max:

  1. oto CYFRYNAJ :liczba
  2.   niech "r reszta :liczba 10
  3.   niech "max :r
  4.   niech "min :r
  5.   dopóki [:liczba > 9][
  6.     niech "liczba (:liczba - :r) / 10
  7.     niech "r reszta :liczba 10
  8.     jeśli (:r > :max)[
  9.       niech "max :r
  10.     ]
  11.     jeśli (:r < :min)[
  12.       niech "min :r
  13.     ]
  14.   ]
  15.   wynik (lista :min :max)
  16. już

(1.) Funkcja CYFRYNAJ przyjmuje jeden argument :liczba. (2.) Pobieramy ostatnią cyfrę liczby - jest to reszta z dzielenia :liczba przez 10. Uznajemy, że wartość :r to wartość (3.) maksymalna i (4.) minimalna. (5.) W każdej iteracji będziemy usuwać ostatnią liczbę cyfry, dlatego będziemy powtarzać to, aż :liczba jest większa od 9. Jeśli liczba jest większa od 9 oznacza to, że jest conajmniej dwucyfrowa. (6.) Usuwamy z liczby ostatnia cyfrę. (7.) Pobieramy ostatnią cyfrę (z nowej wartości) :liczba. (8.) Jeśli :r (ostatnia cyfra :liczba) jest większa od :max to (9.) ustalamy wartość :max na :r. (11.) Analogicznie robimy dla minimum :min: jeśli :r jest mniejsze od :minto (12.) zmiennej :min przypisujemy wartość :r. Na koniec (15.) zwracamy listę elementów utworzonych z :min oraz :max.

Zadanie 3

Rozważamy drzewa o różnym stopniu złożoności. Najprostsze drzewo składa się z samego pnia. Bardziej złożone drzewo może składać się z pnia, z którego wyrastają dokładnie dwa poddrzewa. Pnie poddrzew tworzą kąt prosty i mają taką samą długość stanowiącą dwie trzecie długości pnia drzewa z którego wyrastają.

Poniżej przedstawione są rysunki uzyskane po wywołaniu DRZEWO [], DRZEWO [[] []], DRZEWO [[] [[] []]] oraz DRZEWO [[[] []] [[] [[] []]]]].

Obrazek 1 do zadania 3

  • Kodem drzewa składającego się tylko z pnia, jest lista pusta: []
  • Kodem każdego bardziej złożonego drzewa jest lista, która ma dokładnie dwa elementy: pierwszy element tej listy jest kodem lewego poddrzewa, a drugi element jest kodem prawego poddrzewa.

Napisz jednoparametrową procedurę DRZEWO :kod rysowania drzew takich jak na rysunkach od 1 do 4. Wartością parametru :kod jest lista, która jest kodem drzewa zbudowanego zgodnie z podanymi zasadami. Po wywołaniu procedury DRZEWO z odpowiednim parametrem na ekranie powinien pojawić się możliwie duży rysunek drzewa o danym kodzie.

Rozwiązując tego typu zadania dobrą praktyką jest rozbić zadanie na dwie procedury i zastosować rekurencję. W rozwiązaniu użyjemy funkcji pusta?, która spradzi czy na liście znajduje się jakikolwiek element.

  1. oto DRZEWO_pom :a :lista
  2.   np :a
  3.   jeśli (nie (puste? :lista))[
  4.     lw 45
  5.     DRZEWO_pom :a*2/3 element 1 :lista
  6.     pw 90
  7.     DRZEWO_pom :a*2/3 element 2 :lista
  8.     lw 45
  9.   ]
  10.   ws :a
  11. już

(1.) Funkcja pomocnicza DRZEWO_pom jako argument przyjmuje listę w postaci podanej w zadaniu. (2.) Rysuje gałąź i (3.) sprawdza czy list nie jest pusta. Jeśli nie jest pusta oznacza to, że gałąź się rozgałęzia, dlatego (4.) obracamy się w lewo o i (5.) wywołujemy procedurę DRZEWO_pom, ale podajemy, że długość jest oraz jako listę podajemy pierwszy element z :lista. (6.) Potem obkręcamy się na drugą stronę gałęzi i (7.) analogicznie ponownie wywołujemy procedure DRZEWO_pom tym razem jako drugi dając drugi element z :lista. Na koniec wracamy żółwiem do kierunku, który mieliśmy na początek. (9.) Wracamy żółwiem do punktu wyjścia.

  1. oto DRZEWO :lista
  2.   pod
  3.   ws 240
  4.   opu
  5.   niech "a 220
  6.   DRZEWO_pom :a :lista
  7. już

Funkcja główna DRZEWO ma raczej charakter przygotowawczy bowiem (1. - 3.) ustawia żółwie na odpowiedniej pozycji, (4.) ustalamy wysokość drzewa i (5.) wywołujemy procedurę DRZEWO_pom.