Zadanie 1.2, matura czerwiec 2020, informatyka rozszerzona

3 pktotwartetrudne 25%Czerwiec 2020

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 punkty

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.

Algorytm:

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

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

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.

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.