Strona główna » Poradniki » Logomocja » LOGIA » Logia 2012/13 Etap III
 

Logia 2012/13 Etap III

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

Zadanie 1 (Przekładanie kulek)

Olek i Ala bawią się czerwonymi i zielonymi kulkami oraz zestawem pudełek ułożonych w rzędzie. Ala wkłada kulki do pudełek, po jednej do każdego. Następnie Olek przekłada kulki, wyjmując dowolne dwie z nich i zamieniając je miejscami. Zabawa kończy się, gdy uzyskany zostanie dwubarwny naprzemienny układ:

w pierwszym pudełku kulka czerwona, w drugim zielona, w trzecim czerwona, w czwartym zielona itd. Jeśli zabraknie kulek jednego koloru, to na końcu rzędu pozostaje ciąg kulek w drugim kolorze. Olek stara się uporządkować kulki w możliwie najmniejszej liczbie kroków, aby Ala nie zaczęła się nudzić.

Pomóż Olkowi i napisz funkcję KULKI :s obliczającą, ile co najmniej zamian musi wykonać. Parametr :s jest niepustym słowem złożonym z liter c oraz z, o maksymalnej długości 100, opisującym początkowy układ kulek.

KULKI "czczczzzjest 0 (kulek nie trzeba przekładać)
KULKI "czczzczzjest 1 (wystarczy zamienić miejscami kulki z piątego i szóstego pudełka, aby otrzymać końcowy układ)

Rozwiązanie

    Zadanie 2 (Okrągły stół)

    Przy okrągłym stole siedzi n uczestników spotkania, na krzesłach ponumerowanych od 1 do n. Kolejno co k-ta osoba wstaje i opuszcza spotkanie. Zadaniem Antka jest wskazanie osoby, która pozostanie przy stole jako ostatnia.

    Pomóż Antkowi i napisz funkcję OSTATNI :n :k. Wynikiem funkcji jest numer krzesła zajętego przez uczestnika spotkania, który pozostanie przy stole. Parametry :n i :k mogą przyjmować wartości z zakresu od 1 do 100.

    OSTATNI 7 3jest 4 (kolejne osoby, opuszczające spotkanie, siedzą na krzesłach o numerach: 3, 6, 2, 7, 5, 1)
    OSTATNI 6 2jest 5 (kolejne osoby, opuszczające spotkanie, siedzą na krzesłach o numerach: 2, 4, 6, 3, 1)

    Rozwiązanie

    Strategia rozwiązania polega na przygotowaniu listy gości przy stole, a następnie usuwać co :k-tą osobę z listy. W cely powrotu do początku listy można skorzystać z funkcji modulo (tj. reszta z dzielenia). Kod rozwiązania przedstawia się następująco:

    1. oto OSTATNI :n :k
    2.   niech "stół []
    3.   powtórz (:n) [
    4.     niech "stół nak npw :stół
    5.   ]
    6.   niech "osoba :k
    7.   dopóki [(długość :stół <> 1)] [
    8.     niech "stół bezElNum :osoba :stół
    9.     niech "osoba :osoba + :k - 1
    10.     niech "osoba (reszta (:osoba - 1) (długość :stół)) + 1
    11.   ]
    12.   wynik pierw :stół
    13. już

    (2.) Deklaruje listę i (3. - 5.) wrzucamy wszystkie numery osób przy stole. Następnie (6.) w pętli dopóki przy stole siedzi więcej osób niż jedna to: (7.) usuń odpowiednią osobe przy stole, (8.) wylicz pozycję następnej osoby i (9.) oblicz jej pozycję na liście, ponieważ wskazany indeks może nie istnieć i wtedy należy zacząć wybierać od początku listy. Na koniec (11.) zwróć jedyną osobę na liście.

    Zadanie 3 (Liczby binarne)

    Ola uwielbia zabawy z liczbami. Wie także, że w systemie dwójkowym występują tylko dwie cyfry: zero i jedynka. Ola lubi powtarzające się układy elementów, więc wymyśliła następujące zadanie:

    Prosi mamę o podanie liczby dwójkowej i szuka najmniejszej liczby, jaką należy odjąć od podanej przez mamę, aby w wyniku powstała liczba, w której pierwsza cyfra jest jedynką, druga zerem, trzecia jedynką itd.

    Pomóż Oli i napisz funkcję ILEOD :liczba. Parametr :liczba jest słowem reprezentującym liczbę dodatnią w systemie dwójkowym. Wynikiem funkcji jest słowo reprezentujące najmniejszą liczbę binarną, jaką należy odjąć od parametru, aby otrzymać liczbę, w której naprzemiennie występują jedynki i zera. Długość parametru :liczba jest nie większa niż 30.

    ILEOD "101jest "0
    ILEOD "111jest "10
    ILEOD "1101jest "11

    Strategia

    Do rozwiązania tego zadania przydadzą się funkcje, które pozwolą przeliczyć liczbę w systemie binarnym na dziesiętny oraz odwrotnie. Następnie różnica liczby wejściowej oraz liczby, która ma naprzemiennie 0 i 1 w zapisie binarnym przeliczona na system binarny jest najmniejszą wartością, którą trzeba oddać.

    Poniższa funkcja ILEOD_na2 pozwala przeliczyć dowolną liczbę w systemie dziesiętnym na liczbę zapisaną binarnie.

    1. oto ILEOD_na2 :a
    2.   niech "p 1
    3.   dopóki [:p*2 <= :a][
    4.     niech "p :p*2
    5.   ]
    6.   niech "s "
    7.   dopóki [:p <> 0.5][
    8.     jeżeli (:p <= :a) [
    9.       niech "s (słowo :s "1)
    10.       niech "a :a - :p
    11.     ][
    12.       niech "s (słowo :s "0)
    13.     ]
    14.     niech "p :p/2
    15.   ]
    16.   wynik :s
    17. już

    W celu przeliczania liiczby binarnej na dziesiętną należy wywołać funkcję ILEOD_na10, która zwróci wartość zapisu binarnego w postaci dziesiętnej.

    1. oto ILEOD_na10 :s
    2.   niech "s wspak :s
    3.   niech "p 1
    4.   niech "a 0
    5.   powtórz (długość :s) [
    6.     jeśli (element npw :s = "1) [
    7.       niech "a :a + :p
    8.     ]
    9.     niech "p :p*2
    10.   ]
    11.   wynik :a
    12. już

    Z tak przygotowanymi funkcjami można przejść do napisania głównej funkcji ILEOD. Oto jej kod:

    1. oto ILEOD :liczba
    2.   niech "s "
    3.   powtórz (długość :liczba) [
    4.     niech "s nak (reszta npw 2) :s
    5.   ]
    6.   niech "a ILEOD_na10 :liczba
    7.   niech "b ILEOD_na10 :s
    8.   wynik ILEOD_na2 (:a - :b)
    9. już

    Na początku działania funkcji: (2. - 5.) wyznaczamy docelową liczbę binarną. Następnie przeliczamy (6.) liczbę wejściową oraz (7.) docelową na system dziesiętny. Dla takiej wartości jesteśmy w stanie wyznaczyć różnicę czyli to o ile będzie trzeba odjąć. Rzecz jasna musi być ona zapisana binarnie, więc (8.) przeliczamy na system binarny różnicę poprzednio przeliczonych wartości.

    Zadanie 4 (Latarnie)

    Na prostokątnym placu stoją w rzędach latarnie. Kuba ma rozstrzygnąć, pod którą latarnią jest najjaśniej. Liczba latarń w każdym rzędzie jest taka sama. Odległości pomiędzy sąsiednimi latarniami w rzędzie i pomiędzy rzędami są identyczne. Każda z latarń emituje światło o natężeniu określonym liczbą od 0 (nie świeci - zepsuła się lub nikt jej nie włączył) do 9.

    Latarnia oświetla miejsce, na którym stoi, a także miejsca pod ośmioma (lub mniej, jeśli znajduje się na krawędzi placu) latarniami, w następujący sposób:

    • miejsce, gdzie stoi latarnia, jest oświetlane przez nią z jasnością równą natężeniu światła tej latarni,
    • miejsca pod sąsiednimi latarniami w rzędzie, a także stojącymi na tych samych pozycjach w dwóch sąsiednich rzędach, są przez nią oświetlone z dwukrotnie mniejszą jasnością,
    • miejsca pod latarniami stojącymi najbliżej na skos od danej latarni (tj. znajdujące się w sąsiednich rzędach na pozycji różniącej się o jeden), są przez nią oświetlone z trzykrotnie mniejszą jasnością,
    • zaniedbujemy wpływ latarni na oświetlenie miejsc położonych dalej niż ww., pomijamy wysokość latarni.

    Wyznaczając jasność w danym miejscu sumujemy składowe jasności.

    Pomóż Kubie i napisz funkcję MAXJ :latarnie, której wynikiem jest dwuelementowa lista określająca numer rzędu i numer latarni, pod którą jest najjaśniej. Parametr :latarnie jest listą list opisujących kolejne rzędy. Każdy rząd opisany jest listą zawierającą jednocyfrowe liczby określające natężenie światła kolejnych latarń w tym rzędzie. Zakładamy, że dane są tak dobrane, że jest tylko jedna latarnia, pod którą jest najjaśniej. Liczby rzędów i latarń w rzędzie są dodatnie, nie większe niż 20.

    MAXJ [[1 2 3 2][0 0 1 2]]jest [1 3]
    MAXJ [[8 1 1][4 6 0][6 2 1]]jest [2 1]
    MAXJ [[1][6][3][5][3]]jest [3 1]

    Rozwiązanie