Strona główna » Poradniki » Logomocja » LOGIA » Logia 2008/09 - Etap II
 

Logia 2008/09 - Etap II

https://mattomatti.com/li082
· Etap I · Etap II · Etap III ·
iOryginalna treść zadań jest dostępna pod oficjalnym adresem konkursu LOGIA

Zadanie 1 (czekoladka)

Harcerski szyfr Czekoladka polega na rysowaniu kolejnych zaszyfrowanych liter danego wyrazu. Aby zaszyfrować literę, rysujemy fragment ramki, w którym ta litera jest zapisana, zgodnie z rysunkami obok. Ponieważ w jednej ramce najczęściej znajdują się dwie litery, kropka pokazuje, czy mamy na myśli literę z lewej, czy z prawej strony. Dla liter T, U, W, Y i Z rysowanie kropki jest zbędne (choć nie jest błędem).

Tabelka szyfrowania

Zdefiniuj procedurę CZEKOLADKA :wyraz, której daną może być słowo utworzone z wielkich liter (wybranych spośród tych, które znajdują się na rysunkach powyżej), o długości od 2 do 30 znaków. Procedura tworzy na środku ekranu rysunek przedstawiający zaszyfrowany wyraz zgodnie z regułami szyfru Czekoladka.

Procedura przedstawia wyraz w postaci graficznej, zgodnie z następującymi zasadami:

  • szerokość rysunku przedstawiającego zaszyfrowany wyraz wynosi 700,
  • rysunki odpowiadające kolejnym szyfrowanym literom są tej samej wysokości,
  • szerokość odstępu pomiędzy zaszyfrowanymi literami wynosi 1/4 wysokości rysunku,
  • szerokość zaszyfrowanych liter od A do S jest dwa razy większa od ich wysokości,
  • średnica kropki rysowanej w ramkach wynosi 1/3 wysokości litery.

Rysunki poniżej przedstawiają efekt wywołania procedury Czekoladka:

LOGO
SZYBA
TRATWA

Wyliczanie wysokości

Zastanówmy się na początku nad problemem związanym z wyliczeniem wysokości rysunku. Otóż niektóre fragmenty wymagają dwa razy więcej szerokości niż inne. Z tego powodu należy wpierw sprawdzić ile jest takich przypadków. Chociaż nie jest to ujęte w zadaniu warto zauważyć, że litery U i Y wymagają na szerokość połowę wysokości. Z kolei litery T i W wymagają na szerokość tyle samo co np. litera A.

  1. oto CZEKOLADKA :wyraz
  2.   niech "dl długość :wyraz
  3.   powtórz (długość :wyraz) [
  4.     niech "el element npw :wyraz
  5.     jeśli (LUB (ascii(:el) <= ascii "s) (:el = "T) (:el = "W))[
  6.       niech "dl :dl + 1
  7.     ]
  8.     jeśli (LUB (:el = "U) (:el = "Y))[
  9.       niech "dl :dl - 1.5
  10.     ]
  11.   ]
  12.   niech "SZER 700
  13.   niech "h :SZER/(:dl + ((długość :wyraz) - 1)/4)
  14.   niech "h2 :h*pwk(2)
  15.   niech "h4 :h/pwk(2)

Na początku (2.) ilość szerokości to długość wyrazu. Dopiero potem (3. - 11.) wartość ta jest odpowiednio modyfikowana, aby niektóre litery miały podwójną szerokość, a inne tylko połowę. Następnie (13.) w celu wyliczenia wysokości należy szerokość obrazka podzielić przez wyliczoną ilość szerokości i zsumować z ilością odstępów. Łączną szerokość odstępów można policzyć pomniejszając o jeden liczbę liter, a następnie dzieląc na 4, ponieważ mają mieć szerokości tyle co ćwierć wysokości.

(16. - 19.) Następna część kodu polega na przesunięciu żółwia w miejsce rysowania, a następnie w pęli narysowaniu wszystkich kolejnych liter. W celu uproszczenia zapisu kodu wykorzystana została tutaj składnia wybierz i zadeklarowana została dodatkowa procedura CZEKOLADKA_prost, która zapewnia wygodny sposób rysowania prostokątów. (78. - 81.) Po narysowaniu litery należy zawsze przesunąć żółwia o odstęp w prawo.

  1.   pod
  2.   ws :h/2 pw 90
  3.   ws :SZER/2 lw 90
  4.   opu
  5.   powtórz (długość :wyraz)[
  6.     wybierz (element npw :wyraz)[
  7.       A [CZEKOLADKA_prost :h "0011 0]
  8.       B [CZEKOLADKA_prost :h "0011 1]
  9.       C [CZEKOLADKA_prost :h "1011 0]
  10.       D [CZEKOLADKA_prost :h "1011 1]
  11.       E [CZEKOLADKA_prost :h "1001 0]
  12.       F [CZEKOLADKA_prost :h "1001 1]
  13.       G [CZEKOLADKA_prost :h "0111 0]
  14.       H [CZEKOLADKA_prost :h "0111 1]
  15.       I [CZEKOLADKA_prost :h "1111 0]
  16.       J [CZEKOLADKA_prost :h "1111 1]
  17.       K [CZEKOLADKA_prost :h "1101 0]
  18.       L [CZEKOLADKA_prost :h "1101 1]
  19.       M [CZEKOLADKA_prost :h "0110 0]
  20.       N [CZEKOLADKA_prost :h "0110 1]
  21.       O [CZEKOLADKA_prost :h "1110 0]
  22.       P [CZEKOLADKA_prost :h "1110 1]
  23.       R [CZEKOLADKA_prost :h "1100 0]
  24.       S [CZEKOLADKA_prost :h "1100 1]
  25.       T [ pod
  26.               np :h pw 135
  27.               opu
  28.               np :h2 lw 90
  29.               np :h2 lw 45
  30.               pod
  31.               ws :h
  32.           ]
  33.       U [ pod
  34.               pw 90 np :h/2
  35.               lw 135
  36.               opu
  37.               np :h4 pw 90
  38.               np :h4 lw 45
  39.               pod
  40.               ws :h
  41.           ]
  42.       W [ opu
  43.               pw 45
  44.               np :h2 pw 90
  45.               np :h2 lw 135
  46.           ]
  47.       Y [ opu
  48.               pw 45 np :h4
  49.               lw 90 np :h4
  50.               pod
  51.               pw 45 ws :h
  52.               pw 90 np :h/2
  53.               lw 90
  54.           ]
  55.       Z [ pod
  56.               pw 90 np :h/2
  57.               lw 90 np :h/2
  58.               okrąg :h
  59.               ws :h/2 pw 90
  60.               np :h/2 lw 90
  61.           ]
  62.     ]
  63.     pod
  64.     pw 90 np :h/4
  65.     lw 90
  66.     opu
  67.   ]
  68. już

Prostokąty

W celu narysowania prostokątów procedura korzysta z procedury CZEKOLADKA_prost, która przyjmuje trzy argumenty: :h - aktualna wysokość elementów, :l - lista cyfr, które boki mają być widoczne (począwszy od lewego zgodnie ze wskazówkami zegara, 0 oznacza nie wyświetlaj, a 1 rysuj) oraz :k - określa po której stronie narysować kropkę (0 po lewej, 1 po prawej). Kod procedury wygląda następująco:

  1. oto CZEKOLADKA_prost :h :l :k
  2.   CZEKOLADKA_TEST (element 1 :l)
  3.   np :h pw 90
  4.   CZEKOLADKA_TEST (element 2 :l)
  5.   np :h*2 pw 90
  6.   CZEKOLADKA_TEST (element 3 :l)
  7.   np :h pw 90
  8.   CZEKOLADKA_TEST (element 4 :l)
  9.   np :h*2 pw 180
  10.   np :h*(:k + 0.5)
  11.   pod
  12.   lw 90 np :h/2
  13.   kropka :h/3
  14.   ws :h/2 pw 90
  15.   np :h*(1.5 - :k)
  16.   lw 90
  17.   opu
  18. już

Wykorzystana funkcja CZEKOLADKA_TEST ma za zadanie uprościć proces podnoszenia i opuszczania pisaka. Dla przekazanej wartości 0 podnosi pisak, a dla 1 go opuszcza.

  1. oto CZEKOLADKA_TEST :p
  2.   jeżeli(:p = 1)[
  3.     opu
  4.   ][
  5.     pod
  6.   ]
  7. już

Zadanie 2 (liczby pomiędzy pierwszymi)

Asia bada liczby pierwsze. Dowiedziała się, że jest ich bardzo dużo, ale na przykład zero i jedynka nie są liczbami pierwszymi. Pewnego dnia w encyklopedii znalazła następującą definicję: "Liczbami pomiędzy pierwszymi nazywamy liczby będące średnią arytmetyczną kolejnych dwóch liczb pierwszych większych od 2 (ang. interprime numbers). Pięć najmniejszych liczb pomiędzy pierwszymi to: 4, 6, 9, 12, 15.".

Pomóż Asi wyszukać liczby pomiędzy pierwszymi. Napisz funkcję LLPP :pocz :kon, która zliczy wszystkie liczby pomiędzy pierwszymi większe od :pocz i jednocześnie mniejsze od :kon. Parametr :pocz jest liczbą większą od zera, a parametr :kon jest liczbą mniejszą lub równą 10000.

LLPP 5 7jest 1 (bo 6 jest liczbą pomiędzy pierwszymi)
LLPP 7 16jest 3 (bo 9, 12 i 15 są liczbami pomiędzy pierwszymi)

Czy liczba pierwsza?

Poniżej został przedstawiony kod funkcji, która dla podanej liczby :a zwraca czy jest to liczba pierwsza. O działaniu tego algorytmu można poczytać w artykule o liczbach pierwszych.

  1. oto czyPierwsza? :a
  2.   jeśli (:a < 2) [wynik "fałsz]
  3.   niech "b 2
  4.   dopóki [:b <= pwk(:a)][
  5.     jeśli ((reszta :a :b) = 0) [
  6.       wynik "fałsz
  7.     ]
  8.     zwiększ "b
  9.   ]
  10.   wynik "prawda
  11. już

Ile liczb?

Wyszukiwanie kolejnych liczb pomiędzy pierwszymi będzie polegało na znalezieniu każdej kolejnej pary liczb pierwszych. Dodać do wyniku o ile znajduje się w zakresie. Warunkiem stopu będzie uzyskanie liczby, która jest większa od górnego zakresu przeszukiwania.

  1. oto LLPP :pocz :kon
  2.   niech "a 2
  3.   niech "b 3
  4.   niech "ile 0
  5.   dopóki["prawda][
  6.     niech "a :b
  7.     zwiększ "b
  8.     dopóki[nie czyPierwsza? :b][
  9.       zwiększ "b
  10.     ]
  11.     niech "k (:b + :a)/2
  12.     jeśli(:k > :kon)[
  13.       wynik :ile
  14.     ]
  15.     jeśli(:k >= :pocz)[
  16.       zwiększ "ile
  17.     ]
  18.   ]
  19. już

Do przechowywanie aktualnej pary liczb pierwszych będą służyć zmienne :a i :b. Ich początkowe wartości (2. - 3.) to 2 i 3. (4.) Wystąpienia kolejnych liczb pomiędzy pierwszymi będą zliczane w zmiennej :ile. (5.) W nieskończonej pętli każda kolejna iteracja zaczyna się od (6. - 10.) wyszukania nowej pary liczb pierwszych. Następnie (11.) wyliczeniu aktualnej wartości liczby specjalnej i (12. - 14.) jeśli wykracza poza zakres to należy zwrócić aktualny wynik. (15. - 17.) W przeciwnym wypadku jeśli liczba jest w zakresie to należy zwiększyć zmienną :ile.

Zadanie 3 (duże liczby)

Staś interesuje się dużymi liczbami. Zastanawiał się, czy jest możliwe, aby po pomnożeniu cyfr dużej liczby otrzymać liczbę pierwszą.

Pomóż Stasiowi rozwiązać ten problem. Napisz funkcję ICP :x, której daną :x jest niepuste słowo złożone wyłącznie z cyfr (maksymalnie 100 cyfr), a wynikiem wartość logiczna prawda, gdy iloczyn cyfr danej :x jest liczbą pierwszą, a fałsz, gdy iloczyn cyfr danej :x nie jest liczbą pierwszą.

ICP "121jest "prawda
ICP "999jest "fałsz

Rozwiązanie

Wyliczenie iloczynu wszystkich cyfr podanej liczby polega na wybieraniu ostatniej cyfry mnożeniu aktualnego iloczynu przez nią, a następnie usunięciu ostatniej cyfry. Ostateczny wynik można podać zwracając wynik funkcji czyPierwsza?, która została opisana w zadaniu 2. Kod przedstawia się następująco:

  1. oto ICP :x
  2.   niech "iloczyn 1
  3.   dopóki[:x > 0][
  4.     niech "suma :iloczyn * (reszta :x 10)
  5.     niech "x int(:x / 10)
  6.   ]
  7.   wynik czyPierwsza? :iloczyn
  8. już

Drugie rozwiązanie

Jak wiadomo liczba pierwsza to taka liczba, która w rozkładzie na czynniki pierwsze ma tylko dwa dzielniki: pierwszy to 1 oraz drugi to samą siebie. Przypuśćmy, że liczba a to iloczyn cyfr przekazanych do funkcji. Oznacza to, że każda cyfra to liczba z rozkładu a na czynniki pierwsze.