Zadanie teoretyczne typu „ułóż algorytm”

Poniższe zadanie pochodzi z części I 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 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:

RNoXMtNpunEdR
Ź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 , 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]).

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
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Polecenie 2

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

ROy2cB1CBdroQ1
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Ź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 .

RJEqPbq8N7EhO
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
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
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Polecenie 3

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

R1FoYK0RWfbZb1
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Ź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 .

R1PDTa4VigW6J
Wymyśl pytanie na kartkówkę związane z tematem materiału.