Strona główna » Poradniki » Logomocja » LOGIA » Logia 2011/12 Etap II
 

Logia 2011/12 Etap II

https://mattomatti.com/li112
· Etap I · Etap II · Etap III ·
Oryginalna treść zadań jest dostępna pod oficjalnym adresem konkursu LOGIA

Zadanie 1 (Obrazkowa liczba)

Kolejnym cyfrom odpowiadają obrazki przedstawione na rysunkach poniżej:

Napisz procedurę OL :s, która tworzy na środku ekranu rysunek zaszyfrowanej liczby reprezentowanej przez parametr :s. Parametr :s jest słowem złożonym z minimalnie 2, a maksymalnie 40 cyfr. Odstęp pomiędzy szyfrowanymi cyframi wynosi połowę szerokości cyfry 0. Szerokość całego rysunku wynosi 720.

OL 45432

Rozwiązanie

Rysowanie Figur

Jak można zauważyć z przedstawionych rysunków cyfry od 0 do 8 powstają poprzez dodawanie zaledwie jednego elementu i jedynie cyfra 9 nie jest kwadratem i w żaden sposób się nie łączy. Jednym z pomysłów na narysowanie tych figur jest napisania procedury OL_Element, która na podstawie wybranej cyfry wybiera co narysować i potrafi dla każdej cyfry mniejszej od 9 wywołać funkcję dla poprzedniej cyfry.

  1. oto OL_Element :a :n
  2.   niech "pos poz
  3.   skieruj 0
  4.   wybierz (:n) [
  5.     9 [
  6.       opu
  7.       powtórz 2 [
  8.         np :a pw 90
  9.         np :a/2 pw 90
  10.       ]
  11.       pw 90 np :a/2
  12.       lw 90
  13.     ]
  14.     8 [
  15.       pod
  16.       pw 90 np :a*3/4
  17.       lw 90 opu
  18.       np :a
  19.       pod ustalPoz :pos
  20.       OL_element :a (:n - 1)
  21.     ]
  22.     7 [
  23.       pod
  24.       pw 90 np :a/4
  25.       lw 90 opu
  26.       np :a
  27.       pod ustalPoz :pos
  28.       OL_element :a (:n - 1)
  29.     ]
  30.     6 [
  31.       pod
  32.       np :a/2 pw 90
  33.       opu
  34.       np :a
  35.       pod ustalPoz :pos
  36.       OL_element :a (:n - 1)
  37.     ]
  38.     5 [
  39.       pod
  40.       np :a pw 90
  41.       opu
  42.       np :a
  43.       pod ustalPoz :pos
  44.       OL_element :a (:n - 1)
  45.     ]
  46.     4 [
  47.       pod
  48.       pw 90
  49.       opu
  50.       np :a
  51.       pod ustalPoz :pos
  52.       OL_element :a (:n - 1)
  53.     ]
  54.     3 [
  55.       pod
  56.       pw 90 np :a/2
  57.       lw 90
  58.       opu
  59.       np :a
  60.       pod ustalPoz :pos
  61.       OL_element :a (:n - 1)
  62.     ]
  63.     2 [
  64.       pod
  65.       pw 90 np :a
  66.       lw 90
  67.       opu
  68.       np :a
  69.       pod ustalPoz :pos
  70.       OL_element :a (:n - 1)
  71.     ]
  72.     1 [
  73.       opu
  74.       np :a
  75.       pod ustalPoz :pos
  76.       OL_element :a (:n - 1)
  77.     ]
  78.     0 [
  79.       opu
  80.       pw 45 np :a*pwk(2)
  81.       lw 45
  82.       pod ws :a lw 45 opu
  83.       np :a*pwk(2)
  84.       ws :a*pwk(2)
  85.       pw 45
  86.     ]
  87.   ]
  88. już

W celu szybszego powrotu do punktu początkowego rysowania (2.) zapamiętywana jest pozycja przed rozpoczęciem rysowania i żółw (3;) zawsze jest skierowany do góry, aby uniknąć problemów powstałych wskutek obracania podczas rysowania.

Procedura Główna

W celu poprawnego narysowania na początku (2. - 10.) wyliczana jest łącza liczba długości podstaw figur oraz przestrzeni pomiędzy nimi. Na podstawie tej wartości jest (11.) wyliczany bok :a kwadratu cyfr od 0 do 8.

  1. oto OL :s
  2.   niech "ile ((długość :s) - 1)/2
  3.   powtórz (długość :s) [
  4.     jeżeli(element npw :s <> 9)[
  5.       zwiększ "ile
  6.     ][
  7.       niech "ile :ile + 0.5
  8.     ]
  9.   ]
  10.   niech "a 720 / :ile
  11.   pod
  12.   lw 90 np 360
  13.   pw 90
  14.   opu
  15.   powtórz (długość :s) [
  16.     OL_Element :a (element npw :s)
  17.     pod
  18.     pw 90 np :a/2
  19.     lw 90
  20.     opu
  21.   ]
  22. już

Po obliczeniu boku :a procedura (12. - 15.) przechodzi w lewy dolny róg rysunku i (16. - 22.) rysuje wszystkie cyfry. Wykorzystany zostaje tu fakt, że procedura OL_Element rozpoczyna rysowanie cyfry w jej lewym dolnym rogu, a kończy w prawym dolnym.

Zadanie 2 (Ile cyfr)

Napisz funkcję IleCyfr :liczba :podstawa, której wynikiem jest liczba cyfr liczby podanej jako pierwszy parametr w układzie o podstawie podanej jako drugi parametr. Parametr :liczba jest nieujemną liczbą całkowitą zapisaną w układzie dziesiętnym nie większą niż 1020, parametr :podstawa jest liczbą całkowitą większą od 1 i mniejszą niż 17.

IleCyfr 123456 10jest 6
IleCyfr 1 5jest 1
IleCyfr 255 2jest 8
IleCyfr 255 16jest 2

Rozwiązanie

Podczas zapisywania liczby w innej podstawie najpierw należy wyznaczyć liczbę najbardziej znaczącą czyli pierwszą od lewej. Jej wartość to :podstawa podniesiona do pozycji liczby od prawej - 1. Oto kod znajdujący taką potęge p, że jest mniejsza od :liczba. Zmienna :ile przechowuje, która to jest potęga.

  1. oto IleCyfr :liczba :podstawa
  2.   niech "ile 1
  3.   niech "p 1
  4.   dopóki [:p * :podstawa < :liczba][
  5.     niech "p :p * :podstawa
  6.     zwiększ "ile
  7.   ]
  8.   wynik :ile
  9. już
Więcej informacji na temat przeliczania liczbowych można znaleźć w tym artykule.

Zadanie 3 (Miasta)

Alicja, Tomek i Zuzanna planują wakacyjny wyjazd. Podczas podróży odwiedzą od 2 do 7 miejscowości. Ustalili już wspólną listę tych miejscowości, mają jednak problem z wyborem kolejności odwiedzanych miejsc. Każde z dzieci ma swoje preferencje.

Na przykład Alicja chce odwiedzić najpierw Poznań, potem Łódź i Kraków, a na końcu Warszawę (PŁKW). Tomek chce odwiedzić najpierw Warszawę, potem Poznań, następnie Łódź, na końcu Kraków (WPŁK). Zuzanna chciałaby, żeby zacząć od Poznania, potem pojechać do Warszawy, Krakowa, a Łódź zostawić na koniec (PWKŁ).

Pomóż im podjąć decyzję tak, aby zaproponowana kolejność odwiedzania miast różniła się jak najmniej od preferowanej przez każdego uczestnika wycieczki. Ocenę rozwiązania znajdujemy licząc łączną liczbę par miast występujących w dwóch propozycjach w innej kolejności.

Na przykład kolejność Alicji to PŁKW, Tomka - WPŁK, Zuzanny - PWKŁ. Najlepsza ocena (minimalna łączna liczba zmian kolejności miejscowości) to 4, a najlepszy wybór to PWŁK, ponieważ dla Alicji oznacza to dwie zmiany kolejności (Kraków - Warszawa i Łódź - Warszawa), dla Tomka jedną (Warszawa - Poznań) i dla Zuzanny też jedną (Kraków - Łódź).

Napisz funkcję Miasta :A :T :Z, której wynikiem dla danej preferencji trójki osób będzie słowo reprezentujące kolejność odwiedzanych miejscowości o najlepszej ocenie. Jeśli kilka kolejności ma taką samą ocenę, wynikiem funkcji może być dowolna z nich.

Parametry :A, :T, :Z (a także wynik funkcji) są słowami tej samej długości reprezentującymi kolejność odwiedzania miejscowości, wszystkie dzieci wskazują te same miejscowości reprezentowane przez pojedyncze litery. Nazwy miejscowości zaczynają się od różnych liter.

Miasta "PŁKW "WPŁK "PWKŁjest PWŁK
Miasta "TSG "TGS "GSTjest TGS

Strategia

W celu znalezienia optymalnego rozwiązania warto wyznaczyć wszystkie możliwe kombinacje ustawień kolejności miast. Następnie dla każdego z ustawień wybrać to, które będzie miało najmniejszą różnicę z planami Alicji, Tomka i Zuzanny.

Rozwiązanie

Różnica w planach

Rozpocznijmy najpierw od zliczania różnic pomiędzy dwoma planami. Najprostszym sposobem jest wybór każdej możliwej pary miast, a następnie sprawdzenie ile z nich nie jest w tej samej kolejności co w planie. W celu wybrania par wystarczą dwie pętle.

  1. oto Miasta_Roznica :a :b
  2.   niech "ile 0
  3.   powtórz (długość :a) [
  4.     niech "i npw
  5.     powtórz ((długość :a) - npw) [
  6.       niech "j npw + :i
  7.       jeśli (numel (element :i :b) :a >
  8.                     numel (element :j :b) :a) [
  9.         zwiększ "ile
  10.       ]
  11.     ]
  12.   ]
  13.   wynik :ile
  14. już

(2.) Początkowo licznik potrzebnych zmian to 0. Potem (3.) dla każdego kolejnego miasta: (4.) zapamiętujemy, które. Potem (5.) dla każdego miasta w planie dalej położonym od poprzednia wybranego: (6.) zapamiętuje pozycję drugiego wybranego elementu. Jesli (7. - 8.) pozycję wybranych elementów w planie są w odwrotnej kolejności to (9.) zwiększ licznik :ile. Na koniec (13.) zwróć wartość :ile.

Wyznaczanie wszystkich planów

Generowanie wszystkich możliwych planów odbywa się w sposób rekurencyjny. Funkcja Miasta_Generuj przyjmuje kolejno: :miasta - aktualna lista miast do ustalenia ich kolejności, :plany - plany uczestników wycieczki, :plan - aktualnie wybrany plan podróży oraz :wynik - aktualnie najlepsze rozwiązanie. Wynik to lista złożona z dwóch elementów: pierwszy to liczba potrzebnych zmian, a drugi to plan wycieczki. Kiedy :wynik nie jest ustalony to ma wartość [-1].

  1. oto Miasta_Generuj :miasta :plany :plan :wynik
  2.   jeżeli (długość :miasta = 0) [
  3.     niech "wartosc 0
  4.     powtórz (długość :plany) [
  5.       niech "el element npw :plany
  6.       niech "roznic Miasta_Roznica :plan :el
  7.       niech "wartosc :wartosc + :roznic
  8.     ]
  9.     jeśli (LUB (pierw :wynik = -1) (pierw :wynik > :wartosc)) [
  10.       wynik (lista :wartosc :plan)
  11.     ]
  12.   ][
  13.     powtórz (długość :miasta) [
  14.       niech "el (słowo :plan (element npw :miasta))
  15.       niech "miastaB bezElNum npw :miasta
  16.       niech "wynik Miasta_Generuj :miastaB :plany :el :wynik
  17.     ]
  18.   ]
  19.   wynik :wynik
  20. już

Kiedy (2.) plan zostanie ustalony to (3.) przyjmij, że nie potrzeba zmian, a potem (4. - 8.) dla każdego uczestnika wycieczki wylicz różnicę i dodaj do :wartosc. Potem (9. - 11.) jeśli jest to lepszy plan lub plan nie został ustalony to ustal jako aktualny najlepszy wybór. Jednak kiedy plan jest jeszcze ustalany to: (13.) dla każdego :miasta: (14.) wybierz miasto, (15.) utwórz tymczasowy wybór miast bez tego wybranego i (16.) zacznij generować jego pozostałą część.

Główna funkcja

W głównej funkcji pozostaje teraz: (2.) utworzyć listę planów każdego z uczestników, a następnie (3.) zwrócić ostatni element wyniku funkcji Miasta_Generuj. Podczas wywoływania jako :miasta podajemy dowolny plan wycieczki, jako :plany utworzoną listę, jako :plan puste słowo, a za :wynik domyślną wartość [-1].

  1. oto Miasta :A :T :Z
  2.   niech "plan (lista :A :T :Z)
  3.   wynik ost Miasta_Generuj :A :plan " [-1]
  4. już