Strona główna » Poradniki » Logomocja » LOGIA » Logia 2001/02 - Etap III

Logia 2001/02 - Etap III

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

Zadanie 1

Zdefiniuj polecenie RYSDR :dr, którego skutkiem będzie utworzenie na środku ekranu możliwie dużego rysunku danej drogi, na tle jej zakresu z zaznaczonym za pomocą słowa start punktem początkowym.

Pionki na nieskończonej taśmie

Każdy układ skończonej liczby pionków na nieskończonej taśmie pól, jak na rysunku powyżej, można zapisać za pomocą liczby całkowitej nieujemnej nazywanej kodem dziesiętnym układu, utworzonej w następujący sposób:

najpierw dane ustawienie zapisujemy w postaci słowa zerojedynkowego: cyfra 0 oznacza, że odpowiednie pole jest wolne, a cyfra 1, że stoi na nim pionek. Skrajne puste pola na lewo i prawo od układu pionków pomijamy.Zerojedynkowym zapisem układu pionków na rysunkach a, b i c są odpowiednio słowa: 11111, 11111010011101111 oraz 11011011. Następnie każde słowo zerojedynkowe traktujemy jako dwójkowy zapis liczb i tłumaczymy na zapis dziesiętny.

Układy na rysunkach a, b i c mają następujące kody dziesiętne: 31, 128239 oraz 219.

System binarny

Podstawowym problem, któryp pomoże rowiązać wszystkie zadania jest przeliczanie systemu dziesiętnego na binarny i z powrotem. W celu przeliczenia na system binarny warto utworzyć funkcję naBinarna, która będzie podawać zapis binarny dla podanej liczby jako argument :liczba.

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

(2. - 5.) Znajdź największą potęge 2 występującą w liczbie. (6.) Zadeklaruj zmienną :w do której będą dopisywane 0 i 1. (7. - 15.) Dla każdej potęgi w zakresie od 1 do :a włącznie. Podczas każdej iteracji (8.) sprawdź czy dana potęga znajduje się w liczbie. Jeśli tak to (9.) dopisz 1 oraz (10.) usuń znalezioną wartość z liczby. W przeciwnym razie (12.) dopisz na koniec wyniku 0. (14.) Na koniec każdej iteracji zmniejsz :a dwa razy. Na koniec (16.) wypisz wynik tj. zmienną :w.

Procedura RYSDR

Podczas rozwiązywania warto zdać sobie sprawę, że rysunek należy tu dostosować nie do wysokości, a szerokości strony. Pierwszy etap procedury polega na wyliczeniu odpowiednich wartości, a następnie przesunięciu w lewy dolny róg rysunku.

  1. oto RYSDR :dr
  2.   niech "w 780
  3.   niech "kod naBinarna :dr
  4.   niech "a :w / ((długość :kod) + 1)
  5.   pod
  6.   ws :a / 2 pw 90
  7.   ws :a * ((długość :kod) + 1) / 2
  8.   opu

(2.) Ustal maksymalną szerokość. (3.) Pobierz wartość :dr w zapisie binarnym i (4.) oblicz szerokość najkrótszego odcinka. (5. - 8.) Przesuń w lewy, dolny róg rysunku.

  1.   powtórz 2 [
  2.     powtórz ((długość :kod) + 1) [
  3.       np :a / 2
  4.       lw 90
  5.       np :a / 2
  6.       ws :a / 2
  7.       pw 90
  8.       np :a / 2
  9.     ]
  10.     pod
  11.     lw 90
  12.     np :a
  13.     lw 90
  14.     opu
  15.   ]

Drugi etap rysowania polega na rysowaniu obramowania tj. rysunku, ale jeszcze bez pionków choć istnieje możliwość, aby drugi etap połączyć z trzecim. (9. - 23.) Narysuj dwie identyczne części: (10. - 17.) po odpowiednią ilość elementów. Rysowane elementy przypominają odwróconą literę T.

  1.   np :a / 2
  2.   powtórz (długość :kod) [
  3.     jeśli (element npw :kod = "1) [
  4.       wielokąt [
  5.         ukm "czarny
  6.         np (:a / 4)
  7.         lw 60
  8.         np (:a / 2)
  9.         kropka (:a / 2)
  10.         lw 60
  11.         ws (:a / 2)
  12.         pw 120
  13.         np (:a / 4)
  14.       ]
  15.       np :a / 2
  16.       lw 90
  17.       np :a * 2 / 3
  18.       kropka :a / 2
  19.       ws :a * 2 / 3
  20.       pw 90
  21.       ws :a / 2
  22.     ]
  23.     np :a
  24.   ]
  25. już

Ostatni etap polega na dorysowaniu wewnątrz okienek pionków. W tym celu należy (24.) przejść do najbliższego okienka i (25.) sprawdzając wszystkie wartości zapisu binarnego: (26.) jeśli występuje na sprawdzanym miejscu 1 to (27. - 45.) narysować pionek (metoda dowolna). (46.) Po zakończeniu rysowania (lub nie) pionka należy przejsć do następnego okienka.

Zadanie 2

Zdefiniuj funkcję DŁMP :kd (długość maksymalnego łańcucha pionków), która mając dany kod dziesiętny układu pionków daje w wyniku długość maksymalnego łańcucha pionków, tzn. nieprzerwanej sekwencji pionków, w tym układzie.

Oto przykładowe wyniki:

DŁMP 31powinno dać wynik 5,
DŁMP 128239powinno dać wynik 5,
DŁMP 219powinno dać wynik 2.

Funkcja DŁMP w celu ułatwienia szukania najdłuższego podciągu pionków powinna przeliczyć liczbę na system binarny, a następnie policzyć jak długie są fragmenty złożone z samych jedynek. Ze względu na przyjętą strategię funkcja dopisuje na koniec liczby znak # (chociaż może być dowolny, ale inny niż ostatni znak w zapisie binarnym). Jest to wartownik, który pilnuje, aby obliczenia prawidłowo się zakończyły.

  1. oto DŁMP :kd
  2.     niech "kod (słowo naBinarna :kd "#)
  3.     niech "max 0
  4.     niech "i 1
  5.     dopóki [:i <> (długość :kod)][
  6.         niech "znak element :i :kod
  7.         niech "licznik 0
  8.         dopóki [element :i :kod = :znak][
  9.             zwiększ "licznik
  10.             zwiększ "i
  11.         ]
  12.         jeśli (I :znak = "1 :max <= :licznik) [
  13.             niech "max :licznik
  14.         ]
  15.     ]
  16.     wy :max
  17. już

(2.) Pobierz zapis binarny :liczba i (3.) przyjmij, że nie istnieje żaden łańcuch pionków. (4.) Zadeklaruj zmienną :i, która będzie indeksem do przeszukiwania zapisue binarnego. (5.) Dopóki indeks nie wynosi tyle co długość zapisu: (6.) Pobierz aktualnie wskazywany przez indeks znak i (7.) zresetuj licznik. (8.) Dopóki na i-tym miejscu jest pobrany znak to zwiększaj (9.) licznik i (10.) indeks. (12.) Po zakończeniu pętli: sprawdź dwa warunki: czy policzony został znak 1 oraz czy licznik jest większy bądź równy od wcześniej znalezionego maksimum. (15.) Po zakończeniu głównej pętli dopóki zwróć obliczone maksimum :max.

Zadanie 3

Wolno nam dostawić 1 pionek w dowolnym pustym polu na taśmie. Musimy go wstawić tak, aby utworzyć możliwie najdłuższy łańcuch pionków. Zdefiniuj funkcję PLOMBA :kd, która daje w wyniku kod nowego ustawienia, jakie można utworzyć z danego ustawienia przez dodanie 1 pionka, w taki sposób, aby otrzymać maksymalnie długi łańcuch pionków.

W przypadku jeśli takie nowe ustawienie o maksymalnym łańcuchu pionków można otrzymać na wiele sposobów, wynikiem funkcji powinien być kod ustawienia, reprezentowanego przez najmniejszą liczbę.

Oto przykładowe wyniki:

PLOMBA 31powinno dać wynik 63,
PLOMBA 128239powinno dać wynik 128255,
PLOMBA 219powinno dać wynik 223.

Najprostszym rozwiązaniem w celu sprawdzenia gdzie powinna znaleźć plomba należy sprawdzić wszystkie możliwe rozwiązania. W celu ograniczenia rozwiązań należy próbować wstawić plombę w miejsce, gdzie nie występuje pionek. Sprawdzenie czy po wstawieniu plomby został utworzony odcinek dłuższy niż był do tej pory można zrobić porównując wyniki funkcji DŁMP dla oryginalnego kodu i zmodyfikowanego. Przy każdej iteracji należy pamiętać, że jeśli nowy wynik jest równy niż stary to należy zapamiętać nową pozycję.

  1. oto PLOMBA :kd
  2.   niech "kod (słowo naBinarna :kd "#)
  3.   niech "max DŁMP naDziesiętną (bezElNum (długość :kod) :kod)
  4.   niech "maxi 1
  5.   niech "i 1
  6.   dopóki[:i <> długość :kod][
  7.     jeśli (element :i :kod = "0) [
  8.       niech "kod zastąp :i :kod "1
  9.       niech "dł DŁMP naDziesiętną (bezElNum (długość :kod) :kod)
  10.       jeśli (:dł >= :max) [
  11.         niech "max :dł
  12.         niech "maxi :i
  13.       ]
  14.       niech "kod zastąp :i :kod "0
  15.     ]
  16.     zwiększ "i
  17.   ]
  18.   wynik naDziesiętną zastąp :maxi (bezElNum (długość :kod) :kod) "1
  19. już

Zadanie 4

Układ pionków na taśmie można też zakodować w postaci listy liczb całkowitych. Możemy przyjąć, że każdy łańcuch pionków na taśmie będzie reprezentowany przez jego długość, a każda sekwencja pustych pól przez liczbę przeciwną do jej długości. W tym systemie kodem układu 11101001111 będzie lista [3 -1 1 -2 4].

Zdefiniuj funkcję KL :kd która dla danego kodu dziesiętnego układu daje w wyniku jego kod listowy.

Oto przykładowe wyniki:

KL 31powinno dać wynik [5],
KL 128239powinno dać wynik [5 -1 1 -2 3 -1 4],
KL 219powinno dać wynik [2 -1 2 -1 2].

W celu wykonania tego zadania wystarczy pobrać zapis binarny przekazanej liczby dziesiętnej, a następnie po podliczeniu kolejnego odcinka takich samych znaków dopisać wartość na listę wynikową. W celu uniknięcia sprawdzania czy znak to 1 wystarczy dodatkowa zmienna :mn o wartości 1, która przy każdej zmianie znaku będzie mnożona przez -1. Wtedy licznik pomnożony przez :mn będzie dawał na zmianę wartość dodatnią i ujemną.

  1. oto KL :kd
  2.   niech "kod (słowo naBinarna :kd "#)
  3.   niech "lista []
  4.   niech "i 1
  5.   niech "mn 1
  6.   dopóki [:i <> (długość :kod)][
  7.     niech "znak element :i :kod
  8.     niech "licznik 0
  9.     dopóki [element :i :kod = :znak][
  10.       zwiększ "licznik
  11.       zwiększ "i
  12.     ]
  13.     niech "lista nak (:licznik * :mn) :lista
  14.     niech "mn (:mn * -1)
  15.   ]
  16.   wynik :lista
  17. już