Zadanie 2.2, matura maj 2018, informatyka rozszerzona

4 pktotwartetrudne 28%Maj 2018

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 xAyA<xByB\frac{x_A}{y_A}<\frac{x_B}{y_B};

• szczyt B jest widoczny na lewo od A, jeśli xAyA>xByB\frac{x_A}{y_A}>\frac{x_B}{y_B}.

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:

przykładowe położenie szczytów A, B, C i D oraz obserwatoraPowiększ
przykładowe położenie szczytów A, B, C i D oraz obserwatora

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]).

Polecenie

4 punkty

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

Korepetytor

Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.

Wypróbuj za darmo

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

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.

Uwaga: za każde inne niż przedstawione niżej, ale całkowicie poprawne rozwiązanie przyznajemy maksymalną liczbę punktów.

0 pkt

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.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.