Zadanie 2. Ewolucja. (15 pkt)
Na planecie MLAP każdy żyjący organizm ma postać napisu złożonego z dużych liter
alfabetu łacińskiego. Każdy nowo powstały organizm opisywany jest literą A. Po każdym
roku życia wielkość organizmu podwaja się w taki sposób, że każda z liter zostaje zastąpiona
dwiema literami zgodnie z pewnym ustalonym zbiorem reguł postaci:
L → F S
oznaczających, że literę L można zastąpić przez dwie litery: F S. O literze L mówimy
wówczas, że występuje po lewej stronie reguły, a F i S występują po prawej stronie reguły.
Przez wielkość organizmu rozumiemy tutaj długość odpowiedniego napisu.
Rozważmy następujący zbiór reguł:
A → B C
A → C D
B → A D
C → B A
D → A A
D → B B
Wówczas organizmy roczne mogą przyjąć jedną z postaci:
B C
C D
zaś dwuletnie
A D B A (A → B C → A D B A)
B A A A (A → C D → B A A A)
B A B B (A → C D → B A B B)
O dwóch organizmach mówimy, że są w danym momencie odróżnialne, jeśli różne są
odpowiadające im napisy (mają różne długości lub różnią się na co najmniej jednej pozycji).
a) Wypisz poniżej wszystkie odróżnialne organizmy trzyletnie, które można uzyskać
z organizmu dwuletniego o postaci ADBA.
5
Arkusz I
b) Podaj sposób sprawdzania dla danej liczby naturalnej n ≥ 1, czy mogą istnieć organizmy
o długości n. W przypadku odpowiedzi pozytywnej należy również ustalić wiek
organizmu o wielkości n. Podaj, ile poprawnych wielkości organizmów występuje
w przedziale (n, m] dla liczb naturalnych n i m, gdzie n < m. Odpowiedź uzasadnij.
c) Przyjmijmy, że każda litera pojawiająca się w regułach występuje dokładnie raz po lewej
stronie reguły, przed „strzałką” (zauważmy, że powyższy przykład nie spełnia tego
warunku, ponieważ litery A i D występują każda z lewej strony w dwóch regułach). Ile
odróżnialnych organizmów w wieku 1, 2, 3 itd. może wówczas występować? Odpowiedź
uzasadnij.
d) Poniżej przedstawiona jest funkcja wspomagająca realizację następującego zadania: dla
zadanego zbioru reguł, nowo powstałego organizmu start i danego napisu należy ustalić,
czy napis ten przedstawia organizm, który można uzyskać przy pomocy reguł zadanych
w treści zadania.
Niech:
L1→F1 S1, L2→F2 S2, , Lp→Fp Sp - dany zbiór reguł
Specyfikacja funkcji sprawdź:
Dane: napis - ,
start - ,
Wynik: odpowiedź, czy napis przedstawia organizm, który można uzyskać przy
pomocy podanych reguł, gdy nowo powstały organizm jest opisywany przez start.
6
Arkusz I
Treść funkcji sprawdź:
¾ jeśli długość napisu nie jest potęgą liczby 2, to zakończ wykonywanie funkcji
z odpowiedzią NIE.
W przeciwnym razie wykonuj:
¾ jeśli napis = start, to zakończ wykonywanie funkcji z odpowiedzią TAK;
¾ jeśli długość napisu jest równa 1, to zakończ wykonywanie funkcji
z odpowiedzią NIE;
¾ podziel napis na dwie równe części: napis1 i napis2;
¾ dla i=1, 2, , p wykonuj:
o jeśli Li = start, to
wykonaj funkcję sprawdź rekurencyjnie dla napis = napis1,
start = Fi oraz dla napis = napis2 i start = Si;
jeśli oba rekurencyjne wywołania funkcji sprawdź zakończyły
się odpowiedzią TAK, to zakończ wykonywanie funkcji
z odpowiedzią TAK;
¾ jeśli w powyższej pętli nie zakończyliśmy działania funkcji, to zakończ jej
wykonywanie z odpowiedzią NIE.
Dla podanej powyżej funkcji uzupełnij jej specyfikację.
Podaj parametry wszystkich rekurencyjnych wywołań funkcji sprawdź przy uruchomieniu jej
dla następującego zbioru reguł:
A → B C
A → C D
B → A D
C → B A
D → A A
D → B B
oraz napis = B C A A A D C D i start = A.
Jaką odpowiedź da funkcja w tym przypadku?
7
Arkusz I
Punktacja:
Część zadania
Maks.
a)
2
b)
4
c)
2
d)
7
Razem
15
8
Arkusz I
Za każdy wariant maksymalnie 2 punkty.
15