Po kolei - wszystko zaczyna się od n, czyli liczby szczytów, które będzie trzeba porównać. A więc potrzebna będzie z pewnością pętla.
Dalej - musimy dobrze zrozumieć, kiedy który szczyt będzie znajdować się w jakim miejscu. Informacje o tym znajdują się tutaj:
"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."
Z tego możemy wyciągnąć wniosek, że im mniejszy jest wynik stosunku x do y, tym nasz szczyt będzie bardziej wysunięty ku lewej stronie. Przykładowo: Dla szczytu A(8, 4) stosunek wynosi 8/4=2, szczyt B(3, 6) natomiast będzie miał stosunek równy 0,5. Oznacza to, że B będzie po lewej stronie A, ponieważ stosunek współrzędnych szczytu B jest mniejszy! Zrozumiałe, prawda? 😎
Okej, przypomnijmy, co mamy obliczyć: "napisz algorytm, który [...] poda współrzędne skrajnie lewego szczytu".
Czyli najpierw będziemy mieli pętlę, która wykona się n razy, a potem porównywamy kolejne stosunki współrzędnych i wybierzemy ten, który jest najmniejszy!
Proponuję zastosować tutaj algorytm na element minimalny, o którym możemy poczytać np. tutaj, jeśli go jeszcze nie znamy.
Zapisujemy więc w pseudokodzie:
lewy_indeks = 1 // indeks szczytu najbardziej na lewo
i = 2
dopóki i <= n:
szczyt = X[i]/Y[i]
lewy_szczyt = X[lewy_indeks]/Y[lewy_indeks]
jeżeli szczyt < lewy_szczyt:
lewy_indeks = i
i += 1
x = X[lewy_indeks]
y = Y[lewy_indeks]
Zaledwie kilkoma linijkami udało się zdobyć dwa punkty, a można jeszcze bardziej skrócić ten pseudokod, do czego zachęcam! 😉
Musieliśmy skorzystać ze zmiennej lewy_indeks, ponieważ w wymogach zadania jest "Wynik: x, y – współrzędne skrajnie lewego szczytu [...]". Trzeba jednak pamiętać, że indeks to nie to samo co wartość zmiennej, o czym zdarza się zapominać w pośpiechu. Dlatego też dałem w nazwie "indeks", żeby czasem się nie pomylić. Warto poświęcić kilka liter więcej, żeby uniknąć jakiejś pomyłki 😅
![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 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:
(układ kartezjański od lewej do prawej)
D(-2,2), A(1,3), B(3,4), C(2,1)
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]). 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.](/Arkusze/2018/maj/2.1.png)