Zadanie 1.2, matura maj 2022, informatyka rozszerzona

4 pktotwartetrudne 31%Maj 2022

Darmowe konto pozwoli wrócić do niego później.

Zadanie

Zadanie 1. n-permutacja

Dla dodatniej liczby całkowitej n, n-permutacją nazywamy taki n-elementowy ciąg liczb całkowitych, który zawiera każdą z liczb 1, 2, …, n dokładnie jeden raz.

Przykład:

ciąg (4,2,1,3) jest 4-permutacją,

ciąg (6,5,4,1,2,3) jest 6-permutacją,

ciągi (1,3,1,2) i (2,3,4,5) nie są 4-permutacjami.

W ciągu n liczb całkowitych, który nie jest n-permutacją, można podmienić niektóre elementy tak, aby otrzymać n-permutację.

Przykład:

w ciągu (1,3,1) wystarczy podmienić jeden element – pierwszą lub ostatnią jedynkę (1) – na dwójkę (2), aby powstały ciąg był 3-permutacją.

Polecenie

4 punkty

Zapisz w pseudojęzyku lub wybranym języku programowania algorytm, który dla danego ciągu n dodatnich liczb całkowitych zapisanego w tablicy A obliczy najmniejszą liczbę elementów, które trzeba w nim podmienić, aby otrzymać n-permutację.

Uwaga: W zapisie algorytmu możesz korzystać tylko z instrukcji sterujących, operatorów arytmetycznych: dodawania, odejmowania, mnożenia, dzielenia, dzielenia całkowitego i reszty z dzielenia; operatorów logicznych, porównań, odwoływania się do pojedynczych elementów tablicy i 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.

Specyfikacja:

Dane:

n – dodatnia liczba całkowita

A[1..n] – tablica n dodatnich liczb całkowitych, gdzie A[i] jest i-tym elementem ciągu

Wynik:

k – minimalna liczba elementów, które trzeba podmienić w ciągu zapisanym w tablicy A, aby otrzymać n-permutację

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

Przykład 1:

```

dla i = 1, 2, …, n

B[i] ← 0

k ← 0

dla i = 1, 2, ..., n

jeżeli A[i]≤n

B[A[i]] ← B[A[i]]+1

w przeciwnym razie

k ← k+1

dla i = 1, 2, ..., n

jeżeli B[i]>1

k ← k + B[i] - 1

podaj wynik k

```

Przykład 2:

```

w ← 0;

dla i = 1, 2, …, n

dla j = 1, 2, .., n

jeżeli (A[j] = i)

w ← w+1

przerwij pętlę

k← n - w

podaj wynik k

```

Przykład 3:

```

dla i = 1, 2, …, n-1

dla j = i+1, i+2, …, n

jeżeli (A[i]>A[j])

x ← A[i]

A[i] ← A[j]

A[j] ← x

k ← 0;

dla i = 1, 2, …, n-1

jeżeli (A[i] = A[i+1] lub A[i]>n)

k ← k+1

jeżeli (A[n] > n)

k ← k+1

podaj wynik k

```

Schemat punktowania

4 pkt

za poprawny algorytm, w tym:

W przypadku algorytmu z przykładu 1:

1 pkt

za uwzględnienie liczb spoza przedziału [1, n].

3 pkt

za uwzględnienie liczb powtarzających się, w tym:

1 pkt

za prawidłową pętlę po wszystkich elementach A;

1 pkt

za prawidłowe liczenie duplikatów;

1 pkt

za prawidłowy algorytm ich sumowania.

W przypadku algorytmu sprawdzającego dla każdej liczby 1..n czy istnieje w ciągu (przykład 2):

1 pkt

za zliczenie brakujących liczb.

3 pkt

za wykrywanie brakujących liczb, w tym:

1 pkt

za prawidłową pętlę po wszystkich elementach 1..n;

1 pkt

za prawidłową pętlę po wszystkich elementach A;

1 pkt

za prawidłowy algorytm oznaczania brakujących (lub występujących) liczb.

W przypadku algorytmu wykorzystującego sortowanie (przykład 3):

2 pkt

za prawidłowy algorytm sortowania i wykorzystanie posortowanego ciągu w dalszej części algorytmu, w tym:

1 pkt

za prawidłowe pętle;

1 pkt

za prawidłowe przestawianie elementów.

2 pkt

za wykrywanie brakujących liczb, w tym:

1 pkt

za wykrywanie powtórzeń;

1 pkt

za wykrywanie wartości większych od n.

0 pkt

za odpowiedź błędną lub brak odpowiedzi.

Uwaga: za każde inne niż przedstawione niżej, ale całkowicie poprawne rozwiązanie spełniające warunki zadania przyznajemy maksymalną liczbę punktów.

Komentarz. Za każde inne niż przedstawione, ale całkowicie poprawne rozwiązanie spełniające warunki zadania przyznajemy maksymalną liczbę punktów.

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.