Zadanie 2.2, matura czerwiec 2026, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 2. Algorytm
Dane są: liczba n > 1 oraz tablica T[1..n] zawierająca liczby całkowite. Dla liczby całkowitej 1 ≤ k < n powiemy, że tablica T jest k-podobna wtedy i tylko wtedy, gdy T[1..k] = T[n − k + 1..n]. Ponadto przyjmujemy, że każda tablica jest 0-podobna (k = 0).
Przykład:
Tablica T = [1, 2, 1, 1, 2, 1, 1] jest 0-podobna, 1-podobna i 4-podobna.
Tablica T = [1, 2, 2] jest 0-podobna.
Tablica T = [2, 2, 2] jest 0-podobna, 1-podobna i 2-podobna.
Uwaga:
T = [2, 2, 2] nie jest 3-podobna, bo k musi być mniejsze niż liczba elementów tablicy (analogicznie T = [1, 2, 2] nie jest 3-podobna, a T = [1, 2, 1, 1, 2, 1, 1] nie jest 7-podobna).
Polecenie
4 punktyW pseudokodzie lub w zadeklarowanym języku programowania zapisz algorytm, który oblicza największe takie k, dla którego tablica T jest k-podobna.
Uwaga: W zapisie algorytmu możesz korzystać tylko z operatorów arytmetycznych: dodawania, odejmowania, mnożenia, dzielenia, dzielenia całkowitego i reszty z dzielenia; operatorów logicznych, porównań liczb, odwoływania się za pomocą indeksów do pojedynczych elementów tablicy, instrukcji sterujących, instrukcji przypisania lub samodzielnie napisanych funkcji i procedur wykorzystujących powyższe operacje. Zabronione jest używanie funkcji wbudowanych oraz operatorów innych niż wymienione, dostępnych w językach programowania, w szczególności nie wolno używać operacji pobierania fragmentu tablicy (listy).
Specyfikacja:
Dane:
n – liczba całkowita większa od 1
T[1..n] – tablica n liczb
Wynik:
k – największe takie k, dla którego tablica T jest k-podobna
Miejsce na zapis algorytmu
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
Rozwiązanie przykładowe:
```
k ← n – 1
jest ← fałsz
dopóki jest = fałsz
jest ← prawda
dla i = 1, 2, .., k wykonaj
jeżeli (T[i] ≠ T[n – k + i])
jest ← fałsz
jeżeli jest = fałsz
k ← k – 1
```
Schemat punktowania
za poprawny algorytm, w tym:
za poprawną pętlę po potencjalnych k (od 0 do n-1 lub od n-1 do 0)
za poprawną pętlę sprawdzającą potencjalne k
za poprawny warunek w pętli sprawdzającej potencjalne k
za otrzymanie poprawnego wyniku
odpowiedź niepoprawna albo brak rozwiązania
Uwaga: za każde inne, ale całkowicie poprawne rozwiązanie spełniające warunki zadania przyznajemy maksymalną liczbę punktów.
Komentarz. Za każde inne, ale całkowicie poprawne rozwiązanie spełniające warunki zadania przyznajemy maksymalną liczbę punktów.