Strona główna » Poradniki » Logomocja » LOGIA » Logia 1995/96 - Etap III

Logia 1995/96 - Etap III

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

Zadanie 1

Napisz procedurę jednoparametrową LAS :lista, rysującą na ekranie las na podstawie zdania podanego jako parametr:

  • Liczba drzew ma być równa liczbie słów w zdaniu.
  • Kolejne rysowane drzewa, od lewej do prawej, mają odpowiadać kolejnym słowom parametru.
  • Od pnia, po obu jego stronach, w górę pod kątem 45o, powinny wyrastać pary gałęzi.
  • Kolejne pary gałęzi, od dołu ku górze, mają odpowiadać kolejnym literom słowa opisującego drzewo.
  • Długość gałęzi dla spółgłosek ma być dwa razy mniejsza od długości gałęzi dla samogłosek.

Rysunek powinien wykorzystywać cały ekran. Wszystkie drzewa mają mieć tę samą szerokość. Odległości pomiędzy pniami sąsiednich drzew powinny być jednakowe. Wysokość pnia drzewa powinna być wprost proporcjonalna do liczby liter w słowie opisującym dane drzewo. Poziome podłoże jest elementem tworzonego rysunku. Lista opisująca las może zawierać od jednego do dziesięciu niepustych słów składających się jedynie z małych liter alfabetu łacińskiego.

Obrazek 1 do zadania 1Obrazek 2 do zadania 1

Podczas tego zadania zalecam utworzenie dwóch procedur i funkcji. Pierwsz procedura będzie zarządzać wielkości i będzie wywoływać drugą, która z kolei narusyje pojedyncze pełne drzewo. Zadaniem funkcji będzie sprawdzić czy dana litera jest samogłoską.

Funkcja samogłoska? będzie przyjmować jeden argument - literę do sprawdzenia, a jako wynik zwróći prawdę / fałsz czy to samogłoska czy nie:

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

Przejdźmy teraz do procedury pomocniczej LAS_pom rysującej drzewo. Będziemy jej przekazywać trzy argumenty: :słowo - określi jakie słowo ma przedstawić drzewom, :szer - określi szerokość pojedynczej gałęzi oraz :odl_gal - określi jaka powinna być odległość pomiędzy parą gałęzi:

  1. oto LAS_pom :słowo :szer :odl_gal
  2.   powtórz (długość :słowo)[
  3.       np :odl_gal
  4.       niech "a :szer * pwk(2)
  5.       jeśli (nie (samogłoska? (element npw :słowo)))[
  6.           niech "a :a / 2
  7.       ]
  8.       lw 45
  9.       np :a
  10.       ws :a
  11.       pw 90
  12.       np :a
  13.       ws :a
  14.       lw 45
  15.   ]
  16.   ws :odl_gal * (długość :słowo)
  17. już

(2.) Dla każdego znaku w słowie: (3.) Określamy wstępną długość gałęzi na podstawie parametru :szer. (4.) W przypadku, gdy litera nie jest samogłoską to (5.) zmniejszamy długość gałęzi :a o połowę. (7. - 13.) Rysujemy gałąź po jednej i drugiej stronie. (15.) Cofamy się do punktu z którego zaczęliśmy rysowanie.

Do napisania główna funkcja LAS. Na początku wyliczymy wszystkie wartości potrzebne do narysowania drzewa:

  1. oto LAS :lista
  2.   niech "margines 8
  3.   niech "szer (element 1 s1'rozmiar) - :margines
  4.   niech "wys (element 2 s1'rozmiar) - :margines
  5.   niech "szer_drzewo :szer / (długość :lista)
  6.   niech "max 0
  7.   powtórz (długość :lista)[
  8.     jeśli ((długość (element npw :lista)) > :max)[
  9.       niech "max długość (element npw :lista)
  10.     ]
  11.   ]
  12.   niech "odl_gal (:wys - (:szer_drzewo / 2)) / (:max + 1)

(2.) Na początek ustalamy margines. Dzięki temu łatwiej będzie zmniejszać proporcjonalnie obraz wynikowy. (3.) Obliczamy szerokość i (4.) wysokość obszaru na którym będziemy rysować. (5.) Obliczamy szerokość drzewa. (6. - 11.) W celu obliczenia odległości pomiedzy gałęziami musimy znać jak długie jest najdłuższe słowo. Po znalezieniu maksymalnej wartości możemy wyliczyć (12.) odległość pomiędzy gałęziami.

  1.   pod
  2.   ws :wys / 2
  3.   pw 90
  4.   ws :szer / 2
  5.   lw 90
  6.   opu
  7.   powtórz (długość :lista)[
  8.     pw 90
  9.     np :szer_drzewo / 2
  10.     lw 90
  11.     LAS_pom (element npw :lista) (:szer_drzewo / 2) :odl_gal
  12.     pw 90
  13.     np :szer_drzewo / 2
  14.     lw 90
  15.   ]
  16.  
  17. już

Druga część procedury to (13. - 17.) ustawienie żółwia w lewym dolnym rogu obrazku i (18. - 26.) narysowanie drzew. Warto tu pamiętać, że procedurze pomocniczej przekazujemy :szer_drzewo / 2 jako argument :szer.

Zadanie 2

Napisz funkcję PRZESTAW :zdanie, której wartością będzie zdanie zawierające wszystkie słowa zdania podanego jako parametr, ale poprzestawiane tak, aby na początku znajdowały się słowa zawierające literę a (w tej samej kolejności jak na danej liście). Parametrem funkcji może być tylko lista słów składających się jedynie z małych liter alfabetu łacińskiego. Wynik również powinien być listą słów. Poniżej przedstawiamy przykładowe wyniki:

PRZESTAW [ala ma kota i psa]ma wartość [ala ma kota psa i]
PRZESTAW [hokus pokus abrakadabra]ma wartość [abrakadabra hokus pokus]

W zadaniu najprostszym rozwiazaniem jest podzielenie zestawu na dwie listy, a następnie ich scalenie:

  1. oto PRZESTAW :zdanie
  2.   niech "lista_w []
  3.   powtórz (długość :zdanie)[
  4.     jeśli (element? "a element (npw - długość :lista_w) :zdanie) [
  5.         niech "lista_w nak element (npw - długość :lista_w) :zdanie :lista_w
  6.         niech "zdanie bezElNum (npw + 1 - długość :lista_w) :zdanie
  7.     ]
  8.   ]
  9.   wynik zd :lista_w :zdanie
  10. już

(2.) Deklarujemy pustą listę pomocniczą do której będziemy wrzucać elementy, które mają być na początku. (3.) Dla każdego wyrazu na liście: (4.) jeśli zawiera a w sobie to (5.) dopisujemy na koniec :lista_w i (6.) usuwamy ten element z listy. Odejmujemy od npw długość :lista_w, ponieważ lista :zdanie po usunięciu elementu jest mniejsza. (9.) Zwracamy listę scaloną z dwóch list: (kolejno) :lista_w i :zdanie.

Zadanie 3

Lista liczbowa to taka lista, której każdy element jest liczbą naturalną lub listą liczbową. Na przykład lista [[2 3] 1 [3] [[5 2] 1] 2] jest listą liczbową, bo jej elementy: drugi i piąty (to jest 1 i 2) - są liczbami naturalnymi, a elementy: pierwszy, trzeci i czwarty (to jest [2 3], [3] i [[5 2] 1]) - są listami liczbowymi. Lista pusta też jest listą liczbową.

Jeśli z zapisu listy liczbowej usuniemy wszystkie nawiasy kwadratowe, to otrzymamy skończony ciąg liczb; będziemy je nazywali składnikami listy liczbowej. Liczba składników listy liczbowej na ogół nie jest równa liczbie jej elementów, np. lista podana powyżej ma pięć elementów oraz osiem składników (2, 3, 1, 3, 5, 2, 1, 2).

Dla każdego składnika listy liczbowej określamy jego poziom na tej liście w następujący sposób:

  • wszystkie składniki listy liczbowej, które są jej elementami mają poziom 1,
  • wszystkie elementy elementów listy liczbowej mają poziom 2,
  • wszystkie elementy elementów elementów listy liczbowej mają poziom 3, itd.

Np. składniki: 2, 3, 1, 3, 5, 2, 1, 2 listy liczbowej [[2 3] 1 [3] [[5 2] 1] 2] mają odpowiednio poziom: 2, 2, 1, 2, 3, 3, 2, 1.

Wagą składnika listy liczbowej nazywamy iloczyn tego składnika przez jego poziom. Wagą listy liczbowej nazywamy sumę wag jej składników, listy puste i listy złożone z list pustych mają wagę zero.

Zdefiniuj funkcję WAGALISTY :lliczb, której wartością jest waga listy liczbowej podanej jako parametr. Zakładamy, że dany parametr funkcji będzie zawsze poprawną listą liczbową i napisane procedury nie musza tego sprawdzać. Oto przykładowe wyniki:

WAGALISTY [[2 3] 1 [3] [[5 2] 1] 2]ma wartość 42
WAGALISTY [[] 2 [] [[1]]]ma wartość 5
WAGALISTY [[] []]ma wartość 0

Jest idealne zadania, aby wykorzystać rekurencję. Do funkcji tego typu pierwszym argumentem musi być lista elementów, a drugim poziom. Iterujemy przez wszystkie elementy na liście. W przypadku, gdy element jest liczbą to sumę zwiększamy o iloczyn tego elementu razy poziom. W przeciwnym wypadku, gdy element jest listą to wywołujemy funkcję z tym elementem jako argument :lista, a :poziom zwiększamy o jeden. Wtedy funkcja wygląda następująco:

  1. oto WAGALISTY_rek :lliczb :poziom
  2.   niech "suma 0
  3.   powtórz(długość :lliczb)[
  4.     jeżeli(lista? element npw :lliczb)[
  5.       niech "suma :suma + WAGALISTY_rek (element npw :lliczb) (:poziom + 1)
  6.     ][
  7.       niech "suma :suma + (element npw :lliczb) * :poziom
  8.     ]
  9.   ]
  10.   wynik :suma
  11. już

Jednak zadanie nie przewiduje drugiego argumentu, dlatego funkcja WAGALISTY będzie rozpoczynać rekurencję:

  1. oto WAGALISTY :lliczb
  2.   wynik WAGALISTY_rek :lliczb 1
  3. już