Logia 2014/15 Etap II
Zadanie 1 (Szyfr obrazkowy)
Julka i Kuba używają szyfrów obrazkowych. Najpierw ustalają alfabet zawierający litery, które będą występować w szyfrowanym słowie. Następnie kodują słowo za pomocą prostokątów o różnych wymiarach. Wysokość prostokąta odpowiadającego kolejnej literze słowa zależy od jej pozycji w alfabecie i wynosi, odpowiednio, 10 dla pierwszej litery alfabetu, 20 dla drugiej, 30 dla trzeciej itd. Szerokość prostokąta zależy od pozycji litery w szyfrowanym słowie i jest równa 10 dla pierwszej litery słowa, 20 dla drugiej, 30 dla trzeciej, itd. Dla każdego słowa określona jest linia bazowa, na której leży górny bok prostokątów ilustrujących samogłoski oraz dolny bok prostokątów odpowiadających spółgłoskom.
Napisz dwuparametrową procedurę/funkcję szyfr, po wywołaniu której na środku ekranu powstanie rysunek zaszyfrowanego słowa. Pierwszy parametr jest alfabetem i składa się z co najwyżej 25 liter. Drugi parametr jest szyfrowanym słowem, co najwyżej dwunastoliterowym.
Strategia
W rozwiązaniu została wykorzystana funkcja samogłoska?, która dla podanej jako parametr literze zwraca wartość logiczną w zależności czy dana litera jest samogłoską.
- oto samogłoska? :z
- wynik ((numel :z [a o e u i y]) <> 0)
- już
Rozwiązanie
(3. - 6.) Na początku trzeba sprawdzić jaka będzie długość całego rysunku, aby go (7. - 8.) wyśrodkować. Druga część środkowej lini zostanie narysowana na koniec rysowania.
- oto szyfr :alfabet :s
- niech "a 10
- niech "w 0
- powtórz (długość :s) [
- niech "w :w + npw
- ]
- pw 90 ws :w*:a/2
- lw 90
- powtórz (długość :s) [
- niech "el element npw :s
- niech "szer :a*npw
- niech "wys :a*(numel :el :alfabet)
- jeżeli (samogłoska? :el) [
- ws :wys pw 90
- np :szer lw 90
- np :wys
- ][
- np :wys lw 90
- ws :szer pw 90
- ws :wys
- ]
- ]
- lw 90
- np :w*:a/2 pw 90
- już
Następnie (9.) w pętli rysowane są kolejne litery: (10.) pobieramy literę i obliczamy jej (11.) szerokość oraz (12.) wysokość. Teraz (13.) należy sprawdzić czy jest to samogłoska. Jeśli jest to (14. - 16.) rysujemy w dół, a w przeciwnym razie (18. - 20.) do góry. Na koniec (23. - 24.) wracamy żółwiem na środek ekranu.
Zadanie 2 (Redukcja)
Janek lubi zabawy z liczbami i postanowił je przekształcać. Analizuje liczbę od cyfry jedności do najbardziej znaczącej cyfry. Jeżeli dwie sąsiednie cyfry są takie same, to zastępuje je ostatnią cyfrą ich sumy. Po zamianie przegląda kolejne (jeszcze nieprzejrzane) cyfry. Po przejrzeniu całej liczby powtarza analizę, aż nie dokona żadnej zamiany.
Pomóż Jankowi i napisz jednoparametrową funkcję redukcja, której parametrem jest liczba całkowita dodatnia nie większa niż 10100. Wynikiem funkcji jest liczba po przekształceniach wykonanych przez Janka.
| redukcja 84211 | jest 6 (w kolejnych krokach Janek otrzymuje 8422, 844, 88, 6) |
|---|---|
| redukcja 426633 | jest 86 (w kolejnych krokach Janek otrzymuje 4226, 446, 86) |
Strategia
Zadanie zostanie rozwiązane przy pomocy rekurencji. Podczas każdej rekurencji będzie sprawdzana każda para znaków i jeśli okaże się, że chociaż jedna para została zamieniona to funkcja połączy cyfry, a następnie wywoła siebie, aby sprawdzić czy nowe wyrażenie nie wymaga dalszej redukcji.
Rozwiązanie
Na początku deklarowane są dwie zmienne: (2.) :zmian - licznik ile zmian zostało wprowadzonych, jeśli jego wartość jest równa 0 to oznacza, że nie zostały wykonane jakiekolwiek zmiany. Drugą zmienną jest (3.) :s - do niej zostaną przepisane już przejrzane fragmenty liczby.
- oto redukcja :a
- niech "zmian 0
- niech "s "
- dopóki [(długość :a) > 1][
- jeżeli (pierw :a = pierw bp :a) [
- niech "s (słowo :s (reszta (pierw :a)*2 10))
- niech "a bp bp :a
- zwiększ "zmian
- ][
- niech "s (słowo :s (pierw :a))
- niech "a bp :a
- ]
- ]
- niech "s (słowo :s :a)
- jeżeli (:zmian > 0) [
- wynik redukcja :s
- ][
- wynik :s
- ]
- już
(4.) Dopóki jest jakakolwiek para w :a to (5.) sprawdzamy czy najmniej znacząca para cyfr jest identyczna: jeśli tak to (6. - 8.) dopisujemy do :s nową cyfrę, a z (7.) :a usuwamy parę liczb i (8.) zwiększamy ilość wykonanych zamian. Jednak jeśli para nie jest identyczna to (10. - 11.) wystarczy przenieść najmniej znaczącą cyfrę z :a do :s. Po wykonaniu pętli (15.) jeśli zaszły zmiany to (16.) należy sprawdzić czy nie są potrzebne kolejne, a jeśli nie to (18.) zwracany jest wynik.
Zadanie 3 (Ile liczb)
Napisz dwuparametrową funkcję ile, której wynikiem jest liczba dodatnich liczb całkowitych, o liczbie cyfr równej pierwszemu parametrowi funkcji i mających tę cechę, że w swoim zapisie zawierają co najmniej jedną cyfrę określoną drugim parametrem funkcji. Pierwszy parametr może przyjmować wartości od 1 do 9, a drugi – od 0 do 9. Postaraj się, aby na wynik nie trzeba było czekać zbyt długo.
| ile 1 4 | jest 1 (bo liczba 4 jest jedyną dodatnią liczbą jednocyfrową zawierającą cyfrę 4) |
|---|---|
| ile 2 5 | jest 18 (bo jedynymi liczbami dwucyfrowymi zawierającymi piątkę są: 15, 25, 35, 45, 50-59, 65, 75, 85, 95) |
| ile 3 6 | jest 252. |
Rozwiązanie
Poniższa funkcja :ile nie sprawdza wszystkich liczb :dl cyfrowych. Jej zadanie polega na tym, aby obliczyć liczbę liczb zawierających cyfrę :c wiedząc, że może być na każdej z pozycji. Na początku (2.) :suma wynosi 0. Następnie (4. - 5.) numer powtórzenia określa położenie :c w liczbie, ale nie jest to jawnie pokazane. Następna pętla (6. - 12.) ustala ile jest możliwych cyfr do ustalenia na każdej z pozycji, a (13.) wyliczona ilość zostaje dodana do :suma. Na koniec (15.) należy zwrócić :suma.
- oto ile :dl :c
- niech "suma 0
- powtórz (:dl) [
- niech "poz npw
- niech "iloczyn 1
- powtórz (:dl) [
- niech "w 10
- jeśli (npw = 1) [ zmniejsz "w ]
- jeśli (npw < :poz) [ zmniejsz "w ]
- jeśli (npw = :poz) [ niech "w 1 ]
- niech "iloczyn :iloczyn*:w
- ]
- niech "suma :suma + :iloczyn
- ]
- wynik :suma
- już