Zadanie 2.1, 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
2 punktyNapisz 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.
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
za poprawny algorytm, w tym:
za prawidłową inicjalizację oraz konstrukcję pętli,
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.
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.