Zadanie 2.2, matura maj 2018, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 2. Krajobraz
W pewnym paśmie górskim znajduje się n szczytów, które będziemy przedstawiać jako punkty w układzie kartezjańskim na płaszczyźnie. Wszystkie punkty leżą powyżej osi OX, tzn. druga współrzędna (y) każdego punktu jest dodatnia.
W punkcie (0,0) stoi obserwator. Jeśli dwa szczyty A i B mają współrzędne (xA, yA) oraz (xB, yB), to mówimy, że:
• szczyt A jest dla obserwatora widoczny na lewo od B, jeśli ;
• szczyt B jest widoczny na lewo od A, jeśli .
Wiemy, że żadne dwa szczyty nie leżą w jednej linii z obserwatorem, a zatem dla obserwatora te szczyty nie zasłaniają się nawzajem. Ilustrację przykładowego położenia szczytów można zobaczyć na poniższym rysunku:
PowiększW tym przykładzie, patrząc od lewej do prawej strony, obserwator widzi kolejno szczyt D, szczyt A, szczyt B i szczyt C.
Współrzędne szczytów dane są w dwóch tablicach X[1..n] oraz Y[1..n] – szczyt numer i ma współrzędne (X[i], Y[i]).
Polecenie
4 punktyNapisz 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
X[1..n] – tablica liczb całkowitych
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.
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ł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):
```
dla i = 2, 3, ..., n:
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
```
Schemat punktowania
za poprawny algorytm, w tym:
za poprawną konstrukcję zewnętrznej pętli algorytmu sortowania,
za poprawną konstrukcję wewnętrznej pętli algorytmu sortowania,
za poprawne porównanie elementów,
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.
Uwaga: za każde inne niż przedstawione niżej, ale całkowicie poprawne rozwiązanie przyznajemy maksymalną liczbę punktów.
za podanie odpowiedzi błędnej albo brak odpowiedzi.
Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.
Komentarz. 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.