Prezentacja multimedialna
Zadanie teoretyczne typu „ułóż algorytm”
Poniższe zadanie pochodzi z części arkusza rozszerzonego egzaminu maturalnego z informatyki z maja 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 , tzn. druga współrzędna () każdego punktu jest dodatnia.
W punkcie stoi obserwator. Jeśli dwa szczyty i mają współrzędne oraz , to mówimy, że:
szczyt jest dla obserwatora widoczny na lewo od , jeśli ,
szczyt jest widoczny na lewo od , 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 rysunku:
W tym przykładzie, patrząc od lewej do prawej strony, obserwator widzi kolejno szczyt , szczyt , szczyt i szczyt .
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 problemu:
Dane:
n– liczba całkowita dodatniaX[0..n - 1]– tablica liczb całkowitychY[0..n - 1]– tablica liczb całkowitych dodatnichPara
(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 tablicachXiY
Porównaj swoje rozwiązanie z rozwiązaniem przedstawionym w prezentacji.
W wybranym języku programowania zaimplementuj algorytm z problemu .
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 dodatniaX[0..n - 1]– tablica liczb całkowitychY[0..n - 1]– tablica liczb całkowitych dodatnichPara
(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.
Porównaj swoje rozwiązanie z przedstawionym w prezentacji.
W wybranym języku programowania zaimplementuj algorytm z problemu .