Darmowe konto pozwoli wrócić do niego później.
Polecenie
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ępne w językach programowania.
Specyfikacja:
Dane:
Darmowe konto pozwoli wrócić do niego później.
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ę
Ocena według schematu punktowania CKE, zwykle w 15–30 s
Dowiedz się, ile punktów naprawdę zdobywasz. Zrób zdjęcie kartki albo wklej odpowiedź: Maturownik+ porówna ją ze schematem punktowania, policzy punkty i wytłumaczy, gdzie i dlaczego je tracisz.
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
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.
Za każde inne niż przedstawione, ale całkowicie poprawne rozwiązanie spełniające warunki zadania przyznajemy maksymalną liczbę punktów.
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