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 xA/yA < xB/yB ;
- szczyt B jest widoczny na lewo od A, jeśli xA/yA > xB/yB .
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:
W 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]).
Zadanie 2.1. (0–2)
Napisz algorytm (w pseudokodzie lub wybranym języku programowania), który znajdzie i poda współrzędne skrajnie lewego szczytu, tzn. widocznego dla obserwatora na lewo od wszystkich pozostałych szczytów.
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, y – współrzędne skrajnie lewego szczytu spośród tych opisanych w tablicach X i Y.
Algorytm
Zadanie 2.2. (0–4)
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
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
Przykład
float Y[]={3, 4, 1, 2};
Przykładowe rozwiązania 2.1.
Przykładowe rozwiązanie wersja 1.
Pseudokod CKE [2]
k ← 1
dla i = 2, 3, ..., n
jeżeli X[i] / Y[i] < X[k] / Y[k]
k ← i
x ← X[k]
y ← Y[k]
C++
int k = 1;
int x = X[k];
int y = Y[k];
for (int i = 1; i < n; i = i + 1) {
if (X[i] / Y[i] < X[k] / Y[k]) {
k = i;
}
}
x = X[k];
y = Y[k];
Przykładowe rozwiązanie wersja 2.
Pseudokod CKE [3] poprawiony
i ← 1
x ← X[i]
y ← Y[i]
dopóki i ≤ n wykonuj
jeżeli X[i] / Y[i] < x / y
x ← X[i]
y ← Y[i]
i ← i + 1
C++
int x = X[i];
int y = Y[i];
int i = 2;
while (i <= n) {
if (X[i] / Y[i] < x / y) {
x = X[i];
y = Y[i];
}
i = i + 1;
}
Python
def main():
k = 1
n = 4
X = [1, 3, 2, -2]
Y = [3, 4, 1, 2]
x = X[k]
y = Y[k]
for i in range(1, n):
if X[i] / Y[i] < X[k] / Y[k]:
k = i
x = X[k]
y = Y[k]
print("x=", x, " y=", y)
if __name__ == "__main__":
main()
Przykładowe rozwiązania 2.2
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] wykonuj
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
Poziom wykonania zadania: 2.1. - 36%; 2.2. - 28%;
Przypisy
- https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Arkusze_egzaminacyjne/2018/formula_od_2015/informatyka/MIN-R1_1P-182.pdf
- https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Arkusze_egzaminacyjne/2018/formula_od_2015/Zasady_oceniania/MIN-R2_1P-182_zasady_oceniania.pdf
- https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Informacje_o_wynikach/2018/sprawozdanie/Sprawozdanie%202018%20-%20Informatyka.pdf