Strona główna » Poradniki » Logomocja » LOGIA » Logia 2009/10 - Etap III
 

Logia 2009/10 - Etap III

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

Zadanie 1 (statki)

W grze w statki, każdy z graczy rysuje na swojej kartce mapę o wielkości 10 na 10 kwadratowych pól. Przed rozpoczęciem gry zaznacza na mapie jeden czteromasztowiec, dwa trójmasztowce, trzy dwumasztowce oraz cztery jednomasztowce. Liczba masztów statku określa, ile sąsiednich pól zajmuje on na mapie. Statki można ustawiać dowolnie, poziomo lub pionowo, nie wolno ich jednak wyginać. Różne statki nie mogą zajmować sąsiednich pól, ani stykać się rogami.

Napisz procedurę STATKI, po wywołaniu której na ekranie zostanie narysowana plansza do gry w statki, o boku długości 400, wraz z losowo (ale poprawnie) rozmieszczonymi statkami, widocznymi jako zamalowane pola.Poniżej przykładowy efekt wywołania procedury STATKI.

Strategia rozkładania

Jednym z najprostszych sposobów na rozkładanie jest ustawienie statków w kolejności od największego do najmniejszego. Pozwoli to na znalezienie rozwiązania niezależnie od pozycji ustawiania kolejnych statków. Wszystko to dzięki temu, że nie ma wtedy problemu, że małe statki mogą zablokować miejsce dla dużych statków, a z kolei dla mniejszych statków wielkości 1 pozycję jest bardzo łatwo znaleźć.

Rozwiązanie

Rozwiązywanie zadania można podzielić na dwa etapy. Pierszy z nich polega na znalezieniu mapy rozmieszczenia statków, a drugi to narysowanie na podstawie znalezionej mapy planszy. Rozpocznijmy od części kodu poszukującej rozwiązania:

  1. oto STATKI
  2.   niech "mapa []
  3.   powtórz 10 [
  4.     niech "wiersz []
  5.     powtórz 10 [
  6.       niech "wiersz nak 0 :wiersz
  7.     ]
  8.     niech "mapa nak :wiersz :mapa
  9.   ]
  10.   niech "statki [4 3 3 2 2 2 1 1 1 1]
  11.   powtórz (długość :statki) [
  12.     niech "el element npw :statki
  13.     niech "pozx (losowa 10) + 1
  14.     niech "pozy (losowa (10 - :el)) + 1
  15.     niech "dopostawienia "prawda
  16.     niech "o (losowa 2)
  17.     niech "zx reszta :o 2
  18.     niech "zy reszta (:o + 1) 2
  19.     dopóki [:dopostawienia][
  20.       jeżeli (STATKI_sprawdz :mapa :el :pozx :pozy :zx :zy) [
  21.         niech "dopostawienia "fałsz
  22.         niech "mapa STATKI_ustaw :mapa :el :pozx :pozy :zx :zy
  23.       ][
  24.         niech "pozx :pozx + 1
  25.         jeśli (:pozx = 11) [
  26.           niech "pozx 1
  27.           niech "pozy :pozy + 1
  28.         ]
  29.         jeśli (:pozy = 11) [
  30.           niech "pozy 1
  31.         ]
  32.       ]
  33.     ]
  34.   ]

Na początku działania programu należy (2. - 9.) utworzyć mapę. Jest to tablica dwuwymiarowa 10x10. Następnie (10.) deklarowane są statki do umieszczenia na planszy. Listę tę można zmodyfikować w dowolny sposób np. dodając pięciomasztowiec, ale należy się liczyć z faktem, że utworzona plansza może być za mała na ustawienie danego zestawu statków. (11.) Dla każdego statku: (12.) pobierana jest jego wartość i zapamiętana jako :el. Następnie losowana jest (13. - 14.) pozycja. (15.) Zmienna :dopostawienia jest to zmienna, która sprawdza czy statek wymaga ustawienia. (16.) Losowanie orientacji jest dokonywane poprzez wylosowanie wartości 0 lub 1. Na jej podstawie określa się (17. - 18.) orientację statku. Zakładamy, że na pozycji (x, y) ustawia się statek na kolejne pola w dół, albo na kolejne w prawo. Wylosowane wartości nie zawsze oznaczają, że wylosowana pozycja jest poprawna. Z tego powodu (19.) dopóki statek wymaga ustawienia to: (20.) należy sprawdzić daną pozycję i jeśli pasuje to (21.) zgłaszamy, że statek został ustawiony oraz (22.) ustawiamy statek na planszy. Jednak w przypadku, gdy pozycja jest niepoprawna to (24. - 31.) przehcodzimy po kolejnych polach mapy, aż do znalezienia odpowiedniej pozycji.

Sprawdzanie pozycji odbywa się poprzez funkcję STATKI_sprawdz, która przyjmuje kolejno :mapa - mapę planszy, :dl - długość statku, :pozx i :pozy - kolejno współrzednie "poczatku planszy" oraz przesunięcie jego kolejnych części o (:zx, :zy).

    Działanie opiera się na sprawdzaniu (2.) dla każdego pola na którym ma stać statek czy (3. - 11.) nie będzie stykać się z innym statkiem lub nie wyjdzie poza planszę. Jeśli pole pasuje to (12. - 13.) modyfikujemy aktualne pole. Należy pamiętać, że (14. - 16.) możliwe jest wyjście poza mapę, więc należy upewnić się czy następne pole będzie poprawne. Ze względu na fakt, że kolejne części statku są dokładane do dołu i na prawo to wystarczy sprawdzić współrzędne :pozx i :pozy nie są większy od 10.

    Analogicznie działającą funkcją jest ustawianie statku na planszy. Przyjmuje podobne argumenty, ale nie sprawdza poprawności ustawienia.

    1. oto STATKI_ustaw :mapa :dl :pozx :pozy :zx :zy
    2.   powtórz (:dl) [
    3.     niech "wiersz element :pozy :mapa
    4.     niech "wiersz zastąp :pozx :wiersz 1
    5.     niech "mapa zastąp :pozy :mapa :wiersz
    6.     niech "pozx :pozx + :zx
    7.     niech "pozy :pozy + :zy
    8.   ]
    9.   wynik :mapa
    10. już

    Rysowanie planszy

    W celu narysowania planszy wystarczy poniższy kod:

    1.   niech "w 400
    2.   niech "a :w/10
    3.   pod
    4.   ws :w/2 pw 90
    5.   ws :w/2 lw 90
    6.   opu
    7.   powtórz 10 [
    8.     niech "wiersz element (10 - npw + 1) :mapa
    9.     powtórz 10 [
    10.       niech "kolor "biały
    11.       jeśli (element npw :wiersz = 1) [
    12.         niech "kolor "zielony
    13.       ]
    14.       wielokąt [
    15.         ukm :kolor
    16.         powtórz 4 [
    17.           np :a
    18.           pw 90
    19.         ]
    20.       ]
    21.       pod
    22.       pw 90 np :a
    23.       lw 90
    24.       opu
    25.     ]
    26.     pod
    27.     pw 90 ws :w
    28.     lw 90 np :a
    29.     opu
    30.   ]
    31. już

    Zadanie 2 (kostka i moneta)

    Gra, w którą bawią się dzieci, wymaga użycia jednej sześciennej kości (na jej ścianach jest od 1 do 6 oczek, suma liczby oczek na przeciwległych ścianach wynosi 7) i jednej polskiej monety. Rozpoczyna się od rzutu kością. Następnie grający rozgrywają kolejne tury gry. Tura polega na tym, że każdy z grających najpierw rzuca monetą, a następnie obraca kość:

    • jeśli wypadł orzeł, to górną ścianą kości staje się ta z bocznych ścian, na której jest najwięcej oczek,
    • jeśli wypadła reszka, to górną ścianą kości staje się ta z bocznych ścian, na której jest najmniej oczek.

    Liczba punktów zebranych przez gracza jest sumą liczby oczek widniejących na górnej ścianie kości po obrotach wykonanych przez tego gracza w rozegranych przez niego turach.

    Napisz funkcję GRA :kość :moneta :limit, analizującą przeprowadzoną grę.

    Parametr :kość to liczba oczek na górnej ścianie kości po jej rzucie na początku gry. Parametr :moneta jest listą składającą się z list będących zapisami kolejnych tur. Zapis jednej tury jest listą składającą się z liter o i/lub r, oznaczających odpowiednio, orła bądź reszkę, wyrzucone monetą przez kolejnych graczy.

    Wynikiem funkcji jest lista zawierająca tyle elementów, ilu jest graczy. Każdy kolejny element tej listy jest numerem najwcześniejszej tury, w której liczba punktów zebranych przez kolejnego gracza osiągnęła co najmniej :limit (będący wartością trzeciego parametru funkcji), bądź zero, gdy :limit nie został przez niego osiągnięty do końca gry.

    GRA 3 [[o r][r r][r o]] 7jest [2 3]
    GRA 4 [[o][r][r]] 7jest [2]
    GRA 4 [[o r r][r o r]] 5jest [1 2 0]

    Strategia

    Podczas rozwiązywania zadania należy pamiętać, że jeśli kostka ma u góry wartość x to od spodu ma wartość 7 - x czyli ze wszystkich możliwości ścian: [1 2 3 4 5 6] nie ma na niej x i 7 - x. Jeśli z posortowanej listy usunie się obydwie wartości to pierwszy element na liście będzie szukanym minimum dla danego rzutu monetą, a ostatni szukanym maksimum.

    Rozwiązanie

    Poniżej zostało zamieszczone pełne rozwiązanie zadania:

    1. oto GRA :kość :moneta :limit
    2.   niech "tura []
    3.   niech "wyniki []
    4.   powtórz (długość (pierw :moneta)) [
    5.     niech "wyniki nak 0 :wyniki
    6.     niech "tura nak 0 :tura
    7.   ]
    8.   powtórz (długość :moneta) [
    9.     niech "numertury npw
    10.     niech "el element npw :moneta
    11.     powtórz (długość :el) [
    12.       niech "lista [1 2 3 4 5 6]
    13.       niech "lista be :kość :lista
    14.       niech "lista be (7 - :kość) :lista
    15.       jeżeli ((element npw :el) = "r) [
    16.         niech "kość pierw :lista
    17.       ][
    18.         niech "kość ost :lista
    19.       ]
    20.       niech "punkty (element npw :wyniki) + :kość
    21.       niech "wyniki zastąp npw :wyniki :punkty
    22.       jeśli (I (:punkty >= :limit)
    23.                         (element npw :tura = 0)) [
    24.         niech "tura zastąp npw :tura :numertury
    25.       ]
    26.     ]
    27.   ]
    28.   wynik :tura
    29. już

    (2. - 7.) Na początku działania funkcji GRA należy utworzyć tablicę do przeszukiwania wyników dla kolejnych graczy. Następnie (8.) dla kolejnych rzutów monetą: (9.) zapamiętajemy numer tury i pobieramy kolejny element z listy :moneta. (10.) Dla każdego rzutu monetą: (11.) przygotowywujemy posortowaną tablicę wartości kości i (12. - 13.) usuwamy z niej dwie wartości. Potem (14. - 18.) na podstawie wylosowania reszki czy orła wybieramy odpowiedni element. (19. - 20.) Dodajemy go do wyniku odpowiedniego gracza oraz sprawdzamy (21. - 24.) czy dany gracz osiągnął ustalony :limit. Jednak nalezy pamiętać, że :limit raz osiągnięty będzie osiągnięty w kolejnych turach, więc należy upewnić się, że dany gracz już wcześniej nie osiągnął. Na koniec (27.) zwracamy listę :tura.

    Zadanie 3 (autobusy)

    Odległości między sąsiednimi przystankami każdej linii w całej sieci autobusowej, obejmującej nie więcej niż sto przystanków, są identyczne. Napisz funkcję DROGA :linie :p1 :p2. Parametr :linie jest poprawną listą list, z których każda opisuje jedną linię. Opis linii jest listą numerów przystanków, przez które ta linia przebiega, przy czym zakładamy, że linia kursuje dwukierunkowo, tj. od pierwszego przystanku do ostatniego, a następnie od ostatniego do pierwszego. Wynikiem funkcji jest minimalna liczba przystanków (dokładniej: odcinków między przystankami), jaką należy przebyć, aby przejechać z przystanku o numerze :p1 do przystanku o numerze :p2 bez przesiadek, bądź -1, jeśli nie ma bezpośredniego połączenia.

    DROGA [[1 2 3 4 5][6 5 4 9 8 5 2] [1 6 5 8 9]] 1 5jest 2 (bo pierwszą linią musimy przejechać cztery przystanki, druga nie łączy interesujących nas przystanków, a trzecią musimy przejechać dwa przystanki),
    DROGA [[2 4 3 1][4 2 1 3]] 2 1jest 1 (pierwszą linią trzy przystanki, drugą jeden),
    DROGA [[4 3 2 1][3 2]] 2 3jest 1 (obiema liniami wystarczy przejechać jeden przystanek).

    Rozwiązanie

    Dla każdej linii należy pamiętać, aby znaleźć pozycję jednego i drugiego przystanku. Odległością będzie wartość absolutna różnicy pozycji tych przystanków (docelowy przystanek może być wcześniej od początkowego). Poniżej zostało przedstawione przykładowe rozwiązanie:

    1. oto DROGA :linie :p1 :p2
    2.   niech "min -1
    3.   powtórz (długość :linie) [
    4.     niech "el element npw :linie
    5.     niech "trasa zd :el wspak bo :el
    6.     niech "poz numel :p1 :trasa
    7.     niech "trasa odElementu :p1 :trasa
    8.     niech "poz2 numel :p2 :trasa
    9.     jeśli (:poz <> 0) [
    10.       niech "odl :poz2 - 1
    11.       jeśli (LUB (:min = -1) (:odl < :min)) [
    12.         niech "min :odl
    13.       ]
    14.     ]
    15.   ]
    16.   wynik :min
    17. już

    (2.) Początkowo przyjmujemy, że nie istnieje bezpośrednie połączanie. Nastepnie (3.) dla każde linii autobusowej: (4.) pobieramy kolejne trasy i (5. - 6.) szukamy pozycji przystanków na trasie. Warunkiem obliczenie odległości (7.) jest to, że oba przystanki na trasie występują. Jeśli tak to (8.) wyliczamy odległość pomiędzy przystankami i (9. - 11.) sprawdzamy czy jest to najkrótsze połączenie. Na koniec (14.) zwracamy wartość minimalną :min.

    Zadanie 4 (autobusy)

    Robot Gerard potrafi wykonać tylko cztery polecenia, nakazujące mu przejść w jedną z czterech stron świata. Napisz funkcję ROBOT :trasa, której wynikiem jest liczba odcinków, które robot przebył więcej niż raz. Parametr :trasa jest słowem opisującym sekwencję poleceń, w którym mogą występować jedynie litery N, S, W oraz E. Litery te oznaczają odpowiednio polecenie ruchu w kierunku północnym, południowym, zachodnim oraz wschodnim. Gerard może wykonać maksymalnie 500 ruchów.

    ROBOT "NESWjest 0
    ROBOT "NESWNESWjest 4
    ROBOT "NNNESSSSWNNNEjest 2

    Strategia

    Implementacja zadania jest bardzo podobna do zadania 3 z poprzedniego etapu. Wtedy należało sprawdzić, które punkty robot odwiedził dwa razy. Tu z kolei należy sprawdzić, które odcniki drogi odwiedzi dwa razy. Zadanie można rozwiązać przy pomocy tego samo szkieletu rozwiązania. Mianowicie tym razem zamiasy przechowywać kolejnych punktów należy przechować posortowaną listę złożoną z dwóch punktów: początkowego i końcowego. Posortowanie jest bardzo ważne, ponieważ inaczej przejście z (a, b) na (c, d) odróżniałby od przejścia (c, d) na (a, b).

    Rozwiązanie

    1. oto ROBOT :trasa
    2.   niech "pozx 0
    3.   niech "pozy 0
    4.   niech "pozlista [[[0 0] [0 0]]]
    5.   niech "ile 0
    6.   powtórz (długość :trasa) [
    7.     niech "el (element npw :trasa)
    8.     niech "poz1 (lista :pozx :pozy)
    9.     wybierz (:el) [
    10.       N [niech "pozy :pozy + 1]
    11.       E [niech "pozx :pozx - 1]
    12.       W [niech "pozx :pozx + 1]
    13.       S [niech "pozy :pozy - 1]
    14.     ]
    15.     niech "poz2 (lista :pozx :pozy)
    16.     niech "poz sortuj (lista :poz1 :poz2)
    17.     jeżeli (numel :poz :pozlista = 0) [
    18.       niech "pozlista nak :poz :pozlista
    19.     ][
    20.       niech "ile :ile + 1
    21.     ]
    22.   ]
    23.   wynik :ile
    24. już

    W rozwiązaniu kolejno: (2. - 3.) ustalana jest pozycja wejściowa oraz (4.) wykonany ruch i (5.) licznik do zliczania odcinków po których robot przeszedł dwa razy lub więcej. (6.) Dla każdego elementu trasy :trasa: (7.) pobiera kierunek kolejnego ruchu i (8.) utworzeniu listy reprezentujacej punkt początkowy. Nastepnie (9. - 14.) wykonywane jest przesunięcie w odpowiednim kierunku. Po przejściu można (15.) utworzyć kolejny punkt i (16.) utworzyć drogę przejścia robota złożoną z punktu początkowego i końcowego, posortowaną. (17.) Jeśli dane przejście nie wystąpiło to (18.) dopisujemy na listę, a jeśli wystąpiło to (20.) zwiększamy licznik :ile. Na koniec (23.) zwracamy licznik :ile.