Zadanie 1.2, matura czerwiec 2020, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 1. Podobne tablice
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].
Polecenie
3 punktyZapisz 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.
Algorytm:
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
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]
wynik FAŁSZ
zakończ wykonywanie algorytmu
wynik PRAWDA
```
Sposób I. 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
```
Sposób III. 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
```
Schemat punktowania
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):
za prawidłowe porównanie wszystkich elementów tablicy A z odpowiednimi elementami tablicy B, w tym:
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)
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)
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):
za poprawne zapisanie w tablicy pomocniczej przestawionych elementów jednej z tablic (A lub B), w tym:
za każdy z dwóch fragmentów tablicy
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.
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.