Zadanie 2.2, matura czerwiec 2017, informatyka rozszerzona

4 pktotwarteśrednie (szac.)Czerwiec 2017

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:

Wreg(w)
A1
ABB0
BAAAB1
BBAAABB1
BABBAB3

Polecenie

4 punkty

W 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.

Wypróbuj za darmo

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

1 pkt

poprawne uzupełnienie pierwszej luki (wynikiem jest 1).

1 pkt

poprawne uzupełnienie drugiej luki (w[i] ≠ w[n+1-i]).

2 pkt

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.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.