Darmowe konto pozwoli wrócić do niego później.
Polecenie
Zadanie 2. ab-słowo
Niech n będzie dodatnią liczbą całkowitą i niech s będzie słowem o długości n zbudowanym z liter a lub b. Zapis s[i] oznacza i-tą literę w tym słowie (1 ≤ i ≤ n).
Dla słowa s wykonujemy poniższy algorytm. Wynikiem działania algorytmu jest wartość zmiennej k.
Algorytm
A[0] ← 0
dla i = 1, 2, ..., n
jeżeli s[i] = 'a'
Darmowe konto pozwoli wrócić do niego później.
w przeciwnym razie
A[i] ← A[i – 1]
B[n + 1] ← 0
dla j = n, n – 1, ..., 1
jeżeli s[j] = 'b'
B[j] ← B[j + 1] + 1
w przeciwnym razie
B[j] ← B[j + 1]
k ← 1
dla i = 0, 1, 2, ..., n
jeżeli A[i] + B[i + 1] > k
k ← A[i] + B[i + 1]
Zadanie 2.1.
Uzupełnij tabelę – wpisz wynik działania algorytmu dla podanych wartości s.
| n | s | Wynik działania algorytmu (wartość k) |
|---|---|---|
| --- | --- | --- |
| 5 | aabab | 4 |
| 2 | ab | 2 |
| 3 | aaa | 3 |
| 6 | aababb | |
| 9 | baabbaaab |
1. aabab – 4
2. ab – 2
3. aaa – 3
4. aababb – 5
5. baabbaaab – 6
za poprawną odpowiedź w dwóch wierszach.
za poprawną odpowiedź w jednym wierszu.
Ocena według schematu punktowania CKE, zwykle w 15–30 s
Dowiedz się, ile punktów naprawdę zdobywasz. Zrób zdjęcie kartki albo wklej odpowiedź: Maturownik+ porówna ją ze schematem punktowania, policzy punkty i wytłumaczy, gdzie i dlaczego je tracisz.