Logia 2016/17 Etap II

Zadanie 1

Szyfr Bacona polega na zastępowaniu liter alfabetu łacińskiego pięcioznakowymi ciągami złożonymi z liter a i b zgodnie z poniższą tabelą:

A	B	C	D	E	F	G	H	I, J	K	L	M
aaaaa	aaaab	aaaba	aaabb	aabaa	aabab	aabba	aabbb	abaaa	abaab	ababa	ababb

N	O	P	Q	R	S	T	U, V	W	X	Y	Z
abbaa	abbab	abbba	abbbb	baaaa	baaab	baaba	baabb	babaa	babab	babba	babbb

Adaś postanowił szyfrować kolejne litery słowa. Zamiast liter a i b użył odpowiednio zamalowanych kwadratów:

Napisz jednoparametrową procedurę/funkcję szyfruj, po wywołaniu której na środku ekranu powstanie rysunek zaszyfrowanego słowa (od lewej do prawej). Parametrem jest niepuste słowo złożone z wielkich liter alfabetu łacińskiego o maksymalnej długości 70. Szerokość rysunku wynosi 700 lub wysokość wynosi 400. Do zamalowania użyj dwóch dowolnych kolorów różnych od koloru krawędzi kwadratów.

szyfruj ″ GODZINAKODOWANIA

Strategia

Przyjmijmy, że litera a oznacza cyfrę 0, a litera b cyfrę 1. Wtedy każdej literze przyporządkowywujemy jej pozycję w alfabecie pomniejszona o jeden zapisaną binarnie. Przykładowo litera C ma 00010 co w zapisie binarnym to liczba dziesiętna 2, a litera C to trzecia litera alfabetu. W myśl tej zasady litera A ma indeks 0. Oczywiście należy pamiętać, że dla liter położonych dalej niż I zmniejszać indeks o 1, a od litery V pomniejszyć o jeszcze jeden.

Rozwiązanie

Litera na kod

Każda rysowana litera zostaje zamieniona wpierw na kod zero jedynkowy, a dopiero na podstawie kodu wartości są rysowane. W celu zamiany

1. oto szyfruj_kod :znak
2.   niech "wartosc (ascii :znak) - (ascii "A)
3.   jeśli ((ascii :znak) > (ascii "I)) [ zmniejsz "wartosc ]
4.   jeśli ((ascii :znak) > (ascii "U)) [ zmniejsz "wartosc ]
5.   niech "s "
6.   niech "p 16
7.   dopóki [:p >= 1][
8.     niech "r int(:wartosc/:p)
9.     niech "s (słowo :s :r)
10.     niech "wartosc :wartosc - :r*:p
11.     niech "p :p / 2
12.   ]
13.   wynik :s
14. już

(2.) Sprawdź pozycję litery w alfabecie i (3. - 4.) skoryguj jej wartość jeśli istnieje taka potrzeba. Następnie (5. - 12.) przelicz liczbę dziesiętną na postać binarną i (13.) zwróć zapis jako tekst. Warto tutaj zauważyć, że niezależnie od wartości zawsze zwracane jest pięć cyfr.

Funkcja główna

Funkcja główna szyfruj początkowo ustala rozmiar pojedynczego kwadracika, a następnie dla każdej litery generuje kod i na jego podstawie rysuje obrazek.

1. oto szyfruj :słowo
2.   niech "n (długość :słowo)
3.   niech "a 80
4.   niech "w 700/:n
5.   jeśli (:w < :a) [ niech "a :w ]
6.   pod
7.   ws :a*5/2 pw 90
8.   ws :a*:n/2 lw 90
9.   opu
10.   powtórz (:n) [
11.     niech "el szyfruj_kod element npw :słowo
12.     powtórz (5) [
13.       jeżeli (element npw :el = "1) [
14.         ukm "niebieski
15.       ][
16.         ukm "żółty
17.       ]
18.       wielokąt [ powtórz 4 [ np :a pw 90 ] ]
19.       np :a
20.     ]
21.     pod
22.     ws :a*5 pw 90
23.     np :a lw 90
24.     opu
25.   ]
26. już

(2.) Sprawdź ile jest liter i (3. - 5.) określ rozmiar najmniejszego kwadratu tj. bok :a. (6. - 9.) Przejdź do lewego, dolnego rogu. Następnie (10.) dla każdej litery: (11.) określ jej kod, (12. - 21.) narysuj kolumnę i (22. - 25.) przejdź do następnej.

Strategia

W celu powiązania ze sobą domów najlepiej, aby lista numerów domu była uporządkowana (rosnąco lub malejąco). Wtedy kolejne domy powinny zostać dokładne na listę tak długo, aż numer poprzedniego domu nie różni się o więcej niż 3. Jeśli się różni to licznik należy zapamiętać i rozpocząć nowe liczenie od aktualnego domu. Na koniec należy wybrać licznik, który ma największą wartość. Uwaga: należy pamiętać, aby sprawdzić czy do pierwszego osiedla pasują domy z końca listy (planasza ma kształt owalu).

Rozwiązanie

W funkcji maksos osiedle o (2.) największej ilości domów jest umieszczone w zmiennej :max, a (3.) w zmiennej :ile aktualna wartość domów w osiedlu.

1. oto maksos :lista
2.   niech "max 0
3.   niech "ile 0
4.   jeśli ((pierw :lista) <= 3) [
5.     zwiększ "ile
6.     niech "lista bo :lista
7.   ]
8.   niech "lista nak 0 :lista
9.   niech "ost pierw :lista
10.   powtórz (długość :lista) [
11.     niech "el element npw :lista
12.     niech "w :el - :ost
13.     jeżeli (I (:w >= 0) (:w <= 3)) [
14.       zwiększ "ile
15.     ][
16.       jeśli (:ile > :max) [
17.         niech "max :ile
18.       ]
19.       niech "ile 1
20.     ]
21.     niech "ost :el
22.   ]
23.   wynik :max
24. już

Strategia

Zadanie zostanie podzielone na kilka etapów. Pierwszy będzie polegał na podzieleniu słowa na listę znaków w następujący sposób: przygotuj pustą listę. W liście umieść nową pustą listę. Następnie dla każdej listy w głównej liście dopisz kolejny znak ze słowa. Czynność tę powtarzaj dopóki pozostaną niewybrane znaki z słowa. W ten sposób w i-tej liście znajdą się znaki z i-tej kolumny. Następnie wystarczy sprawdzić ile jest list, które mają wszystkie znaki identyczne.

Rozwiązanie

Identyczne elementy?

Do sprawdzenia czy na liście wszystkie elementy są identyczne służy funkcja kolit_sprawdz. Zwraca ona wartość logiczną.

1. oto kolit_sprawdz :lista
2.   jeśli (puste? :lista)[ wynik "fałsz ]
3.   niech "el pierw :lista
4.   powtórz (długość :lista) [
5.     jeśli (:el <> element npw :lista) [
6.       wynik "fałsz
7.     ]
8.   ]
9.   wynik "prawda
10. już

(2.) Dla pustej liście nie ma żadnego elementu, więc nie mogą być identyczne. Należy wtedy zwrócić fałsz. W przeciwnym wypadku (3.) pobierz pierwszy znak i (4. = 8.) porównaj go z każdym pozostałym elementem. Jeśli choć raz elementy będą się różnić to zwróć fałsz w przeciwnym wypadku (9.) zwróć prawdę.

Funkcja główna

Przed przystąpieniem do obliczeń należy: (2.) przygotować pustę listę i (3.) określić, który znak zostaje wybrany (tj. od pierwszego). Następnie (4. - 14.) podziel słowo na listę elementów w każdej z kolumn i (15. - 20.) policz ile jest list na których elementy są identyczne. Na koniec (21.) zwróć wartość zmiennej :licznik.

1. oto kolit :słowo
2.   niech "lista []
3.   niech "i 1
4.   dopóki [:i <= (długość :słowo)][
5.     niech "lista nak [] :lista
6.     powtórz (długość :lista) [
7.       jeśli (:i <= (długość :słowo)) [
8.         niech "el element npw :lista
9.         niech "znak element :i :słowo
10.         niech "lista zastąp npw :lista (zd :el :znak)
11.         zwiększ "i
12.       ]
13.     ]
14.   ]
15.   niech "licznik 0
16.   powtórz (długość :lista) [
17.     jeśli (kolit_sprawdz element npw :lista) [
18.       zwiększ "licznik
19.     ]
20.   ]
21.   wynik :licznik
22. już

(2.) Dla pustej liście nie ma żadnego elementu, więc nie mogą być identyczne. Należy wtedy zwrócić fałsz. W przeciwnym wypadku (3.) pobierz pierwszy znak i (4. = 8.) porównaj go z każdym pozostałym elementem. Jeśli choć raz elementy będą się różnić to zwróć fałsz w przeciwnym wypadku (9.) zwróć prawdę.

• Rozwiązania zadań