Zadanie 2.1, matura maj 2018, informatyka rozszerzona

2 pktotwartetrudne 36%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

2 punkty

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

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

```

k ← 1

dla i = 2, 3, ..., n wykonuj

jeżeli X[i]/Y[i] < X[k]/Y[k]

k ← i

x ← X[k], y ← Y[k]

```

Schemat punktowania

2 pkt

za poprawny algorytm, w tym:

1 pkt

za prawidłową inicjalizację oraz konstrukcję pętli,

1 pkt

za zastosowanie prawidłowego porównania oraz wyznaczenie współrzędnych skrajnie lewego szczytu.

Uwaga: za prawidłowe porównanie i wyznaczenie poprawnej najmniejszej wartości ilorazu współrzędnych oraz poprawnego indeksu – 1 punkt.

0 pkt

za podanie odpowiedzi błędnej albo brak odpowiedzi.

Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.

Komentarz. Aby uniknąć dzielenia zmiennoprzecinkowego, można porównywać X[i]*Y[k] < X[k]*Y[i] zamiast X[i]/Y[i] < X[k]/Y[k], pamiętając że Y wartości są dodatnie.

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.