Logia 2001/02 - Etap III

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.

9.   powtórz 2 [
10.     powtórz ((długość :kod) + 1) [
11.       np :a / 2
12.       lw 90
13.       np :a / 2
14.       ws :a / 2
15.       pw 90
16.       np :a / 2
17.     ]
18.     pod
19.     lw 90
20.     np :a
21.     lw 90
22.     opu
23.   ]

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.

24.   np :a / 2
25.   powtórz (długość :kod) [
26.     jeśli (element npw :kod = "1) [
27.       wielokąt [
28.         ukm "czarny
29.         np (:a / 4)
30.         lw 60
31.         np (:a / 2)
32.         kropka (:a / 2)
33.         lw 60
34.         ws (:a / 2)
35.         pw 120
36.         np (:a / 4)
37.       ]
38.       np :a / 2
39.       lw 90
40.       np :a * 2 / 3
41.       kropka :a / 2
42.       ws :a * 2 / 3
43.       pw 90
44.       ws :a / 2
45.     ]
46.     np :a
47.   ]
48. 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.

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.

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ż

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ż

• Rozwiązania zadań