Strona główna » Poradniki » Logomocja » LOGIA » Logia 2007/08 - Etap II
 

Logia 2007/08 - Etap II

· Etap I · Etap II · Etap III ·
iOryginalna treść zadań jest dostępna pod oficjalnym adresem konkursu LOGIA

Zadanie 1

Alek i Olek postanowili rozegrać mecz rzucając kostkami do gry. Umówili się, że w każdej partii meczu każdy z nich rzuca kilkoma kostkami. Daną partię wygrywa ten z nich, który uzyska większą sumę oczek. Jeśli uzyskają taką samą sumę, to partia kończy się remisem. Cały mecz wygrywa ten z chłopców, który wygra więcej partii. Jeśli Alek i Olek wygrają taką samą liczbę partii, to mecz kończy się remisem. Ela, młodsza siostra Alka, notowała na kartce wszystkie wyniki rzutów wykonywanych przez chłopców. Pomóż Eli wskazać zwycięzcę meczu.

Napisz funkcję MECZ :wyniki :n, której wynikiem będzie imię chłopca, który wygrał mecz lub słowo "Remis. Dana :wyniki określa liczby oczek na kostkach podczas kolejnych partii, w obrębie jednej partii najpierw są wyniki Alka, potem Olka. Dana :n określa iloma kostkami chłopcy rzucali. Zakładamy, że chłopcy rzucali nie więcej niż 6 kostkami i rozegrali nie więcej niż 10 partii.

MECZ "1231 1jest "Remis - chłopcy rozegrali dwie partie rzucając jedną kostką, pierwszą partię wygrał Olek (2 oczka wobec 1 oczka Alka), drugą Alek.
MECZ "213345325166 2jest "Olek - chłopcy rozegrali 3 partie rzucając dwiema kostkami, Olek wygrał dwie partie (pierwszą 6 do 3 i trzecią 12 do 6), drugą przegrał (5 do 9).

Sumowanie cyfr

Cyfry przekazywane do sumowania są w postaci znaków, a nie cyfr jako liczba. Z tego powodu należy je odpowiednio rozpoznać i dopiero można zsumować ich wartości. Przedstawiona funkcja sumujLiczby przyjmuje trzy argumenty: :słowo - cyfry w postaci tekstu, :od - indeks od którego ma się rozpocząć sumowanie oraz :n - ile cyfr ma zostać zsumowanych.

  1. oto sumujLiczby :słowo :od :n
  2.   niech "suma 0
  3.   powtórz (:n) [
  4.     niech "el (ascii element npw+:od-1 :słowo)
  5.     niech "suma :suma + (:el - 48)
  6.   ]
  7.   wynik :suma
  8. już

Funkcja rozpoczyna działanie (2.) od zainicjalizowania zmiennej do zapisywania sumy. Następnie (3.) w pętli sumowane jest :n liczb. W każdej iteracji (4.) wybierany jest kolejny znak z uwzględnieniem wskazanego przesunięcia :od, a następnie (5.) do sumy jest dodawana wartość znaku w systemie ascii pomniejszona o 48 (tj. pozycję cyfry 0 w tablicy ascii). Na koniec (7.) zwracana jest wartość zmiennej :suma.

Procedura główna

Na podstawie przekazanych danych (zapisków oraz ile kostek zostało użytych) można wyznaczyć ile zostało rozegranych partii. Na początek (2.) funkcja określa ile cyfr zostało użytych do zapisu partii (po :n na każdego gracza) i na tej podstawie (3.) została wyliczona ilość partii. Potem zainicjalizowane zostały (4. - 5.) zmienne do przechowywania ile meczy wygrał każdy z chłopców. Remisy nie są sumowane, ponieważ nie wpływają one na wynik, który chłopiec wygrał.

  1. oto MECZ :wyniki :n
  2.   niech "cyfr 2 * :n
  3.   niech "meczy (długość :wyniki) / :cyfr
  4.   niech "wAlek 0
  5.   niech "wOlek 0
  6.   powtórz (:meczy) [
  7.     niech "i npw - 1
  8.     niech "pAlek sumujLiczby :wyniki :cyfr*:i+1 :n
  9.     niech "pOlek sumujLiczby :wyniki :cyfr*:i+:n+1 :n
  10.     jeśli (:pAlek > :pOlek) [ zwiększ "wAlek ]
  11.     jeśli (:pAlek < :pOlek) [ zwiększ "wOlek ]
  12.   ]
  13.   jeśli (:wAlek > :wOlek) [ wynik "Alek ]
  14.   jeśli (:wAlek < :wOlek) [ wynik "Olek ]
  15.   jeśli (:wAlek = :wOlek) [ wynik "Remis ]
  16. już

Następnie (6.) dla każdej partii: (7.) pomniejsz numer powtórzenia o 1 i zapisz do zmiennej :i. Dalej (8. - 9.) zsumuj cyfry z odpowiednich zakresów i (10. - 11.) rozpoznaj, który chłopiec wygrał. Po zakończeniu pętli sprawdź wyniki wykonując (13. - 15.) serię porównań.

Zadanie 2

Jasia fascynują liczby pierwsze i doskonałe. Liczba doskonała to taka liczba naturalna, która jest równa sumie swoich podzielników właściwych, czyli podzielników mniejszych od tej liczby. Na przykład 28 jest liczbą doskonałą, bo 28=1+2+4+7+14. Liczb doskonałych jest niewiele, do 10000 tylko cztery (6, 28, 496 i 8128). Jaś postanowił "złagodzić" definicję liczby doskonałej i wymyślił liczby "prawie doskonałe", tj. takie, które są wielokrotnością sumy swoich podzielników właściwych. Jaś zastanawiał się, ile jest takich liczb. Pomóż Jasiowi policzyć, ile takich liczb jest w zadanym przedziale.

Napisz funkcję ILEPD :m :n, której wynikiem jest liczba liczb "prawie doskonałych" nie mniejszych niż :m i nie większych niż :n. Dane :m i :n to liczby całkowite dodatnie mniejsze od 10000. Zakładamy, że :m nie przekracza :n. Postaraj się napisać funkcję ILEPD w taki sposób, aby Jasio nie czekał długo na wynik.

ILEPD 10 100jest 22

Czy prawie doskonała?

Dzielniki właściwe to takie liczby, które są dzielnikami n, ale są od niej mniejsze. Jak wiadomo najmniejszym dzielnikiem różnym od 1 może być 2. Z tego powodu zakres wyszukiwania dzielników liczby można zawęzić do przedziału [2, n/2].

Ponadto program ma stwierdzić czy dana liczba n jest wielokrotnością sumy ich dzielników właściwych. Można to sprawdzić wykonując dzielenie n przez sumę dzielników. Jeśli reszta takiego dzielenia wynosi 0 to znaczy, że warunek został spełniony.

  1. oto czyPrawieDoskonała? :n
  2.   niech "dzielniki 0
  3.   powtórz (:n/2)[
  4.     jeśli (reszta :n npw = 0) [
  5.       niech "dzielniki :dzielniki + npw
  6.     ]
  7.   ]
  8.   wynik (reszta :n :dzielniki = 0)
  9. już

W pętli (3. - 7.) dla każdej liczby całkowitej z przedziału [2, n/2] (4.) sprawdź czy dzieli :n. Jeśli tak to (5.) do sumy dzielników dodaj aktualną wartość dzielnika. Na koniec (8.) zwróć wartość logiczną czy warunek został spełniony.

Funkcja główna

Funkcja główna sprawdza każdą liczbę z zakresu [:m, :n] i zlicza każdą wartość, która jest liczbą prawie doskonałą poprzez wywołanie funkcji czyPrawieDoskonała?. Na koniec zwraca wartość licznika :ile.

  1. oto ILEPD :m :n
  2.   niech "ile 0
  3.   dopóki [:m <= :n][
  4.     jeśli (czyPrawieDoskonała? :m) [
  5.       zwiększ "ile
  6.     ]
  7.     zwiększ "m
  8.   ]
  9.   wynik :ile
  10. już

Zadanie 3

Napisz funkcję MAXX :słowo, gdzie :słowo jest dowolnym niepustym słowem składającym się jedynie z małych liter alfabetu łacińskiego. Wynikiem funkcji jest najdłuższe podsłowo (fragment słowa - ciąg kolejnych znaków), które rozpoczyna się i kończy się tym samym znakiem. Jeśli w danym słowie jest wiele takich najdłuższych podsłów, to wynikiem jest dowolne z nich.

MAXX "bbbaaubueytwyetrywaxjest "aaubueytwyetrywa
MAXX "abcdefghijjest dowolny znak danego słowa

Strategia

Zadanie sprowadza się do znalezienia pierwszej wartości od lewej danego znaku i pierwszego wystąpienia tej samej litery od prawej strony. W ten sposób możliwe jest, że program będzie musiał 26 razy przejrzeć całe słowo (tyle ile jest liter).

Istnieje jednak rozwiązanie liniowe, które pozwala uogólnić działanie programu na dowolny zestaw znaków bez zmian w kodzie. Po pierwsze utwórzmy listę na której będą prezchowywane pary znak × liczba. Rozpoczynamy program od pierwszego znaku od lewej. Jeśli dana litera nie wystąpiła jeszcze na liście to jest ona zapisywana do listy i jako liczba podawana jest jej pozycja na liście. To gwarantuje, że na koniec działania funkcji będziemy znać pierwsze wystąpienie każdego znaku, które wystąpiła w :słowo.

Jednak w przypadku, gdy dany znak jest już na liście to znamy pierwsze występienie tego znaku w :słowo, więc istnieje możliwość obliczenia jaki fragment tekstu zostałby wycięty. Jeśli nowy, określony fragment jest dłuższy niż dotychczasowy to ustalamy, aby program na koniec zwrócił nowy znaleziony fragment.

Przykład działania

Weźmy słowo "abcbae". Rozpoczynając od początku program wykona następujące akcje:

List IndeksówAktualny znakWybrany fragment [od, max]Akcja
[]a (poz. 1)[0, 0]dopisz parę [a, 1] na listę i ustaw wybrany fragment na [1, 1]
[[a 1]]b (poz. 2)[1, 1]dopisz parę [b, 2] na listę
[[a 1], [b 2]]c (poz. 3)[1, 1]dopisz parę [c, 3] na listę
[[a 1], [b 2], [c, 3]]b (poz. 4)[1, 1]znak b został wcześniej znaleziony, długość nowego fragmentu to 3 co jest większe od 1, ustaw wybrany fragment na [2, 3]
[[a 1], [b 2], [c, 3]]a (poz. 5)[2, 3]znak a został wcześniej znaleziony, długość nowego fragmentu to 5 co jest większe od 3, ustaw wybrany fragment na [1, 5]
[[a 1], [b 2], [c, 3]]e (poz. 6)[1, 5]dopisz parę [e, 6] na listę

Zwrócony fragment rozpoczyna się od indeksu 1 i ma długość 5, więc jest to "abcba".

Rozwiązanie

Poniższy kod przedstawia opisane wyżej rozwiązanie:

  1. oto ILEPD :m :n
  2.   niech "ile 0
  3.   dopóki [:m <= :n][
  4.     jeśli (czyPrawieDoskonała? :m) [
  5.       zwiększ "ile
  6.     ]
  7.     zwiększ "m
  8.   ]
  9.   wynik :ile
  10. już

Inicjalizowane są kolejno (2.) lista par znak × liczba, (3.) aktualna długość najdłuższego podsłowa oraz (4.) indeks od którego dane słowo się rozpoczyna. (5.) Dla każdego znaku w tekście: (6.) pobierany jest element i (7.) dokonuje się sprawdzenia czy występuje on już na liście. Jeśli jest to (8.) pobierany jest indeks pierwszego wystąpienia danego znaku i (9.) wyliczana jest długość wybranego fragmentu. (10.) Jeśli wyliczona wartość jest większa od aktualnie wybranego fragmentu to należy zmienić (11.) długość i (12.) indeks początkowy.

(14.) Jednak jeśli znak do tej pory nie wystąpił to (15.) zostaje utworzona para i dodana do zmiennej :indeksy. Dodatkowo (16.) Jeśli to pierwszy znak to (17. - 18.) należy zmienić dane o wybranym fragmencie. Na koniec (22.) należy zwrócić fragment zaczynający się od indeksu :od i długości :max.