Prezentacja multimedialna

Zadanie teoretyczne typu „ułóż algorytm”

Poniższe zadanie pochodzi z części $I$ arkusza rozszerzonego egzaminu maturalnego z informatyki z maja $2018$ roku. Jest dostępne w oryginalnej formie na oficjalnej stronie internetowej Centralnej Komisji Egzaminacyjnej.

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 $\left(0,\ 0\right)$ stoi obserwator. Jeśli dwa szczyty $A$ i $B$ mają współrzędne $\left(x_A,\ y_A\right)$ oraz $\left(x_B,\ y_B\right)$ , to mówimy, że:

szczyt $A$ jest dla obserwatora widoczny na lewo od $B$ , jeśli $\frac{x_A}{y_A}\lt\frac{x_B}{y_B}$ ,
szczyt $B$ jest widoczny na lewo od $A$ , jeśli $\frac{x_A}{y_A}\gt\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 rysunku:

RNoXMtNpunEdR

Ilustracja przedstawia układ współrzędnych z poziomą osią X oraz z pionową osią Y. Na płaszczyźnie umieszczono punkty: A, B, C, D. Od punktu przecięcia osi X z osią Y (0, 0) wychodzą przerywane linie dążące do punktów D(-2, 2), A(1, 3), B(3, 4), C(2, 1). — Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

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 1

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 problemu:

Dane:

n – liczba całkowita dodatnia
X[0..n - 1] – tablica liczb całkowitych
Y[0..n - 1] – tablica liczb całkowitych dodatnich
Para (X[i], Y[i]) to współrzędne jednego szczytu, i = 0, 1, ..., n - 1.
Ż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

RpQoSKDRePEGX

Polecenie 2

Porównaj swoje rozwiązanie z rozwiązaniem przedstawionym w prezentacji.

ROy2cB1CBdroQ1

Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

Praca domowa

W wybranym języku programowania zaimplementuj algorytm z problemu $1$ .

RJEqPbq8N7EhO

Problem 1

Napisz za pomocą pseudokodu algorytm, 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. 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 problemu:

Dane:

n – liczba całkowita dodatnia
X[0..n - 1] – tablica liczb całkowitych
Y[0..n - 1] – tablica liczb całkowitych dodatnich
Para (X[i], Y[i]) to współrzędne jednego szczytu, i = 0, 1, ..., n - 1
Żadne dwa szczyty nie leżą w jednej linii z obserwatorem.

Wynik:

X[0..n - 1], Y[0..n - 1] – 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.

Rx7pga8H3lzHY

Polecenie 3

Porównaj swoje rozwiązanie z przedstawionym w prezentacji.

R1FoYK0RWfbZb1

Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

Praca domowa

W wybranym języku programowania zaimplementuj algorytm z problemu $2$ .

R1PDTa4VigW6J

Przeczytaj

Sprawdź się

Zadanie teoretyczne typu „ułóż algorytm”