Zadanie 2.4, matura czerwiec 2023, informatyka rozszerzona

3 pktotwarteśrednie (szac.)Czerwiec 2023

Darmowe konto pozwoli wrócić do niego później.

Zadanie

Zadanie 2. Sufiksy

Słowo definiujemy jako ciąg złożony z małych liter alfabetu angielskiego.

Niech s[1..n] będzie słowem o długości n > 0.

Sufiksem słowa s nazywamy każde jego podsłowo kończące na ostatniej pozycji słowa s. Sufiks s[k..n] nazywamy k-tym sufiksem.

Przykład 1.

słowo s[1..10] = mascarpone ma następujące sufiksy:

ks[k..n]
1mascarpone
2ascarpone
3scarpone
4carpone
5arpone
6rpone
7pone
8one
9ne
10e

Uporządkowanie alfabetyczne wszystkich sufiksów słowa mascarpone daje następującą kolejność ich numerów (od najmniejszego): 5, 2, 4, 10, 1, 9, 8, 7, 6, 3:

ks[k..n]
5arpone
2ascarpone
4carpone
10e
1mascarpone
9ne
8one
7pone
6rpone
3scarpone

Poniżej zapisano funkcję czy_mniejszy(n, s, k1, k2). Wynikiem funkcji jest wartość PRAWDA, gdy sufiks s[k1..n] jest mniejszy w porządku alfabetycznym od sufiksu s[k2..n] oraz FAŁSZ w przeciwnym przypadku.

Specyfikacja

Dane:

n – długość słowa,

s[1..n] – słowo zapisane jako tablica znaków (numerowanych od 1),

k1 – numer pierwszego sufiksu (1 ≤ k1 ≤ n),

k2 – numer drugiego sufiksu (1 ≤ k2 ≤ n, k1 ≠ k2).

Wynik:

PRAWDA jeśli sufiks s[k1..n] jest mniejszy w porządku alfabetycznym od s[k2..n], albo FAŁSZ – w przeciwnym wypadku.

```

czy_mniejszy (n, s, k1, k2)

i ← k1

j ← k2

dopóki ( i ≤ n oraz j ≤ n ) wykonuj

jeżeli ( s[i] == s[j] )

i ← i + 1

j ← j + 1

w przeciwnym razie

jeżeli ( s[i] < s[j] )

zakończ z wynikiem PRAWDA

w przeciwnym razie

zakończ z wynikiem FAŁSZ

jeżeli ( j ≤ n )

zakończ z wynikiem PRAWDA

w przeciwnym razie

zakończ z wynikiem FAŁSZ

```

Polecenie

3 punkty

W pliku slowa4.txt znajduje się 10 wierszy. Każdy wiersz zawiera liczbę n (1 ≤ n ≤ 100) oraz n-literowe słowo s składające się z małych liter alfabetu angielskiego. Dane w wierszu są oddzielone znakiem odstępu.

Napisz program, który dla każdego słowa s z pliku wypisze jego sufiks najmniejszy w porządku alfabetycznym.

Przykład:

Sufiksem najmniejszym w porządku alfabetycznym dla słowa mascarpone jest arpone, a dla słowa truskawki sufiksem najmniejszym w porządku alfabetycznym jest awki.

Dla przykładowego pliku sufiks_4.txt, zawierającego tylko 4 wiersze (ze słowami: banan, mascarpone, abcaabbaabbccba, maturazinformatyki), Twój program powinien dać odpowiedź:

```

an

arpone

a

aturazinformatyki

```

Wyniki zapisz w pliku wyniki2_4.txt, każdy sufiks w oddzielnym wierszu, zgodnie z kolejnością danych w pliku slowa4.txt.

Do oceny oddajesz:

• plik wyniki2_4.txt – zawierający odpowiedź do zadania 2.4.

• plik(i) zawierający(-e) kody źródłowe Twojego programu o nazwie(-ach):

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

```

ato

a

abracadabrad

abecadlo

aaababbbbcaababaz

a

aaababbbbcaababaaabcaabbccbbccbacbcaabbaabbccbbccbaaababbbbcaababaz

aaababbbbcaababaz

aaababbbbcaababacaacacaacaacaacacacacb

aaababbbbcacbabaaabcaabbccbbccbaabcaabbaabbccbbccbaaababbbbccababazbcabbab

```

Schemat punktowania

3 pkt

poprawna odpowiedź

2 pkt

prawidłowa odpowiedź dla pierwszych 5 słów

1 pkt

prawidłowa odpowiedź dla pierwszych 4 słów

0 pkt

odpowiedź niepoprawna albo brak rozwiązania.

W zadaniach praktycznych wszystkie wyniki muszą być odzwierciedleniem komputerowej realizacji obliczeń.

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.