Darmowe konto pozwoli wrócić do niego później.
Polecenie
Napisz algorytm (w pseudokodzie lub wybranym języku programowania), który przestawi elementy tablic X i Y tak, aby szczyty były uporządkowane w kolejności, w której obserwator widzi je od lewej do prawej strony. Aby otrzymać maksymalną ocenę, Twój algorytm powinien mieć złożoność czasową kwadratową lub mniejszą.
Algorytm może używać wyłącznie instrukcji sterujących, operatorów arytmetycznych, operatorów logicznych, porównań i przypisań do zmiennych. Zabronione jest używanie funkcji bibliotecznych dostępnych w językach programowania.
Specyfikacja:
Dane:
n – liczba całkowita dodatnia
Darmowe konto pozwoli wrócić do niego później.
Y[1..n] – tablica liczb całkowitych dodatnich
Para (X[i], Y[i]) to współrzędne jednego szczytu, i = 1, 2, …, n.
Żadne dwa szczyty nie leżą w jednej linii z obserwatorem.
Wynik:
X[1..n], Y[1..n] – tablice zawierające współrzędne danych szczytów, uporządkowanych w kolejności, w której obserwator widzi je od lewej do prawej strony.
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ładowe rozwiązanie 1 (sortowanie bąbelkowe):
powtarzaj n-1 razy:
dla i = 1, 2, ..., n-1
jeżeli X[i+1]/Y[i+1] < X[i]/Y[i]
t = X[i]
X[i] = X[i+1]
X[i+1] = t
t = Y[i]
Y[i] = Y[i+1]
Y[i+1] = t
Przykładowe rozwiązanie 2 (sortowanie przez wybór):
dla i = 1, 2, ..., n-1:
m = i
dla j = i+1, i+2, ..., n
jeżeli X[j]/Y[j] < X[m]/Y[m]
m = j
t = X[i]
X[i] = X[m]
X[m] = t
t = Y[i]
Y[i] = Y[m]
Y[m] = t
Przykładowe rozwiązanie 3 (sortowanie przez wstawianie):
4 pkt – za poprawny algorytm, w tym:
1 pkt – za poprawną konstrukcję zewnętrznej pętli algorytmu sortowania,
1 pkt – za poprawną konstrukcję wewnętrznej pętli algorytmu sortowania,
1 pkt – za poprawne porównanie elementów,
1 pkt – za poprawną zamianę elementów uwzględniającą zarówno X, jak i Y.
Uwaga: za prawidłowe rozwiązanie o złożoności większej niż kwadratowa – maksymalnie 3 punkty.
Akceptowane są sortowanie bąbelkowe, przez wybór, przez wstawianie i inne algorytmy sortowania o złożoności O(n²) lub lepszej. Każde inne całkowicie poprawne rozwiązanie otrzymuje maksymalną liczbę punktów.
j = i
dopóki j>1 oraz X[j]/Y[j]<X[j-1]/Y[j-1]:
t = X[j]
X[j] = X[j-1]
X[j-1] = t
t = Y[j]
Y[j] = Y[j-1]
Y[j-1] = t
j = j-1