Logia 2011/12 Etap III

Strategia

Strategia rozwiązania zadania opiera się na tym, aby sprawdzać kolejną liczbę naturalną i jeśli jest możliwe jej zapisanie przy pomocy liczb na liście to należy zwiększyć liczbę i proces powtórzyć. W końcu jeśli natrafi się na liczbę, której nie można zapisać jako sumę liczb z listy to wystarczy ją zwrócić. Oczywiście należy pamiętać, że mając daną liczbę a należy odjąć jak największą wartość z listy i proces powtórzyć, aż do otrzymania 0 lub wyczerpania liczb na liście.

Czy da się zapisać?

Funkcja SUM_Ok przyjmuje dwa parametry: :liczby - lista liczb na liście oraz :n - jaką liczbę chcemy otrzymać jak sumę tych dwóch liczb. W pętli wybieramy kolejne wartości z listy i jeśli to możliwe to odejmujemy je od :n. Jeśli po odjęciu :n wynosi 0 to zwracamy prawdę. Będzie to oznaczało, że daną liczbę :n da się otrzymać jako sumę elementów z :liczby.

1. oto SUM_Ok :liczby :n
2.   powtórz (długość :liczby) [
3.     niech "el element npw :liczby
4.     jeśli (:el <= :n) [
5.       niech "n :n - :el
6.       jeśli (:n = 0) [
7.         wynik "prawda
8.       ]
9.     ]
10.   ]
11.   wynik "fałsz
12. już

Główna funkcja

Z kolei główna funkcja SUM rozpoczyna sprawdzanie od :n = 1. Następnie zmienia kolejność elementów listy tak, aby była posortowana malejąco i po znalezieniu odpowiedniej wartości zwraca wartość :n.

1. oto SUM :liczby
2.   niech "n 1
3.   niech "liczby wspak :liczby
4.   dopóki[Sum_Ok :liczby :n][
5.     zwiększ "n
6.   ]
7.   wynik :n
8. już

Zadanie 2 (Wieża)

Strzałki na rysunku 1 opisują możliwe kierunki ruchu wieży na planszy sześciokątnej.

Rysunek 1

Rysunek 2

Napisz funkcję POLE :n :ruchy, parametr :n - oznacza liczbę sześciokątów na jednym boku i może przyjmować wartości od 2 do 1000, parametr :ruchy jest poprawną listą ruchów wieży - pól, na których zatrzymuje się wieża. Pola są reprezentowane przez dwuelementową listę liczb czerwona czarna. Liczba czerwona określa numer kolumny, a liczba czarna numer wiersza (sposób numeracji wierszy zaznaczony jest na rysunku 2). Wynikiem funkcji jest pierwsze pole odwiedzone przez wieżę po raz drugi (wieża niekoniecznie musi się na nim zatrzymać). Jeśli żadne pole nie zostanie odwiedzone dwa razy wynikiem funkcji jest 0.

POLE 4 [[4 7] [5 6] [5 4] [7 2]]	jest 0 (patrz rys. 3)
POLE 6 [[2 3] [5 6] [5 4] [1 4]]	jest [3 4] (patrz rys. 4)

Rysunek 3

Rysunek 4

Strategia i Rozwiązanie

Zauważmy, że wszystkie punkty do których ma przechodzić wieża to w rzeczywistości proste odcinki. Z każdym przejściem wartości pozycji X i Y zmieniają się o tyle samo, więc możliwe jest wyznaczenie przesunięcia na podstawie punktu początkowego i końcowego. W tym celu wystarczy obliczyć o ile przesunąła się wieża w osi X i o ile w osi Y. Na podstawie takiej informacji można wyznaczyć ile kroków jest do wykonania, ponieważ maksymalna zmiana zarówno X i Y jest o 1.

Kiedy już wiemy jakie kroki są do wykonania oraz ile ich jest możemy zapisywać wszystkie kroki na liście. Wszystkie kroki, które już na tej liście występują mogą zostać zapisane do drugiej listy. W ten sposób wystarczy sprawdzić na koniec czy lista powtarzających ruchów jest pusta. Główna funkcja POLE ma następującą postać:

1. oto POLE :n :ruchy
2.   niech "poz pierw :ruchy
3.   niech "listaRuchow (lista :poz)
4.   niech "powtRuchy []
5.   powtórz ((długość :ruchy) - 1) [
6.     niech "el element (npw + 1) :ruchy
7.     niech "zmiana :el - :poz
8.     niech "zmiana (lista POLE_min pierw :zmiana
9.                                   POLE_min ost :zmiana)
10.     dopóki [:poz <> :el][
11.       niech "poz :poz + :zmiana
12.       jeżeli(numel :poz :listaRuchow) [
13.         jeśli(numel :poz :powtRuchy = 0) [
14.           niech "powtRuchy nak :poz :powtRuchy
15.         ]
16.       ][
17.         niech "listaRuchow nak :poz :listaRuchow
18.       ]
19.     ]
20.   ]
21.   jeżeli (puste? :powtRuchy)[
22.     wynik 0
23.   ][
24.     wynik :powtRuchy
25.   ]
26. już

Kolejno od początku: (2.) za pozycję początkową przyjmujemy pierwszy element z listy, (3.) od razu dołączamy go do listy, a (4.) listę powtórzonych ruchów pozostawiamy pustą. Potem (5.) dla każdego pola prócz pierwszego: (6.) pobierz nowe pole docelowe, (7.) oblicz zmianę pozycji współrzędnych i na tej podstawie (8.) przesunięcie. Do tego korzystamy z dodakowej funkcji. Potem (10.) dopókimy nie osiągniemy pola docelowego: (11.) przesuwamy się na pole obok i (12. - 20.) sprawdzamy gdzie przypisać aktualną pozycję tj. czy listy ruchów zrobionych czy dany ruch się powtórzył. Na koniec (22. - 26.) sprawdzamy czy lista powtórzonych ruchów jest pusta i zwracamy odpowiedni wynik.

Dodatkowa funkcja POLE_min pozwala obliczyć przesunięcie w osi X lub Y. Funkcja jest potrzebna, ponieważ długość przesunięcia dzielimy przez długość przesunięcia, a ta wartość może wynieść 0, więc pojawi się błąd związany z dzieleniem przez 0.

1. oto POLE_min :a
2.   jeżeli(:a = 0)[
3.     wynik 0
4.   ][
5.     wynik :a/abs(:a)
6.   ]
7. już

Zadanie 3 (Kulki)

Ola przygotowuje dekoracje do ozdobienia klasy na dzień dziecka. Z kulek w kolorach czerwonym (r), zielonym (g), niebieskim (b) i żółtym (y) tworzy łańcuchy. Na spotkaniu klasowym ustalono, że dwie kulki w tym samym kolorze nie mogą występować obok siebie.

Pomóż Oli projektować łańcuchy i napisz funkcję KULKI :lk, której wynikiem jest posortowana lista słów reprezentujących łańcuchy, jakie można zbudować z wszystkich dostępnych kulek. Parametr :lk jest czteroelementową listą liczb określających odpowiednio liczbę kulek czerwonych, zielonych, niebieskich i żółtych. Maksymalna liczba wszystkich kulek wynosi 10.

KULKI [2 1 1 0]	jest [brgr grbr rbgr rbrg rgbr rgrb]

Rozwiązanie

Rozwiązanie

• Rozwiązania zadań