Zadanie 2.4, matura czerwiec 2023, informatyka rozszerzona
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:
| k | s[k..n] |
|---|---|
| 1 | mascarpone |
| 2 | ascarpone |
| 3 | scarpone |
| 4 | carpone |
| 5 | arpone |
| 6 | rpone |
| 7 | pone |
| 8 | one |
| 9 | ne |
| 10 | e |
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:
| k | s[k..n] |
|---|---|
| 5 | arpone |
| 2 | ascarpone |
| 4 | carpone |
| 10 | e |
| 1 | mascarpone |
| 9 | ne |
| 8 | one |
| 7 | pone |
| 6 | rpone |
| 3 | scarpone |
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 punktyW 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.
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
poprawna odpowiedź
prawidłowa odpowiedź dla pierwszych 5 słów
prawidłowa odpowiedź dla pierwszych 4 słów
odpowiedź niepoprawna albo brak rozwiązania.
W zadaniach praktycznych wszystkie wyniki muszą być odzwierciedleniem komputerowej realizacji obliczeń.