Logia0 – rok szkolny 1999/2000 – etap - III
Zad. 1. (Kod MKI) MAZOWIECKI URZĄD SZYFRÓW posługuje się (do zapisywania tajnych informacji) alfabetem składającym się tylko z 16 znaków - małych liter od a do p. W celu usprawnienia przetwarzania dokumentów utworzył własny system cyfrowego kodowania znaków, tzw. kod MKI, w którym każdej literze odpowiada czterobitowe słowo (patrz tabela).
Ustalano następujący system szyfrowania znaków, słów oraz zdań:
- Szyfrem znaku x (gdzie x oznacza dowolny znak od a do p) jest taki znak, którego kod MKI jest symetrycznym odbiciem (przestawieniem wspak) kodu znaku x.
- Szyfrem słowa s jest takie słowo, którego każdy znak jest szyfrem odpowiedniego znaku słowa s.
- Szyfrem zdania z (listy słów) jest takie zdanie, którego każde słowo jest szyfrem odpowiedniego słowa zdania z.
Zdefiniuj funkcję SZYFR :zd, której wynikiem dla dowolnego zdanie utworzonego ze słów w alfabecie od a do p jest szyfr tego zdania utworzony zgodnie z ustalonymi wyżej zasadami.
Przykładowe wyniki:
- SZYFR [ala nie ela] - powinno dać wynik [ana lbc cna]
- SZYFR [moja lalka] - powinno dać wynik [dhja nanfa]
Tabela kodów MKI | |
znak | kod znaku |
a | 0000 |
b | 0001 |
c | 0010 |
d | 0011 |
e | 0100 |
f | 0101 |
g | 0110 |
h | 0111 |
i | 1000 |
j | 1001 |
k | 1010 |
l | 1011 |
m | 1100 |
n | 1101 |
o | 1110 |
p | 1111 |
Zad. 2. (Kody flagowe) Dwie przekątne kwadratu dzielą go na cztery ćwiartki. Zamalowując różne kombinacje tych ćwiartek możemy otrzymać 16 różnych wzorów, których możemy używać jako wizualnych kodów flagowych 16 elementowego alfabetu od a do p. Ustalamy następujący system wizualnego kodowania liter alfabetu od a do p w postaci flag.
Kodem flagowym słowa będzie odpowiednia sekwencja kodów flagowych kolejnych znaków. Kodem flagowym zdania będzie sekwencja, umieszczonych kolejno jeden pod drugim i wyrównanych do lewego brzegu kodów słów tworzących zdanie.
Zdefiniuj procedurę FLAGI :zd, która dla dowolnego danego zdania :zd wyświetla na środku ekranu jego kod na tle szarego prostokąta. Zakładamy, że dane zdanie będzie się składać z co najmniej jednego i co najwyżej ośmiu słów, a każde słowo z co najmniej jednej i co najwyżej 12 liter z alfabetu od a do p.
Rysunek przedstawia wynik wywołania FLAGI [ola ma domek].
Zad. 3. (Waga szalkowa) Jeśli mamy po jednym odważniku o masie 1 kg, 3 kg, 9 kg itd. aż do 3n kg, to możemy na wadze szalkowej odważyć każdy ciężar, którego masa w kg jest liczbą całkowitą z zakresu od 0 do 1+3+...+3n i to w dodatku tylko w jeden sposób.
Na przykład, żeby zrównoważyć ciężar 11 kg, trzeba na jednej szali położyć dany ciężar i odważnik 1 kg., a na drugiej szali - odważniki 9 kg i 3 kg.
Zdefiniuj funkcję ZRW :mc, która dla danej masy ciężaru, będącej liczbą całkowitą dodatnią, wyznacza odważniki, które trzeba położyć na szalach wagi, żeby zrównoważyć dany ciężar.
Wynikiem funkcji ma być dwuelementowa lista. Pierwszym jej elementem powinna być lista mas odważników, które należy położyć na jednej szali z odmierzanym ciężarem, a drugim elementem - lista mas odważników, które należy położyć na przeciwnej szali. Obie te listy powinny być uporządkowane malejąco.
Oto przykładowe wyniki:
- ZRW 101 - powinno dać wynik [[9 1][81 27 3]],
- ZRW 282 - powinno dać wynik [[][243 27 9 3]],
- ZRW 3295 - powinno dać wynik [[2187 729 243 81 27][6561 1]],
- ZRW 243 - powinno dać wynik [[][243]].