Zadanie 1.2, matura maj 2022, informatyka rozszerzona
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 punktyZapisz 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.
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
za poprawny algorytm, w tym:
W przypadku algorytmu z przykładu 1:
za uwzględnienie liczb spoza przedziału [1, n].
za uwzględnienie liczb powtarzających się, w tym:
za prawidłową pętlę po wszystkich elementach A;
za prawidłowe liczenie duplikatów;
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):
za zliczenie brakujących liczb.
za wykrywanie brakujących liczb, w tym:
za prawidłową pętlę po wszystkich elementach 1..n;
za prawidłową pętlę po wszystkich elementach A;
za prawidłowy algorytm oznaczania brakujących (lub występujących) liczb.
W przypadku algorytmu wykorzystującego sortowanie (przykład 3):
za prawidłowy algorytm sortowania i wykorzystanie posortowanego ciągu w dalszej części algorytmu, w tym:
za prawidłowe pętle;
za prawidłowe przestawianie elementów.
za wykrywanie brakujących liczb, w tym:
za wykrywanie powtórzeń;
za wykrywanie wartości większych od n.
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.