{"id":"informatyka-2018-maj-matura-rozszerzona/zad/2.1","paper_id":"informatyka-2018-maj-matura-rozszerzona","number":"2.1","points":2,"ptype":"open","subject":"informatyka","category":"matura","year":2018,"month":"maj","level":"rozszerzona","text":"Zadanie 2.1. (0-2)\nNapisz algorytm (w pseudokodzie lub wybranym języku programowania), który znajdzie i poda\nwspółrzędne skrajnie lewego szczytu, tzn. widocznego dla obserwatora na lewo od wszystkich\npozostałych szczytów.\nSpecyfikacja:\nDane:\nn\n- liczba całkowita dodatnia\nX[1 n] - tablica liczb całkowitych\nY[1 n] - tablica liczb całkowitych dodatnich\nPara (X[i], Y[i]) to współrzędne jednego szczytu, i = 1, 2, …, n.\nŻadne dwa szczyty nie leżą w jednej linii z obserwatorem.\nWynik:\nx, y - współrzędne skrajnie lewego szczytu spośród tych opisanych w tablicach X i Y.\nAlgorytm\nWypełnia\negzaminator\nNr zadania\n2.1.\nMaks. liczba pkt.\n2\nUzyskana liczba pkt.\nMIN_1R","answer":null,"answer_text":"Zadanie 2.1. (0-2)\nWymagania ogólne\nWymagania szczegółowe\nIII. Rozwiązywanie problemów\ni podejmowanie decyzji […] z zastosowaniem\npodejścia algorytmicznego.\n5. Rozwiązywanie problemów\ni podejmowanie decyzji […], stosowanie\npodejścia algorytmicznego.\nZdający:\n1) analizuje, modeluje i rozwiązuje sytuacje\nproblemowe z różnych dziedzin;\n2) stosuje podejście algorytmiczne do\nrozwiązywania problemu;\n4) dobiera efektywny algorytm do\nrozwiązania sytuacji problemowej\ni zapisuje go w wybranej notacji;\n5) posługuje się podstawowymi technikami\nalgorytmicznymi;\n11) opisuje podstawowe algorytmy\ni stosuje:\nb) algorytmy wyszukiwania\ni porządkowania (sortowania), np.:\n- jednoczesne znajdowanie największego\ni najmniejszego elementu w zbiorze:\nalgorytm naiwny i optymalny,\n- algorytmy sortowania ciągu liczb:\nbąbelkowy, przez wybór, przez wstawianie\nliniowe lub binarne, przez scalanie, szybki,\nkubełkowy.\nSchemat punktowania\n2 p. - za poprawny algorytm, w tym:\n1 p. - za prawidłową inicjalizację oraz konstrukcję pętli,\n1 p. - za zastosowanie prawidłowego porównania oraz wyznaczenie współrzędnych\nskrajnie lewego szczytu,\nUwaga: za prawidłowe porównanie i wyznaczenie poprawnej najmniejszej wartości ilorazu\nwspółrzędnych oraz poprawnego indeksu - 1 punkt,\n0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.\nPrzykładowe rozwiązanie\nk ← 1\ndla i = 2, 3, , n wykonuj\njeżeli X[i]/Y[i] < X[k]/Y[k]\nk ← i\nx ←X[k], y←Y[k]","solution":"## Poprawna odpowiedź\n\n**Algorytm (pseudokod):**\n\nk ← 1\ndla i = 2, 3, , n wykonuj:\njeżeli X[i]/Y[i] < X[k]/Y[k]:\nk ← i\nx ← X[k]\ny ← Y[k]\n\nLub równoważnie (bez dzielenia, uważając na znak Y[i] > 0):\nk ← 1\ndla i = 2, 3, , n wykonuj:\njeżeli X[i] * Y[k] < X[k] * Y[i]:\nk ← i\nx ← X[k]\ny ← Y[k]\n\n## Sposób 1 - analiza problemu i klasyczny algorytm znajdowania minimum\n\n**Idea:** szczyt jest \"widoczny na lewo\" gdy ma najmniejszą wartość ilorazu `X[i]/Y[i]`. Szukamy więc **MINIMUM** spośród wszystkich ilorazów `X[i]/Y[i]`.\n\nAlgorytm to standardowe **wyszukiwanie minimum** w tablicy z modyfikacją w warunku porównania:\n1. Załóżmy, że minimum jest na pozycji 1 (k = 1).\n2. Iterujemy i od 2 do n.\n3. Jeśli iloraz pozycji i jest mniejszy niż na pozycji k → aktualizujemy k = i.\n4. Po pętli zwracamy współrzędne (X[k], Y[k]).\n\n## Sposób 2 - implementacja Python\n\n```python\ndef skrajnie_lewy(X, Y):\nn = len(X)\nk = 0 # indeks od 0 w Python\nfor i in range(1, n):\nif X[i] / Y[i] < X[k] / Y[k]:\nk = i\nreturn X[k], Y[k]\n\n# Przykład: D(-2,2), A(1,3), B(3,4), C(2,1)\nX = [-2, 1, 3, 2]\nY = [2, 3, 4, 1]\nprint(skrajnie_lewy(X, Y)) # (-2, 2) - szczyt D\n\n**Weryfikacja na przykładzie:**\n- D: -2/2 = **-1.0** (najmniejszy)\n- A: 1/3 ≈ 0.333\n- B: 3/4 = 0.75\n- C: 2/1 = 2.0\n\nMinimum = -1.0 → D ✓\n\n## Sposób 3 - C++ / Pascal\n\n**C++ (bezpieczna wersja bez dzielenia float):**\n```cpp\nvoid skrajnieLewy(int X[], int Y[], int n, int& x, int& y) {\nint k = 0;\nfor (int i = 1; i < n; i++) {\n// X[i]/Y[i] < X[k]/Y[k] <=> X[i]*Y[k] < X[k]*Y[i] (Y[i], Y[k] > 0)\nif ((long long)X[i] * Y[k] < (long long)X[k] * Y[i]) {\nk = i;\n}\n}\nx = X[k]; y = Y[k];\n}\n\n**Pascal:**\n```pascal\nprocedure SkrajnieLewy(X, Y: array of LongInt; n: Integer; var x, y: LongInt);\nvar i, k: Integer;\nbegin\nk := 0;\nfor i := 1 to n - 1 do begin\nif X[i] * Y[k] < X[k] * Y[i] then k := i;\nend;\nx := X[k]; y := Y[k];\nend;\n\n## Reference informatyczny - wyszukiwanie minimum\n\n> Reference - Wyszukiwanie minimum w tablicy:\n> - Klasyczny algorytm O(n) z jedną zmienną przechowującą bieżące minimum.\n> - Inicjalizacja: minimum = pierwszy element. Iteracja: porównanie z pozostałymi.\n> - Tutaj funkcja porównująca to `X[i]/Y[i]`, czyli **funkcja klucza** (analogicznie do `key=` w Python `min()`).\n>\n> Reference - Porównanie ilorazów bez dzielenia:\n> - `a/b < c/d` ⟺ `a·d < c·b` (gdy b, d > 0).\n> - Zaleta: brak błędów zaokrąglenia floating-point.\n> - Wada: ryzyko przepełnienia int (gdy `a·d` duże). W zadaniu Y > 0 zawsze, więc bezpiecznie.\n>\n> Reference - Interpretacja geometryczna:\n> - Iloraz X/Y to **kąt nachylenia** linii od obserwatora (0,0) do punktu (X, Y).\n> - Im mniejszy iloraz (ujemny dla X<0), tym bardziej w lewo.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 2.1, max 2 pkt):\n> - **1 pkt** za prawidłową inicjalizację (k = 1) ORAZ poprawną pętlę (dla i = 2, , n)\n> - **1 pkt** za prawidłowe porównanie (X[i]/Y[i] < X[k]/Y[k]) ORAZ wyznaczenie wyniku (x, y)\n> - **0 pkt** - odpowiedź błędna lub brak\n\n## Typowe pułapki\n\n- **Inicjalizacja k = 0** - w pseudokodzie CKE indeks startowy to 1, nie 0.\n- **Wyszukiwanie maksimum** zamiast minimum - szczyt skrajnie LEWY to NAJMNIEJSZY iloraz X/Y.\n- **Porównanie bezpośrednie X[i] < X[k]** - zła interpretacja \"lewo\" jako najmniejsze X. Trzeba uwzględnić Y.\n- **Zwracanie indeksu** zamiast współrzędnych - pytanie pyta o (x, y), nie o k.\n- **Float vs integer division** - w Pascal `/` zwraca Real, w C++ trzeba uważać przy int. Bezpieczniej mnożyć skrośnie.\n- **Pominięcie warunku Y > 0** - w zadaniu Y jest dodatnie (z definicji), więc krzyżowe mnożenie bezpieczne.\n\n## Złożoność obliczeniowa\n\n- Jedno przejście przez tablicę: **O(n)** porównań.\n- Pamięć: **O(1)** dodatkowa (tylko zmienna k).\n- **Optymalne** - nie da się znaleźć minimum w mniej niż O(n) (każdy element trzeba sprawdzić).","image":"img/informatyka-2018-maj-matura-rozszerzona/zad-2.1.webp","solution_image":null,"topics":null,"page_from":5,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2018 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 2.1. (0-2)
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

\n\n

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
Wypełnia
egzaminator
Nr zadania
2.1.
Maks. liczba pkt.
2
Uzyskana liczba pkt.
MIN_1R

","answer_text_html":"

Zadanie 2.1. (0-2)
Wymagania ogólne
Wymagania szczegółowe
III. Rozwiązywanie problemów
i podejmowanie decyzji […] z zastosowaniem
podejścia algorytmicznego.

\n
  1. Rozwiązywanie problemów
\n

i podejmowanie decyzji […], stosowanie
podejścia algorytmicznego.
Zdający:

\n
  1. analizuje, modeluje i rozwiązuje sytuacje
\n

problemowe z różnych dziedzin;

\n
  1. stosuje podejście algorytmiczne do
\n

rozwiązywania problemu;

\n
  1. dobiera efektywny algorytm do
\n

rozwiązania sytuacji problemowej
i zapisuje go w wybranej notacji;

\n
  1. posługuje się podstawowymi technikami
\n

algorytmicznymi;

\n
  1. opisuje podstawowe algorytmy
\n

i stosuje:
b) algorytmy wyszukiwania
i porządkowania (sortowania), np.:

\n\n

i najmniejszego elementu w zbiorze:
algorytm naiwny i optymalny,

\n\n

bąbelkowy, przez wybór, przez wstawianie
liniowe lub binarne, przez scalanie, szybki,
kubełkowy.
Schemat punktowania
2 p. - za poprawny algorytm, w tym:
1 p. - za prawidłową inicjalizację oraz konstrukcję pętli,
1 p. - 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 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.
Przykładowe rozwiązanie
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]

","solutions":[{"source":"maturazai","label":"maturazai.pl (AI)","kind":"text","html":"

Poprawna odpowiedź

\n

Algorytm (pseudokod):

\n

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]

\n

Lub równoważnie (bez dzielenia, uważając na znak Y[i] > 0):
k ← 1
dla i = 2, 3, , n wykonuj:
jeżeli X[i] * Y[k] < X[k] * Y[i]:
k ← i
x ← X[k]
y ← Y[k]

\n

Sposób 1 - analiza problemu i klasyczny algorytm znajdowania minimum

\n

Idea: szczyt jest "widoczny na lewo" gdy ma najmniejszą wartość ilorazu X[i]/Y[i]. Szukamy więc MINIMUM spośród wszystkich ilorazów X[i]/Y[i].

\n

Algorytm to standardowe wyszukiwanie minimum w tablicy z modyfikacją w warunku porównania:

\n
  1. Załóżmy, że minimum jest na pozycji 1 (k = 1).
  2. Iterujemy i od 2 do n.
  3. Jeśli iloraz pozycji i jest mniejszy niż na pozycji k → aktualizujemy k = i.
  4. Po pętli zwracamy współrzędne (X[k], Y[k]).
\n

Sposób 2 - implementacja Python

\n

```python
def skrajnie_lewy(X, Y):
n = len(X)
k = 0 # indeks od 0 w Python
for i in range(1, n):
if X[i] / Y[i] < X[k] / Y[k]:
k = i
return X[k], Y[k]

\n

Przykład: D(-2,2), A(1,3), B(3,4), C(2,1)

\n

X = [-2, 1, 3, 2]
Y = [2, 3, 4, 1]
print(skrajnie_lewy(X, Y)) # (-2, 2) - szczyt D

\n

Weryfikacja na przykładzie:

\n\n

Minimum = -1.0 → D ✓

\n

Sposób 3 - C++ / Pascal

\n

C++ (bezpieczna wersja bez dzielenia float):
```cpp
void skrajnieLewy(int X[], int Y[], int n, int& x, int& y) {
int k = 0;
for (int i = 1; i < n; i++) {
// X[i]/Y[i] < X[k]/Y[k] <=> X[i]Y[k] < X[k]Y[i] (Y[i], Y[k] > 0)
if ((long long)X[i] * Y[k] < (long long)X[k] * Y[i]) {
k = i;
}
}
x = X[k]; y = Y[k];
}

\n

Pascal:
```pascal
procedure SkrajnieLewy(X, Y: array of LongInt; n: Integer; var x, y: LongInt);
var i, k: Integer;
begin
k := 0;
for i := 1 to n - 1 do begin
if X[i] * Y[k] < X[k] * Y[i] then k := i;
end;
x := X[k]; y := Y[k];
end;

\n

Reference informatyczny - wyszukiwanie minimum

\n
Reference - Wyszukiwanie minimum w tablicy:
- Klasyczny algorytm O(n) z jedną zmienną przechowującą bieżące minimum.
- Inicjalizacja: minimum = pierwszy element. Iteracja: porównanie z pozostałymi.
- Tutaj funkcja porównująca to X[i]/Y[i], czyli funkcja klucza (analogicznie do key= w Python min()).

Reference - Porównanie ilorazów bez dzielenia:
- a/b < c/d ⟺ a·d < c·b (gdy b, d > 0).
- Zaleta: brak błędów zaokrąglenia floating-point.
- Wada: ryzyko przepełnienia int (gdy a·d duże). W zadaniu Y > 0 zawsze, więc bezpiecznie.

Reference - Interpretacja geometryczna:
- Iloraz X/Y to kąt nachylenia linii od obserwatora (0,0) do punktu (X, Y).
- Im mniejszy iloraz (ujemny dla X<0), tym bardziej w lewo.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 2.1, max 2 pkt):
- 1 pkt za prawidłową inicjalizację (k = 1) ORAZ poprawną pętlę (dla i = 2, , n)
- 1 pkt za prawidłowe porównanie (X[i]/Y[i] < X[k]/Y[k]) ORAZ wyznaczenie wyniku (x, y)
- 0 pkt - odpowiedź błędna lub brak
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}