Strona główna » Poradniki » Logomocja » LOGIA » Logia 1997/98 - Etap II

Logia 1997/98 - Etap II

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

Zadanie 1

Zdefiniuj procedurę z dwoma parametrami TROJKI :zakres :suma, której wywołanie powoduje wypisanie w kolejnych wierszach wszystkich trójek liczb całkowitych dodatnich a b c, nie większych niż dana wartość :zakres, takich że: a < b < c oraz a + b + c =:suma. Oto przykładowe działanie procedury:

TROJKI 6 10TROJKI 7 12
powinno wypisać na ekranie:powinno wypisać na ekranie:
1 3 61 4 7
1 4 51 5 6
2 3 52 3 7
2 4 6
3 4 5

Przed przystąpieniem do zadania warto stwierdzić jakie warunki muszą spełanić liczby. Wiadomo, że , dlatego , ponieważ jeśli a będzie większe to wtedy wszystkie lub tylko b i c musiałyby być równe. Wiadomo też, że b jest większe od a, ale nigdy nie jest równe :zakres, czyli . Ostatnia liczba c musi być większy od b, dlatego należy do zakresu . Tego typu rozwiązanie realizuje poniższy kod:

  1. oto TROJKI :zakres :suma
  2.   powtórz (:zakres - 2)[
  3.     niech "a npw
  4.     powtórz (:zakres - :a - 1)[
  5.       niech "b :a + npw
  6.       niech "c :suma - :b - :a
  7.       jeśli (:c > :b)[
  8.         ps (zd :a (znak 32) :b (znak 32) :c)
  9.       ]
  10.     ]
  11.   ]
  12. już

(2.) Dla każdej wartości a: (3.) zapamiętujemy jej wartość i (4.) w zależności od a sprawdzamy odpowiedni wartości b: (5.) obliczamy wartość b oraz (6.) ile musi wynieść c. (7.) Jeśli c > b to (8.) to wypisujemy wyliczoną trójke. Nie trzeba sprawdzać czy a < b, ponieważ jest to zagwarantowane przez zakresy.

Liczbę c można wyznaczyć w ten sam sposób jak b. Jednak sprawdzanie wszystkich możliwości zmniejsza efektywność algorytmu.

Zadanie 2

Zdefiniuj funkcję z jednym parametrem MOS :wyraz, której wartością dla danego wyrazu jest liczba liter zawartych między najbardziej odległymi samogłoskami w tym wyrazie, lub -1 w przypadku gdy wyraz nie zawiera przynajmniej dwóch samogłosek. Zakładamy, że wyrazy zawierają jedynie małe litery alfabetu łacińskiego. Oto przykładowe wyniki:

MOS "hokusma wartość 1
MOS "nicma wartość -1
MOS "abrakadabrama wartość 9

Do rozwiązania zadania warto zadeklarować dodatkową funkcję SAMOGŁOSKA?, która będzie przyjmowała znak. Zwrócona wartość określi czy dany znak jest samogłoską:

  1. oto SAMOGŁOSKA? :a
  2.   wynik (numel :a [a e i o u y] <> 0)
  3. już

Zadanie można wyznaczyć sprawdzając kolejne znaki. Jeśli napotkamy samogłoskę należy ją przypisać indeksowi pierwszemu, a jeśli znajdziemy następną to przypisujemy ją tylko do drugiego indeksu. Różnica indeksu będzie szukaną wartością.

  1. oto MOS :wyraz
  2.   niech "max -1
  3.   niech "lp 0
  4.   powtórz (długość :wyraz)[
  5.     jeśli (SAMOGŁOSKA? element npw :wyraz)[
  6.       jeżeli (:lp = 0)[
  7.         niech "lp npw
  8.       ][
  9.         jeśli (npw - :lp - 1 > :max)[
  10.           niech "max npw - :lp - 1
  11.         ]
  12.       ]
  13.     ]
  14.   ]
  15.   wynik :max
  16. już

Ustalanie indeksów początkowych (2.) :p - indeks pierwszej samogłoski i (3.) :o - indeks ostatniej samogłoski. (4.) Dla każdej litery z :wyraz: (5.) sprawdza czy litera jest samogłoską. Jeśli jest to należy sprawdzić (6.) czy jest to pierwsza samogłoska, czyli czy :p = 0. Jeśli drugi warunek też jest spełniony to (7.) ustalamy :p na aktualny indeks litery. Jednak jeśli nie jest to pierwsza samogłoska to zmieniamy drugi indeks :o. Po pętli pozostaje (13.) zinterpretować wynik. Jeśli :o = 0 to (14.) należy zwrócić wynik -1, ponieważ nie ma lub jest tylko jedna samogłoska. W przeciwnym wypadku (16.) należy zwrócić różnicę pomiędzy :o i :p. Wartość tę należy jeszcze zmniejszyć o jeden.

Zadanie 3

Z trzech identycznych kwadratów można ułożyć figurę o kształcie litery L, taką jak na rysunku a. Takie samo L można utworzyć:
z 4 dwa razy mniejszych L - ja na rysunku b,
z 16 cztery razy mniejszych L - jak na rysunku c, itd.

Obrazek 1 do zadania 3
Każde kolejne L jest coraz bardziej złożone. Przyjmijmy, że:

  • proste L na rysunku a ma stopień złożoności 0
  • L na rysunku b ma stopień złożoności 1
  • L na rysunku c ma stopień złożoności 2
  • L o stopniu złożoności n składa się z 4-n odpowiednio mniejszych prostych L.
Napisz procedurę z jednym parametrem L :n, która dla dowolnego :n tworzy na środku ekranu możliwie duży rysunek L o stopniu złożoności :n.

Najprostsze rozwiązanie tego zadania opiera się o rekurencję. Wystarczy bowiem napisać funkcję rysującą L, a następnie, aby w odpowiednich punktach narysować L o mniejszym stopniu złożoności. Punkty zostały zaznaczone na poniższym schemacie:

Schemat pomocniczy do zadania 3
  1. oto L_rek :n :a
  2.   jeśli(:n > 0)[L_rek :n-1 :a/2]
  3.   np :a
  4.   pw 90
  5.   jeśli(:n > 0)[L_rek :n-1 :a/2]
  6.   np :a/2
  7.   pw 90
  8.   np :a/2
  9.   lw 90
  10.   jeśli(:n > 0)[
  11.     pod
  12.     ws :a/4
  13.     lw 90
  14.     ws :a/4
  15.     opu
  16.     L_rek :n-1 :a/2
  17.     pod
  18.     np :a/4
  19.     pw 90
  20.     np :a/4
  21.     opu
  22.   ]
  23.   np :a/2
  24.   pw 90
  25.   np :a/2
  26.   pw 90
  27.   jeśli(:n > 0)[L_rek :n-1 :a/2]
  28.   np :a
  29.   pw 90
  30. już

(2.) Wywołanie L o mniejszym stopniu złożoności. (3. - 4.) Przejście do górnego punktu. (5.) Ponowne wywołanie funkcji. (6. - 9.) Przejście w prawo i w dół. (10. - 22.) Wywołanie mniejszego L w punkcie pośrodku ekranu. (23. - 26.) Przejście do prawego dolnego rogu i (27.) ponowne wywołanie funkcji o mniejszym stopniu złożoności. (28 - 29.) Zakończenie rysowania L i ustawienie żółwia w pozycji początkowej.

Pozostaje napisać teraz właściwą procedurę :L, która wywoła L_rek, a wcześniej określi wymiary rysunku:

  1. oto L :n
  2.   niech "h 400
  3.   pod
  4.   ws :h/2
  5.   pw 90
  6.   ws :h/2
  7.   lw 90
  8.   opu
  9.   L_rek :n :h
  10. już