Strona główna » Poradniki » Logomocja » LOGIA » Logia 2007/08 - Etap III
 

Logia 2007/08 - Etap III

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

Zadanie 1 (domino)

W tradycyjnej grze w domino występuje 28 kamieni. Każdy kamień składa się z 2 pól zawierających od zera do sześciu oczek. Każdy układ oczek na polach kamieni występuje tylko raz. Poniższe rysunki przedstawiają przykładowe kamienie.

Najczęściej spotykana wersja gry polega na wykładaniu przez graczy kolejnych kamieni w taki sposób, aby stykające się pola na kamieniach miały taką samą liczbę oczek. Alek, przygotowując się do turnieju, postanowił zanotować przebieg rozegranej partii, a następnie go przeanalizować. Dla ułatwienia liczbę oczek na stykających się kamieniach notował raz, pomijając powtórzenia, np. układ [1 0][0 3][3 2] zapisał jako 1032. Napisz procedurę DOMINO :gra, która narysuje przebieg gry według notatek Alka lub wypisze komunikat - Błąd. Parametr :gra jest słowem złożonym z cyfr od 0 do 6. Rysunek musi mieścić się na ekranie, jego szerokość nie może być mniejsza niż 400, kamienie układane są poziomo.

Przykłady: efekt wywołania DOMINO "0123456

wywołanie DOMINO "232 powinno wypisać komunikat Błąd.

Strategia

W celu sprawdzenia poprawności zapisanej rozgrywki należy utworzyć dodatkową liste tymczasową na której przechowywane będą dotychczas położone klocki. Jeśli klocek danego typu został już położony należy wypisać błąd. Należy zauważyć, że wedlug zapisu kładziony jest np. klocek [3 2], ale jest to ten sam klocek co [2 3], dlatego wartości na kostce domina dobrze jest posortować wtedy oba przypadki nie będą rozróżnialne.

W kwestii rysowania warto dopisać dodatkową funkcję rysującą. Jeśli przyjrzeć się jak zostały narysowane symboliczne reprezentacje wartości to wszystkie korzystają z kółek osadzonych na siatce 3×3. Oznacza to, że każdej wartości można przyporządkować pewna tablicę danych złożonych z 0 i 1, która stwierdzi, które kółka mają zostać narysowane. Przykładowo dla czterech będzie to lista [[1 0 1] [0 0 0] [1 0 1]], a dla trójki [[1 0 0] [0 1 0] [0 0 1]].

Procedura główna

Poprawność rozgrywki

Pierwsza część procedury polega na sprawdzeniu czy zapis jest poprawny. Dopiero potem można przejść do rysowania rozgrywki.

  1. oto DOMINO :gra
  2.   jeśli((długość :gra) <= 1) [
  3.     pisz "Błąd
  4.     stop
  5.   ]
  6.   niech "wyk []
  7.   powtórz ((długość :gra) - 1)[
  8.     niech "a element npw :gra
  9.     niech "b element (npw + 1) :gra
  10.     niech "p utwórzPare :a :b
  11.     jeśli(numel :p :wyk <> 0) [
  12.       pisz "Błąd
  13.       stop
  14.     ]
  15.     niech "wyk nak :p :wyk
  16.   ]

(1. - 4.) Na początek wyróżniamy przypadek, gdy zapis gry jest niepoprawny czyli, gdy jest mniej niż dwie cyfry na zapiskach. Potem (5.) deklarowana jest lista do przechowywania już wykorzystanych kostek domino. (6.) Dla każdej pary cyfr: (7. - 8.) pobierane są obie wartości na kostce i (9.) zamieniane na posortowaną listę dwuelementową. (10.) Jeśli dana kostka już była wykorzystana to: (11. - 12.) program zostaje przerwany. Jeśli jednak kostka nie była wcześniej użyta to (14.) zostaje dopisana na liste. Jeśli program nie zostanie przerwany do zakończenia pętli oznacza to, że zapis jest poprawny.

Rysowanie

Drugą część kodu można wygodnie zrealizować przy pomocy dodatkowej procedury DOMINO_el, która narysuje część kostki uwzględniając rysowaną wartość na podstawie kodu oraz wielkość kostki.

  1.   niech "w 460
  2.   niech "kody [[[0 0 0] [0 0 0] [0 0 0]]
  3.                             [[0 0 0] [0 1 0] [0 0 0]]
  4.                             [[1 0 0] [0 0 0] [0 0 1]]
  5.                             [[1 0 0] [0 1 0] [0 0 1]]
  6.                             [[1 0 1] [0 0 0] [1 0 1]]
  7.                             [[1 0 1] [0 1 0] [1 0 1]]
  8.                             [[1 1 1] [0 0 0] [1 1 1]]]
  9.   niech "n ((długość :gra) - 1) * 2
  10.   niech "a :w/:n
  11.   pod
  12.   ws :a/2 pw 90
  13.   ws :n/2*:a lw 90
  14.   opu
  15.   powtórz ((długość :gra) - 1)[
  16.     niech "ela element npw :gra
  17.     niech "elb element (npw + 1) :gra
  18.     DOMINO_el (element (:ela+1) :kody) :a
  19.     pw 90 np :a lw 90
  20.     DOMINO_el (element (:elb+1) :kody) :a
  21.     pw 90 np :a lw 90
  22.   ]
  23. już

(17. - 25.) Zadeklaruj zmienne początkowe: maksymalną szerokość rysunku oraz kody poszczególnych cyfr (i-ta lista opisuje cyfrę i - 1), ile będzie rysowanych fragmentów kostek domina :n oraz bok pojedynczego fragmentu :a. (26. - 29.) Przejdź w lewy dolny róg rysunku i (30. - 37.) narysuj każdą parę wartości.

Rysowanie fragmentu kostki

Poniżej został zamieszczony kod procedury DOMINO_el używanej do rysowania kostek:

  1. oto DOMINO_el :kod :a
  2.   niech "b :a/4
  3.   opu
  4.   powtórz 4 [
  5.     np :a
  6.     pw 90
  7.   ]
  8.   pod
  9.   pw 90 np :b
  10.   lw 90 np 3*:b
  11.   powtórz 3 [
  12.     niech "wiersz element npw :kod
  13.     pw 90
  14.     powtórz 3 [
  15.       niech "el element npw :wiersz
  16.       jeśli (:el = 1)[
  17.         kropka :b/2
  18.       ]
  19.       np :b
  20.     ]
  21.     ws :b*3 lw 90
  22.     ws :b
  23.   ]
  24.   pw 90
  25.   ws :b
  26.   lw 90
  27.   opu
  28. już

(3. - 8.) Narysuj obramowanie i (9. - 11.) przejdź do pierwszej pozycji w pierwszym rzędzie kropek. (12.) Narysuj trze wiersze po (16.) trzy kropki i (18.) rysuj kropkę tylko wtedy, gdy powiązana wartość na liście wynosi 1.

Zadanie 2 (wyspy)

Jasio postanowił zwiedzić archipelag zachodnich Wysp Kanaryjskich. Składa się on z czterech wysp: Tenerife, La Gomera, La Palma oraz El Hierro. Pomiędzy wyspami kursują promy. Odległości pomiędzy poszczególnymi wyspami przedstawia tabelka poniżej.

TenerifeLa GomeraLa PalmaEl Hierro
Tenerife×28 km85 km88 km
La Gomera28 km×58 km61 km
La Palma85 km58 km×68 km
El Hierro88 km61 km68 km×

Jasio zapisał na liście trasę, którą zamierza pokonać. Oblicz długość trasy. Napisz funkcję DT :trasa, której wynikiem jest liczba kilometrów, jaką przepłynie prom, który zawinie po kolei do wysp, których nazwy są na liście :trasa.

DT []jest 0
DT [Tenerife La Gomera El Hierro La Palma Tenerife]jest 242

Strategia

Pierwszym przyjętem założeniem będzie ignorowanie dwuliterowych przedrostków La i El, więc program niekoniecznie będzie działać z każdym zestawem danych (np. inna lista miast i odległości). W funkcji zostaną zadeklarowane dwie listy. Pierwsza z nich będzie przechowywać nazwy miejscowości, a druga to będzia lista list, gdzie i-ty element będzie listą odległości do j-tej miejscowości.

W celu znalezienia odległości za początkowe miasto przyjęte zostanie pierwsze miasto na liście. Potem zostanie określony cel i po znalezieniu odległości i jej dodaniu za aktualnie miasto należy przyjąć miasto docelowe.

Funkcja główna

    (2.) Zadeklaruj listę miast oraz (3. - 4.) tablicę odległości. (5.) Wyszczególniamy przypadek, gdy trasa podróży jest pusta: wtedy (6.) należy zwrócić 0. (7.) Jeśli jednak trasa ma pewne cele to (8.) ustal, że aktualnie Jaś znajduje się w pierwszej miejscowości na liście i (9.) aktualnie przebyty dystans wynosi 0. (10.) Dla każdego pozostałego punktu podróży, o ile (12.) nie istnieje to (13.) wybierz odległości z aktualnego miasta i (14.) wybierz odpowiednią odległość. (15.) Do przebytego dystansu dodaj znaleziony odcinek i (16.) zmień aktualne miasto pobytu. Na koniec (19.) zwróć przebyty dystans.

    Zadanie 3 (szyfr)

    Ela wymyśliła metodę szyfrowania tekstu przy pomocy klucza złożonego z małych liter alfabetu łacińskiego. Zaczęła od zapisania liter alfabetu według następujących zasad:

    1. najpierw słowo kluczowe (bez powtarzających się liter),
    2. potem pozostałe litery alfabetu.

    Na przykład dla klucza "choinka kolejność liter będzie następująca: choinkabdefgjlmpqrstuvwxyz, a dla klucza "abrakadabrahokuspokus: abrkdhouspcefgijlmnqtvwxyz.

    Ela szyfrowała każdą literę tekstu w następujący sposób - znajdowała pozycję litery w alfabecie łacińskim i odpowiadającą literę tej pozycji w swoim alfabecie. Na przykład zaszyfrowana litera "c (trzecia pozycja w alfabecie) według klucza "abrakadabrahokuspokus, to litera "r (trzecia litera w alfabecie Eli), a zaszyfrowane "d to litera "k według tego klucza.

    Grzesio pisze zaszyfrowany list do kolegi używając szyfru Eli. Napisz funkcję SZYFR :klucz :list, która pomoże Grzesiowi zaszyfrować list. Parametr :klucz jest słowem (kluczem szyfrowania) a parametr :list listą słów (listem do zaszyfrowania). Obydwa parametry składają się tylko z małych liter alfabetu łacińskiego. Wynikiem jest słowo będące zaszyfrowanym listem (spacje pomijamy).

    SZYFR "choinka [ala ma kotka i lwa]jest "cgcjcfmtfcdgwc
    SZYFR "abrakadabrahokuspokus [dookola wojtek biega wolno]jest "kiicieawipqdcbsdoawiegi

    Tworzenie klucza

    Zasada tworzenia klucza polega na przeglądaniu kolejnych liter klucza, a następnie wpisaniu tych, które do tej pory nie wystąpiły wcześniej. Podobna zasada dotyczy później dopisywania pozostałych liter alfabetu, więc oba zadania można połączyć dopisując na koniec klucza cały alfabet. Funkcja SZYFR_klucz przyjmuje jeden argument :słowo, którym jest klucz. Wynikiem jest nowy alfabet do szyfrowania.

    1. oto SZYFR_klucz :słowo
    2.   niech "s "
    3.   niech "słowo (słowo :słowo "abcdefghijklmnopqrstuvwxyz)
    4.   powtórz (długość :słowo) [
    5.     niech "el element npw :słowo
    6.     jeśli (numel :el :s = 0) [
    7.       niech "s (słowo :s :el)
    8.     ]
    9.   ]
    10.   wynik :s
    11. już

    Szyfrowanie wyrazu

    Do szyfrowania pojedynczego wyrazu służy funkcja SZYFR_szyfruj, która akceptuje szyfrowane :słowo oraz używany :alfabet.

    1. oto SZYFR_szyfruj :słowo :alfabet
    2.   niech "s "
    3.   powtórz (długość :słowo) [
    4.     niech "el element npw :słowo
    5.     niech "poz (ascii :el) - (ascii "a) + 1
    6.     niech "s (słowo :s (element :poz :alfabet))
    7.   ]
    8.   wynik :s
    9. już

    (3.) Dla każdej litery: (4.) pobierz ją i (5.) określ pozycję w alfabecie. (6.) Do wyniku dopisz literę z :alfabet z wyliczonej linijkę wcześniej pozycji :poz.

    Funkcja główna

    Teraz w głównej funkcji pozostaje wykorzystać napisane funkcje:

    1. oto SZYFR :klucz :list
    2.   niech "alfabet SZYFR_klucz :klucz
    3.   niech "s "
    4.   powtórz (długość :list) [
    5.     niech "el element npw :list
    6.     niech "f SZYFR_szyfruj :el :alfabet
    7.     niech "s (słowo :s :f)
    8.   ]
    9.   wynik :s
    10. już

    (2.) Utwórz alfabet, a potem (4.) Dla każdego wyrazu z listy: (5.) pobierz go, (6.) zaszyfruj przy pomocy wcześniej znalezionego alfabetu i (7.) połącz z dotychczasowym wynikiem.

    Zadanie 4 (anagramy)

    Ola lubi łamigłówki słowne. Interesują ją szczególnie słowa-anagramy, czyli wyrazy powstałe przez przestawienie liter innego wyrazu. Pomóż Oli pogrupować słowa-anagramy i napisz funkcję ANAGRAMY :wyrazy, której parametrem jest niepusta lista słów zbudowanych z małych liter alfabetu łacińskiego. Wynikiem funkcji jest lista list. Lista podrzędna składa się ze słów-anagramów zbudowanych z tych samych liter. Kolejność list oraz słów na liście jest dowolna.

    ANAGRAMY [kto tyran kra kot pies tok narty rak]jest [[kto kot tok][tyran narty][kra rak][pies]]

    Strategia

    Na początek napiszmy funkcję czyAnagram?, która będzie sprawdzać czy dane dwa wyrazy są anagramami. W celu porównania oba wyrazy zostaną zamienione na listę znaków funkcją naListe, następnie posortowane i porównane.

    Z kolei główna funkcja będzie w pętli wykonywać określone polecenia. Po pierwsze pobierany będzie pierwszy wyraz z listy i nazwany wzór, a następnie pozostała część listy zostanie podzielona na dwie podlisty: pierwsza z nich będzie zawierać słowa z którymi wzór jest anagramem oraz na listę tych z którymi nie. Pierwsza lista jest dopisywana do listy wynikowej, a dla drugiej listy powtarzany jest ten sam zestaw instrukcji.

    Czy anagram?

    Funkcja czyAnagram? sprawdza czy wyrazy :a i :b są anagramami.

    1. oto czyAnagram? :a :b
    2.   jeśli ((długość :a) <> (długość :b)) [
    3.     wynik "fałsz
    4.   ]
    5.   niech "alista sortuj naListe :a
    6.   niech "blista sortuj naListe :b
    7.   powtórz (długość :alista) [
    8.     jeśli (element npw :alista <>
    9.                   element npw :blista) [
    10.       wynik "fałsz
    11.     ]
    12.   ]
    13.   wynik "prawda
    14. już

    (2. - 4.) Wyklucz przypadki, gdy wyrazy nie są tej samej długości. (5. - 6.) Zamień oba wyrazy na listę znaków i każdy posortuj oddzielnie. (7. - 12.) Sprawdź czy elementy na obu listach są identyczne. (13.) Jeśli wszystkie warunki zostaną spełnione zwróć, że :a i :b są anagramami.

    W celu zamiany wyrazu na listę znaków została napisana funkcja naListe. Przyjmuje ona tylko jeden argument :słowo, którym jest wyraz do rozbicia.

    1. oto naListe :słowo
    2.   niech "l []
    3.   powtórz (długość :słowo) [
    4.     niech "l nak element npw :słowo :l
    5.   ]
    6.   wynik :l
    7. już

    Funkcja główna

    Wybieranie anagramów będzie trwało tak długo jak lista :wyrazy nie będzie pusta.

    1. oto ANAGRAMY :wyrazy
    2.   niech "w []
    3.   dopóki [
    4.     (długość :wyrazy) > 0
    5.   ][
    6.     niech "pasuje []
    7.     niech "pozostałe []
    8.     niech "wzor pierw :wyrazy
    9.     powtórz ((długość :wyrazy) - 1) [
    10.       niech "el element (npw + 1) :wyrazy
    11.       jeżeli (czyAnagram? :wzor :el)[
    12.         niech "pasuje nak :el :pasuje
    13.       ][
    14.         niech "pozostałe nak :el :pozostałe
    15.       ]
    16.     ]
    17.     niech "pasuje nak :wzor :pasuje
    18.     niech "w nak :pasuje :w
    19.     niech "wyrazy :pozostałe
    20.   ]
    21.   wynik :w
    22. już

    (2.) Dopóki (3.) lista nie jest pusta to przygotuj listę (6.) na anagramy (7.) i pozostałe. (8.) Wybierz pierwszy element jako wzór (praktycznie może być dowolny element). (9.) Dla każdego wyrazu prócz wybranego: (10.) pobierz element i (11. - 15.) przyporządkuj do odpowiedniej listy. (17.) Na koniec dopisz :wzor do listy elementów pasujących, (18.) i dopisz listę :pasuje do wyniku :w. (19.) Liste nie pasujących wyrazów przypisz zmiennej :wyraz i wróć na początek pętli.