Logia 2008/09 - Etap III

Zadanie 1 (nawożenie i plony)

Wieś Logianów postanowiła nawozić swoje pola zgodnie z zasadami rolnictwa precyzyjnego. Za pomocą specjalnych kombajnów zbożowych wyposażonych w mierniki plonów zebrano dane o wysokości zbiorów w różnych częściach logianowskich pól. Następnie opracowano wyniki na komputerze, tworząc barwne mapy plonów. Na podstawie mapy plonów stosuje się zabiegi nawożenia roślin polegające na tym, że te części pola, które mogą wydać większy plon otrzymują odpowiednio wyższe nawożenie, natomiast te, które mają mniejszy potencjał otrzymują odpowiednio mniej. Przyjęto trzy poziomy nawożenia: I - minimalne nawożenie, II - średnie, III - najwyższe.

Każde pole ma wymiary :n na :n jednostek. Dzielimy je na prostokątne obszary, ze względu na poziom nawożenia. Położenie oraz poziom nawożenia obszaru określamy za pomocą pięcioelementowej listy liczb całkowitych. Cztery pierwsze liczby wyznaczają przeciwległe narożniki obszaru i mogą przyjmować wartości z zakresu od 0 do :n, piąta liczba określa poziom nawożenia, może przyjmować wartości z zakresu od 1 do 3. Na przykład lista [0 0 1 2 3] oznacza najwyższy stopień nawożenia górnego lewego kwadratu pola i kwadratu poniżej.

Napisz funkcję ILEN :n :mapa, która wyliczy, jakie części logianowskich pól obejmuje każdy ze stosowanych poziomów nawożenia. Parametr :n określa wielkość pola i może przyjmować wartości od 1 do 10, parametr :mapa jest listą złożoną z list określających położenie oraz poziom nawożenia obszarów. Zakładamy, że wszystkie obszary, które nie są wymienione na liście wymagają minimalnego nawożenia, na liście nie ma też sprzecznych danych. Wynikiem funkcji jest trójelementowa lista liczb określających powierzchnię objętą I, II oraz III poziomem nawożenia.

ILEN 4 [[0 0 4 4 2]]	jest [0 16 0]
ILEN 3 [[0 0 1 1 3][2 2 3 3 2]]	jest [7 1 1]
ILEN 4 [[0 0 1 2 2][0 1 3 2 2][3 3 4 4 3]]	jest [11 4 1]

Strategia

Na początku należy zadeklarować tablicę, która będzie pamiętać jaki poziom nawożenia wymaga każde z pól. Następnie dla każdego określonego obszaru aktualizowane są odpowiednie pola. Na koniec wystarczy wtedy sprawdzić ile razy występuje, która wartość w tablicy, aby uzyskać wynik.

Rozwiązanie

(2.) Tablica dwuwymiarowa jest dla prostoty przetrzymywana jako jednowymiarowa i (3. - 5.) jest ona na początku deklarowana samymi wartościami 1, ponieważ jest to minimalny poziom nawożenia:

1. oto ILEN :n :mapa
2.   niech "obszar []
3.   powtórz (:n*:n) [
4.     niech "obszar nak 1 :obszar
5.   ]
6.   powtórz (długość :mapa) [
7.     niech "el element npw :mapa
8.     niech "xp element 1 :el
9.     niech "yp element 2 :el
10.     niech "xk element 3 :el
11.     niech "yk element 4 :el
12.     niech "pz element 5 :el
13.     dopóki [:yp < :yk] [
14.       niech "xp element 1 :el
15.       dopóki [:xp < :xk] [
16.         niech "poz :yp*:n + :xp + 1
17.         jeśli ((element :poz :obszar) < :pz) [
18.           niech "obszar zastąp :poz :obszar :pz
19.         ]
20.         zwiększ "xp
21.       ]
22.       zwiększ "yp
23.     ]
24.   ]
25.   niech "dane [0 0 0]
26.   powtórz (:n*:n) [
27.     niech "p element npw :obszar
28.     niech "k (element :p :dane) + 1
29.     niech "dane zastąp :p :dane :k
30.   ]
31.   wynik :dane
32. już

(6.) Następnie dla każdego pola: (7. - 12.) pobieramy odpowiednie dane z kolejnego elementu tj. współrzędne początkowe (xp, yp), końcowe (xk, yk) oraz poziom nawożenia pz. Do zapełniania odpowiednich pól została wykorzystana (13. - 23.) podwójna pętla, która przechodzi po kolejnych polach wskazanego obszaru. (17.) Jeśli dane pole ma mniejszy stopień nawożenia niż wskazany to jest (18.) on aktualizowany. Na koniec (25. - 30.) zliczane jest ile jest jakich poziomów nawożenia.

Zadanie 2 (ślimak)

Szyfrujemy słowo zapisując je w formie ślimaka (druga litera nad pierwszą, trzecia po prawej stronie drugiej, czwarta pod trzecią itd. dookoła), a następnie czytamy wierszami od lewej do prawej. Na przykład zapisane w formie ślimaka słowo "abcdefghijklmnopqrstuvwxy odczytamy jako "yjklmxibcnwhadovgfeputsrq.

Napisz funkcję SZYFR :słowa, której daną jest lista słów do zaszyfrowania, a wynikiem jest lista zaszyfrowanych słów według przedstawionego sposobu.

SZYFR [abc defg hijkl]	jest [bca efdg ijhkl]
SZYFR [konkurs logia]	jest [onkksru oglia]

Strategia

Szyfrowanie w formia ślimaka opiera się na zasadzie rysowania spirali. Oznacza to, że kolejno przed skrętem w prawo idzie się kolejno 1, 1, 2, 2, 3, 3, 4, 4, ... pól do przodu. Jednak, aby móc poruszać wskaźnik pola po spirali należy mieć jaką planszę - może to być dwuwymiarowa tablica. Dla każdej kolejnej litery będzie wyliczana nowa pozycja i w tym miejscu zostanie umieszczony znak. Na koniec wystarczy przeczytać kolejne wiersze tablicy, aby odczytać wynik.

Rozwiązanie

(3.) Dla każdego słowa przekazanego na liscie słów: (4.) pobieramy kolejny wyraz i (5. - 8.) szukamy takiego boku tablicy dwuwymiarowej tak, aby wszystkie znaki się zmieściły. Następnie (9. - 12.) całą tablicę wypełniamy znakami spacji - później będą one ignorowane podczas odczytywania wyniku. Jest to ważne, ponieważ zwykle znalezione wymiary tablicy są w stanie pomieścić więcej znaków niż ma rozważane słowo. Przed przejściem do uzupełniania tablicy pozostało teraz (13. - 19.) przygotować listę liczb co ile kroków należy skręcić w prawo.

1. oto SZYFR :słowa
2.   niech "w []
3.   powtórz (długość :słowa)[
4.     niech "słowo element npw :słowa
5.     niech "n 1
6.     dopóki [:n*:n < (długość :słowo)][
7.       niech "n :n + 2
8.     ]
9.     niech "dane []
10.     powtórz (:n*:n) [
11.       niech "dane nak (znak 32) :dane
12.     ]
13.     niech "dl []
14.     powtórz (:n*:n) [
15.       niech "q npw
16.       powtórz (2) [
17.         niech "dl nak :q :dl
18.       ]
19.     ]

Początkowym (20.) miejscem zapisu jest środek tablicy dwuwymiarowej. Jest to możliwe, ponieważ jej bok zawsze jest nieparzysty. (21.) Dodatkowo zadeklarowane zostały możliwe przesunięcia oraz (22.) które przesunięcie jest aktualnie używane. Na początku (23.) wybieramy, że tylko jedno pole ma zostać zapisane. (24.) Dopóki będą znaki do zapisania to: (25. - 26.) zastąp odpowiednie miejsce w tablicy kolejnym znakiem i (28. - 36.) sprawdź czy nie trzeba odbić w prawo. Warunkiem jest (29.) brak kroków do wykonania. Na koniec iteracji należy pamiętać, aby (37.) zmienić wybrane pole i (38.) usunąć zapisany znak. Na koniec (40. - 45.) zapisane znaki są odczytywane kolejno z tablicy i (46.) zaszyfrowane słowo zostaje dopisane na listę wynikową.

19.     ]
20.     niech "gdzie (lista (int(:n/2)) (int(:n/2)))
21.     niech "przes [[0 -1] [1 0] [0 1] [-1 0]]
22.     niech "k 4
23.     niech "ile pierw :dl
24.     dopóki [(długość :słowo) > 0][
25.       pokaż :gdzie
26.       niech "poz (ost :gdzie)*:n + (pierw :gdzie)
27.       niech "dane zastąp :poz :dane (pierw :słowo)
28.       zmniejsz "ile
29.       jeśli (:ile <= 0) [
30.         niech "ile pierw :dl
31.         niech "dl bp :dl
32.         zwiększ "k
33.         jeśli (:k = 5) [
34.           niech "k 1
35.         ]
36.       ]
37.       niech "gdzie :gdzie + (element :k :przes)
38.       niech "słowo bp :słowo
39.     ]
40.     niech "s "
41.     powtórz (:n*:n) [
42.       jeśli (nie ((element npw :dane) = (znak 32))) [
43.         niech "s nak (element npw :dane) :s
44.       ]
45.     ]
46.     niech "w nak :s :w
47.   ]
48.   wynik :w
49. już

Strategia

W celu rozwiązania zadania najpierw zostaną wyznaczone wszystkie liczby pierwsze trzycyfrowe i na ich podstawie zostaną wyliczone liczby sześciocyfrowe. Po posortowaniu zostanie przepisane jedynie :n pierwszych liczb na listę wynikową.

Rozwiązanie

Do sprawdzenia czy liczba jest pierwsza została napisana specjalna funkcja czyPierwsza, która dla podanej liczby :a zwraca czy wartość logiczną, która określa czy należy ona do zbioru liczb pierwszych.

1. oto czyPierwsza :a
2.   jeśli (:a <= 1) [
3.     wynik "fałsz
4.   ]
5.   niech "dzielnik 2
6.   dopóki [:dzielnik <= pwk(:a)][
7.     jeśli (reszta :a :dzielnik = 0) [
8.       wynik "fałsz
9.     ]
10.     zwiększ "dzielnik
11.   ]
12.   wynik "prawda
13. już

Z kolei w głównej funkcji (2. - 4.) możemy wykluczyć, gdy :n = 0, ponieważ wtedy zawsze jest zwracana pusta lista. Jeśli jednak :n jest większe od 0 to (5. - 14.) szukamy wszystkich trzycyfrowych liczb pierwszych, a na listę (9. - 11.) zapisujemy gotowe liczby sześciocyfrowe. Używany jest do tego wzór w linijce (10.). Kolejny etap polega na (15.) posortowaniu i (16. - 19.) przepisaniu tylko pierwszych :n wyrazów.

1. oto LLLP :n
2.   jeśli (:n = 0) [
3.     wynik []
4.   ]
5.   niech "pierwsze []
6.   niech "od 100
7.   dopóki [:od < 1000][
8.     jeśli (I (czyPierwsza :od) (czyPierwsza wspak :od)) [
9.       niech "a :od
10.       niech "a (wspak :a) + 1000*:a
11.       niech "pierwsze nak :a :pierwsze
12.     ]
13.     zwiększ "od
14.   ]
15.   niech "pierwsze sortuj :pierwsze
16.   niech "w []
17.   powtórz(:n) [
18.     niech "w nak (element npw :pierwsze) :w
19.   ]
20.   wynik :w
21. już

Strategia

Wyliczanie czasu pomiędzy dwoma czasami jest problematyczne, ponieważ należy obliczyć różnicę minut pomiędzy dwoma czasami, podzielić na dwa i uzyskany wynik dodać do wcześniejszej godziny. Zadanie to można uprościć poprzez możliwość przeliczenia dowolnej godziny na ilość minut, która upłynęła od północy.

W celu poszerzenia rozkładu wystarczy podzielić aktualny rozkład na rozkład każdej z linii. Następnie każdy rozkład rozszerzamy niezależnie tak, aby był posortowany. Mając tak przygotowane nowe rozkłady wystarczy wybierać z każdej listy wcześniejszą godzinę i dopisać do niej numer linii. W przypadku, gdy nie ma mniejszego czasu to znaczy, że są równe i należy je oddzielić o minutę.

Rozwiązanie

Funkcje pomocnicze

Funkcja naMinuty pozwala na zamianę dowolnej godziny na ilość minut, które upłynęły od północy.

1. oto naMinuty :czas
2.   niech "minuty reszta :czas 100
3.   niech "godziny (:czas - :minuty)/100
4.   wynik :minuty+:godziny*60
5. już

Funkcja naCzas konwertuje ilość minut z powrotem na czas z zachowaniem formatu ustalonego w zadaniu.

1. oto naCzas :minuty
2.   niech "godziny 0
3.   dopóki [:minuty >= 60][
4.     niech "minuty :minuty - 60
5.     zwiększ "godziny
6.   ]
7.   wynik :godziny*100 + :minuty
8. już

Funkcja rozszerz dla każdej kolejnej pary czasów przyjazdu autobusu wylicza czas pośredni, a na sam koniec zwraca posortowany rozkład.

1. oto rozszerz :l
2.   powtórz ((długość :l) - 1) [
3.     niech "a (element npw :l)
4.     niech "b (element (npw+1) :l)
5.     niech "l nak (:a + :b) / 2 :l
6.   ]
7.   wynik sortuj :l
8. już

Funkcja główna

Funkcja NRJ rozpoczyna działanie od (2. - 12.) podziału rozkładu na czasy przyjazdu dla każdej z linii, a nastepnie (13. - 14.) na dodaniu dodatkowych kursów.

1. oto NRJ :lista
2.   niech "a1 []
3.   niech "a2 []
4.   niech "w []
5.   powtórz (długość :lista) [
6.     niech "el element npw :lista
7.     jeżeli (pierw :el = 1) [
8.       niech "a1 nak naMinuty ost :el :a1
9.     ][
10.       niech "a2 nak naMinuty ost :el :a2
11.     ]
12.   ]
13.   niech "a1 rozszerz :a1
14.   niech "a2 rozszerz :a2

Dalsza część programu polega na (15. - 30.) wybieraniu wcześniejszego czasu z obu rozkładów, a następnie wstawieniu go w poprawnej formie tj. numer linii i czas przyjazdu. Oczywiście należy pamiętać, że (31. - 38.) po zakończeniu tego fragmentu kody jeden z rozkładów nie będzie pusty, dlatego dla jednego i drugiego należy przepisać pozostałe przyjazdy.

15.   dopóki [I (długość :a1 > 0) (długość :a2 > 0)][
16.     jeżeli(pierw :a1 = pierw :a2) [
17.       niech "w nak (lista 1 naCzas pierw :a1) :w
18.       niech "w nak (lista 2 naCzas ((pierw :a2) + 1)) :w
19.       niech "a1 bp :a1
20.       niech "a2 bp :a2
21.     ][
22.       jeżeli (pierw :a1 < pierw :a2) [
23.         niech "w nak (lista 1 naCzas pierw :a1) :w
24.         niech "a1 bp :a1
25.       ][
26.         niech "w nak (lista 2 naCzas pierw :a2) :w
27.         niech "a2 bp :a2
28.       ]
29.     ]
30.   ]
31.   dopóki [długość :a1 > 0][
32.     niech "w nak (lista 1 naCzas pierw :a1) :w
33.     niech "a1 bp :a1
34.   ]
35.   dopóki [długość :a2 > 0][
36.     niech "w nak (lista 2 naCzas pierw :a2) :w
37.     niech "a2 bp :a2
38.   ]
39.   wynik :w
40. już

• Rozwiązania zadań