Niech n będzie dodatnią liczbą całkowitą, a A[1..n] i B[1..n] będą n-elementowymi tablicami liczb całkowitych.
Dla nieujemnej liczby całkowitej k, gdzie k < n, powiemy, że tablice A i B są k-podobne, gdy A[1..k] = B[n-k+1..n] oraz A[k+1..n] = B[1..n-k]. Liczbę k nazywamy świadectwem podobieństwa.
Uwaga: dla k = 0 przyjmujemy, że prawdziwe jest A[1..0]=B[n+1..n].
Zadanie 1.1. (0–1)
Uzupełnij tabelę – wpisz w pustych kratkach odpowiednie wartości. W wierszu piątym i siódmym wpisz słowo PRAWDA, jeśli tablice A i B są k-podobne przy podanym k, albo FAŁSZ w przeciwnym przypadku. W wierszu szóstym wpisz takie k, dla którego tablice A i B są k-podobne.
| Lp. | n | Tablica A | Tablica B | k | odp. |
| 1. | 3 | [5, 7, 9] | [5, 7, 9] | 0 | PRAWDA |
| 2. | 5 | [4, 7, 1, 4, 5] | [1, 4, 5, 4, 7] | 2 | PRAWDA |
| 3. | 5 | [10, 9, 12, 10, 9] | [10, 10, 9, 9, 12] | 3 | FAŁSZ |
| 4. | 5 | [3, 6, 5, 1, 8] | [5, 1, 8, 3, 6] | 4 | FAŁSZ |
| 5. | 5 | [1, 2, 3, 4, 5] | [3, 4, 5, 1, 2] | 2 | |
| 6. | 9 | [1,1,1,1,3,1,1,1,1] | [3,1,1,1,1,1,1,1,1] | PRAWDA | |
| 7. | 6 | [4, 2, 4, 4, 2, 6] | [4, 4, 2, 6, 4, 2] | 1 |
Zadanie 1.2. (0–3)
Zapisz w wybranej przez siebie notacji (w postaci pseudokodu, listy kroków lub w wybranym języku programowania) funkcję czy_k_podobne(n, A, B, k), gdzie A i B są n-elementowymi tablicami liczb całkowitych. Wynikiem funkcji jest PRAWDA, jeśli tablice A i B są k-podobne dla zadanego parametru k, natomiast FAŁSZ – w przeciwnym przypadku.
Uwaga: w zapisie możesz wykorzystać tylko operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, reszta z dzielenia), odwoływanie się do pojedynczych elementów tablicy, porównywanie liczb, instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane funkcje zawierające wyżej wymienione operacje.
Specyfikacja:
Dane:
n – dodatnia liczba całkowita
A[1..n], B[1..n] – n-elementowe tablice liczb całkowitych
k – nieujemna liczba całkowita mniejsza niż n
Wynik:
PRAWDA, jeśli tablice A i B są k-podobne dla podanego parametru k
FAŁSZ w przeciwnym przypadku.
Zadanie 1.3. (0–2)
Zapisz w wybranej przez siebie notacji funkcję czy_podobne(n, A, B), która dla danych tablic A i B daje odpowiedź PRAWDA, jeśli istnieje takie k, dla którego tablice A i B są k-podobne, natomiast FAŁSZ – w przeciwnym przypadku.
Uwaga: w zapisie możesz skorzystać jedynie z operacji wymienionych w zadaniu 1.2. oraz funkcji czy_k_podobne(n, A, B, k) opisanej w zadaniu 1.2.
Specyfikacja:
Dane:
n – dodatnia liczba całkowita
A[1..n], B[1..n] – n-elementowe tablice liczb całkowitych
Wynik:
PRAWDA, jeśli istnieje takie k (0 ≤ k < n), dla którego tablice A i B są k-podobne
FAŁSZ w przeciwnym przypadku.
Zasady oceniania
1 pkt – za poprawną odpowiedź
0 pkt – za podanie odpowiedzi niepoprawnej lub niepełnej albo brak odpowiedzi
| Lp. | n | Tablica A | Tablica B | k | odp. |
| 1. | 3 | [5, 7, 9] | [5, 7, 9] | 0 | PRAWDA |
| 2. | 5 | [4, 7, 1, 4, 5] | [1, 4, 5, 4, 7] | 2 | PRAWDA |
| 3. | 5 | [10, 9, 12, 10, 9] | [10, 10, 9, 9, 12] | 3 | FAŁSZ |
| 4. | 5 | [3, 6, 5, 1, 8] | [5, 1, 8, 3, 6] | 4 | FAŁSZ |
| 5. | 5 | [1, 2, 3, 4, 5] | [3, 4, 5, 1, 2] | 2 | PRAWDA |
| 6. | 9 | [1,1,1,1,3,1,1,1,1] | [3,1,1,1,1,1,1,1,1] | 4 | PRAWDA |
| 7. | 6 | [4, 2, 4, 4, 2, 6] | [4, 4, 2, 6, 4, 2] | 1 | FAŁSZ |
Zasady oceniania
3 pkt – za poprawny algorytm, w tym:
w przypadku rozwiązania bazującego na porównaniu odpowiednich elementów tablicy A z odpowiadającymi elementami tablicy B przez modyfikowanie indeksów (zapisanego za pomocą jednej pętli – sposób I lub dwóch pętli – sposób II):
2 pkt – za prawidłowe porównanie wszystkich elementów tablicy A
z odpowiednimi elementami tablicy B, w tym:
1 pkt – za prawidłową konstrukcję pętli (sposób I)
ALBO
za porównanie pierwszej części tablicy A z odpowiednią częścią
tablicy B (sposób II)
1 pkt – za prawidłowe indeksy tablic A i B (sposób I)
ALBO
za porównanie drugiej części tablicy A z odpowiednią częścią
tablicy B (sposób II)
1 pkt – za wykrycie niezgodnej wartości w tablicach i otrzymanie prawidłowego wyniku
w przypadku rozwiązania bazującego na wykorzystaniu pomocniczej tablicy (sposób III):
2 pkt – za poprawne zapisanie w tablicy pomocniczej przestawionych elementów jednej z tablic (A lub B), w tym: 1 pkt – za każdy z dwóch fragmentów tablicy
1 pkt – za porównanie (w pętli – tj. element po elemencie) tablicy pomocniczej z drugą z tablic (B lub A) oraz wykrycie niezgodnej wartości prowadzące do otrzymania poprawnego wyniku.
0 pkt – za podanie odpowiedzi niepoprawnej albo brak odpowiedzi.
Uwaga: Jeżeli zdający wykonuje porównanie tylko dla jednej części tablic A i B to może otrzymać maksymalnie 1 punkt za całe rozwiązanie.
Przykładowe rozwiązania poprawione
Sposób I
Przykładowe rozwiązanie 1:
funkcja czy_k_podobne(n, A, B, k)
dla i = 1, 2, ..., n
j ← i - k
jeżeli j < 1
j ← j + n
jeżeli A[i] ≠ B[j]
zwróć FAŁSZ
zakończ
zwróć PRAWDA
Przykładowe rozwiązanie 2:
funkcja czy_k_podobne(n, A, B, k)
dla i = 0,1,...,n-1
jeżeli B[i+1] ≠A[((i+k) mod n) + 1]
wynik FAŁSZ
zakończ wykonywanie algorytmu
wynik PRAWDA
Sposób II
Przykładowe rozwiązanie 3:
funkcja czy_k_podobne(n, A, B, k)
dla i = 1,2,...,k
jeżeli B[n-k+i] ≠A[i]
wynik FAŁSZ
zakończ wykonywanie algorytmu
dla i =1,2,...,n-k
jeżeli B[i] ≠A[k+i]
wynik FAŁSZ
zakończ wykonywanie algorytmu
wynik PRAWDA
Sposób III
Przykładowe rozwiązanie 4:
funkcja czy_k_podobne(n, A, B, k)
dla i=1,2, ... k
C[i] = B[i-k+n]
dla i=k+1,k+2, ... n
C[i] = B[i-k]
dla i=1,2, ... n
jeżeli (A[i] ≠ C[i])
wynik FAŁSZ
zakończ wykonywanie algorytmu
wynik PRAWDA
Przykładowe rozwiązanie 5:
funkcja czy_k_podobne(n, A, B, k)
dla i=1,2, ... k
C[i] = B[i-k+n]
dla i=1,2, ... n-k
C[k+i] = B[i]
dla i=1,2, ... n
jeżeli (A[i] ≠ C[i])
wynik FAŁSZ
zakończ wykonywanie algorytmu
wynik PRAWDA
Zasady oceniania
2 pkt – za poprawny algorytm, w tym:
1 pkt – za prawidłową konstrukcję pętli uwzględniającą wszystkie możliwe przesunięcia
liczb
1 pkt – za prawidłowy warunek prowadzący do otrzymania prawidłowego wyniku.
0 pkt – za podanie odpowiedzi błędnej albo brak odpowiedzi.
Przykładowe rozwiązanie
dla k = 0,1,...,n-1
jeżeli czy_k_podobne(n,A,B,k) = prawda
wynik PRAWDA
zakończ algorytm
wynik FAŁSZ
Poziom wykonania zadania (%) - 26
Przykładowe rozwiązania
Sposób I
Przykładowe rozwiązanie 1:
#include <iostream>
using namespace std;
bool czy_k_podobne(int n, int A[], int B[], int k) {
for (int i = 0; i < n; i++) {
int j = i - k;
if (j < 0) {
j += n;
}
if (A[i] != B[j]) {
return false;
}
}
return true;
}
int main() {
int n = 3;
int A[] = {5, 7, 9};
int B[] = {5, 7, 9};
int k = 0;
if (czy_k_podobne(n, A, B, k)) {
cout << "PRAWDA";
}
else {
cout << "FALSZ";
}
return 0;
}