Zadanie 2.2, matura czerwiec 2017, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 2. Regularność
W tym zadaniu rozważamy tylko słowa zbudowane z wielkich liter A i B. Słowo nazwiemy palindromem, gdy czytane od lewej do prawej jest takie samo jak czytane od prawej do lewej. Przykładowo słowo ABABA jest palindromem, natomiast palindromem nie jest słowo BAABA.
Dla słowa w definiujemy jego regularność reg(w), jak następuje:
– jeśli słowo w jest słowem jednoliterowym, to jest palindromem, a jego reg(w) = 1
– jeśli słowo w składa się z więcej niż jednej litery, to można je przedstawić w postaci:
w = w1Zw2, gdy ma długość nieparzystą
lub
w = w1w2, gdy ma długość parzystą,
gdzie w1, w2 są słowami tej samej długości, a Z jest literą A lub literą B.
Jeżeli w nie jest palindromem, definiujemy reg(w) = 0, natomiast gdy w jest palindromem definiujemy reg(w) = reg(w1) + 1.
Przykład:
| W | reg(w) |
|---|---|
| A | 1 |
| ABB | 0 |
| BAAAB | 1 |
| BBAAABB | 1 |
| BABBAB | 3 |
Polecenie
4 punktyW zaprezentowanej w tym punkcie funkcji REG(w,n) uzupełnij brakujące elementy tak, aby realizowała ona następującą specyfikację:
Specyfikacja:
Dane:
n – dodatnia liczba całkowita
w[1..n] – słowo złożone z liter A, B
Wynik:
– wartość reg(w).
```
Funkcja REG(w,n)
jeżeli n = 1
wynikiem jest
w przeciwnym przypadku
jeżeli n mod 2 = 0
m ← n / 2
w przeciwnym przypadku
m ← (n – 1) / 2
dla i=1,2,…,m wykonuj
jeżeli w[i] ≠
podaj wynik 0 i zakończ wykonywanie funkcji
x ← w[1..m]
wynikiem jest 1 +
```
Uwaga: mod – reszta z dzielenia całkowitego
Korepetytor
Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.
5 rozmów · bez karty · Zaloguj się
Sprawdź się
Jak poszło?
Pokaż rozwiązanieUkryj rozwiązanie
Odpowiedź z klucza CKE
Poprawne uzupełnienia kolejnych luk:
```
1
w[n+1-i]
REG(w[1..m],m)
```
W trzeciej luce dopuszcza się także REG(x,m).
Schemat punktowania
poprawne uzupełnienie pierwszej luki (wynikiem jest 1).
poprawne uzupełnienie drugiej luki (w[i] ≠ w[n+1-i]).
poprawne uzupełnienie trzeciej luki (wynikiem jest 1 + REG(w[1..m],m) lub 1 + REG(x,m)).
Komentarz. Algorytm sprawdza, czy słowo jest palindromem. Warunek w[i] ≠ w[n+1-i] porównuje znaki z obu końców słowa.