{"id":"informatyka-2018-maj-matura-rozszerzona/zad/2.2","paper_id":"informatyka-2018-maj-matura-rozszerzona","number":"2.2","points":4,"ptype":"open","subject":"informatyka","category":"matura","year":2018,"month":"maj","level":"rozszerzona","text":"Zadanie 2.2. (0-4)\nNapisz algorytm (w pseudokodzie lub wybranym języku programowania), który przestawi\nelementy tablic X i Y tak, aby szczyty były uporządkowane w kolejności, w której obserwator\nwidzi je od lewej do prawej strony. Aby otrzymać maksymalną ocenę, Twój algorytm powinien\nmieć złożoność czasową kwadratową lub mniejszą.\nAlgorytm może używać wyłącznie instrukcji sterujących, operatorów arytmetycznych,\noperatorów logicznych, porównań i przypisań do zmiennych. Zabronione jest używanie funkcji\nbibliotecznych dostępnych w językach programowania.\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[1 n], Y[1 n] - tablice zawierające współrzędne danych szczytów, uporządkowanych\nw kolejności, w której obserwator widzi je od lewej do prawej strony.\nAlgorytm\nMIN_1R","answer":null,"answer_text":"Zadanie 2.2. (0-4)\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- algorytmy sortowania ciągu liczb:\nbąbelkowy, przez wybór, przez wstawianie\nliniowe lub binarne, przez scalanie, szybki,\nkubełkowy.\nSchemat punktowania\n4 p. - za poprawny algorytm, w tym:\n1 p. - za poprawną konstrukcję zewnętrznej pętli algorytmu sortowania,\n1 p. - za poprawną konstrukcję wewnętrznej pętli algorytmu sortowania,\n1 p. - za poprawne porównanie elementów,\n1 p. - za poprawną zamianę elementów uwzględniającą zarówno X, jak i Y.\nUwaga: za prawidłowe rozwiązanie o złożoności większej niż kwadratowa - maksymalnie 3\npunkty,\n0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.\nUwaga: za każde inne niż przedstawione niżej, ale całkowicie poprawne rozwiązanie\nprzyznajemy maksymalną liczbę punktów.\nPrzykładowe rozwiązania\nPrzykładowe rozwiązanie 1. (sortowanie bąbelkowe):\npowtarzaj n-1 razy:\ndla i = 1, 2, , n-1\njeżeli X[i+1]/Y[i+1] < X[i]/Y[i]\nt = X[i]\nX[i] = X[i+1]\nX[i+1] = t\nt = Y[i]\nY[i] = Y[i+1]\nY[i+1] = t\nPrzykładowe rozwiązanie 2. (sortowanie przez wybór):\ndla i = 1, 2, , n-1:\nm = i\ndla j = i+1, i+2, , n\njeżeli X[j]/Y[j] < X[m]/Y[m]\nm = j\nt = X[i]\nX[i] = X[m]\nX[m] = t\nt = Y[i]\nY[i] = Y[m]\nY[m] = t\nPrzykładowe rozwiązanie 3. (sortowanie przez wstawianie):\ndla i = 2, 3, , n:\nj = i\ndopóki j>1 oraz X[j]/Y[j] 1 oraz X[i]/Y[i] < X[i-1]/Y[i-1] wykonuj:\nzamień X[i] z X[i-1]\nzamień Y[i] z Y[i-1]\ni ← i - 1\n\n**Pascal:**\n```pascal\nprocedure InsertionSort(var X, Y: array of LongInt; n: Integer);\nvar k, i, tx, ty: Integer;\nbegin\nfor k := 1 to n - 1 do begin\ni := k;\nwhile (i > 0) and (X[i] * Y[i-1] < X[i-1] * Y[i]) do begin\ntx := X[i]; X[i] := X[i-1]; X[i-1] := tx;\nty := Y[i]; Y[i] := Y[i-1]; Y[i-1] := ty;\ni := i - 1;\nend;\nend;\nend;\n\n## Reference informatyczny - sortowanie\n\n> Reference - Sortowanie bąbelkowe (bubble sort):\n> - Powtarza n-1 razy: porównuje sąsiadów i zamienia jeśli nieuporządkowani.\n> - **Złożoność**: O(n²) najgorszy/średni, O(n) najlepszy (z flagą \"swap\").\n> - **Pamięć**: O(1) dodatkowa (in-place).\n> - **Stabilność**: stabilny (nie zamienia równych).\n>\n> Reference - Sortowanie przez wybieranie (selection sort):\n> - W każdym przejściu wybiera minimum i zamienia z pozycją k.\n> - **Złożoność**: O(n²) zawsze.\n> - **Niestabilny** (zamiana minimum z pozycją k niszczy kolejność).\n>\n> Reference - Sortowanie przez wstawianie (insertion sort):\n> - Bierze kolejny element i wstawia go w odpowiednie miejsce wśród posortowanych.\n> - **Złożoność**: O(n²) najgorszy, O(n) najlepszy (dane już posortowane).\n> - **Stabilny**, **in-place**, **adaptywny**.\n>\n> Reference - Sortowanie z funkcją porównawczą (klucz):\n> - Zamiast `a[i] < a[j]` używamy `klucz(a[i]) < klucz(a[j])`.\n> - Tu: `klucz(i) = X[i] / Y[i]`.\n> - Synchronicznie zamieniamy WSZYSTKIE elementy powiązane z indeksem (tu X i Y).\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 2.2, max 4 pkt):\n> - **1 pkt** - poprawna konstrukcja zewnętrznej pętli sortowania\n> - **1 pkt** - poprawna konstrukcja wewnętrznej pętli\n> - **1 pkt** - poprawne porównanie elementów (iloraz X/Y)\n> - **1 pkt** - poprawna zamiana elementów uwzględniająca **OBA** X i Y\n>\n> **Uwaga: za algorytm o złożoności WIĘKSZEJ niż kwadratowa - maksymalnie 3 pkt.**\n\n## Typowe pułapki\n\n- **Zamiana tylko X bez Y** - strata 1 pkt. Synchronizacja par jest KRYTYCZNA.\n- **Zamiana tylko Y bez X** - j.w.\n- **Sortowanie po samym X** zamiast X/Y - błędna kolejność (np. D(-2,2) zaszedłby przed A(1,3), ale gdyby było C(2,1) i A(1,3), to A miało większe X niż źle).\n- **Złożoność O(n³)** - przy sortowaniu z dodatkową pętlą wewnątrz porównań. Strata 1 pkt.\n- **Użycie funkcji bibliotecznej `sorted()` / `qsort`** - **zabronione przez treść**.\n- **Off-by-one** w pętlach - pamiętaj o indeksowaniu od 1 w pseudokodzie.\n- **Niepoprawne zamiana** - bez zmiennej tymczasowej `t` można nadpisać wartości.\n\n## Złożoność obliczeniowa\n\n- **Czas**: O(n²) - dwie zagnieżdżone pętle do n.\n- **Pamięć**: O(1) dodatkowa (in-place, tylko zmienna `t` lub `min_idx`).\n- **Operacje porównania**: do n(n-1)/2.\n- **Operacje zamiany**: do n(n-1)/2 w bubble; do n-1 w selection.\n\nDla maksymalnej oceny (4 pkt) wystarcza kwadratowa - to jest mile widziane przez klucz CKE.","image":"img/informatyka-2018-maj-matura-rozszerzona/zad-2.2.webp","solution_image":null,"topics":null,"page_from":6,"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.2. (0-4)
Napisz algorytm (w pseudokodzie lub wybranym języku programowania), 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. Aby otrzymać maksymalną ocenę, Twój 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:
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[1 n], Y[1 n] - 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.
Algorytm
MIN_1R

","answer_text_html":"

Zadanie 2.2. (0-4)
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

bąbelkowy, przez wybór, przez wstawianie
liniowe lub binarne, przez scalanie, szybki,
kubełkowy.
Schemat punktowania
4 p. - za poprawny algorytm, w tym:
1 p. - za poprawną konstrukcję zewnętrznej pętli algorytmu sortowania,
1 p. - za poprawną konstrukcję wewnętrznej pętli algorytmu sortowania,
1 p. - za poprawne porównanie elementów,
1 p. - za poprawną zamianę elementów uwzględniającą zarówno X, jak i Y.
Uwaga: za prawidłowe rozwiązanie o złożoności większej niż kwadratowa - maksymalnie 3
punkty,
0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.
Uwaga: za każde inne niż przedstawione niżej, ale całkowicie poprawne rozwiązanie
przyznajemy maksymalną liczbę punktów.
Przykładowe rozwiązania
Przykładowe rozwiązanie 1. (sortowanie bąbelkowe):
powtarzaj n-1 razy:
dla i = 1, 2, , n-1
jeżeli X[i+1]/Y[i+1] < X[i]/Y[i]
t = X[i]
X[i] = X[i+1]
X[i+1] = t
t = Y[i]
Y[i] = Y[i+1]
Y[i+1] = t
Przykładowe rozwiązanie 2. (sortowanie przez wybór):
dla i = 1, 2, , n-1:
m = i
dla j = i+1, i+2, , n
jeżeli X[j]/Y[j] < X[m]/Y[m]
m = j
t = X[i]
X[i] = X[m]
X[m] = t
t = Y[i]
Y[i] = Y[m]
Y[m] = t
Przykładowe rozwiązanie 3. (sortowanie przez wstawianie):
dla i = 2, 3, , n:
j = i
dopóki j>1 oraz X[j]/Y[j]<X[j-1]/Y[j-1]:
t = X[j]
X[j] = X[j-1]
X[j-1] = t
t = Y[j]
Y[j] = Y[j-1]
Y[j-1] = t
j = j-1

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

Poprawna odpowiedź

\n

Algorytm - sortowanie bąbelkowe (bubble sort) wg ilorazu X[i]/Y[i]:

\n

powtarzaj n-1 razy:
dla i = 1, 2, , n-1 wykonuj:
jeżeli X[i+1]/Y[i+1] < X[i]/Y[i]:
t ← X[i]
X[i] ← X[i+1]
X[i+1] ← t
t ← Y[i]
Y[i] ← Y[i+1]
Y[i+1] ← t

\n

Sposób 1 - sortowanie bąbelkowe

\n

Idea: w każdym przejściu "bąbel" (największy nieuporządkowany element) wędruje na koniec. Powtarzając n-1 razy, mamy gwarancję pełnego posortowania.

\n

Klucz porównania: X[i]/Y[i] (kąt nachylenia od obserwatora).

\n

Zamiana par (X[i], Y[i]) ↔ (X[i+1], Y[i+1]) - zamieniamy OBIE tablice synchronicznie.

\n

Sposób 2 - implementacja Python

\n

```python
def sortuj_szczyty(X, Y):
n = len(X)
for k in range(n - 1):
for i in range(n - 1 - k): # optymalizacja: ostatnie k jest posortowane
if X[i+1] / Y[i+1] < X[i] / Y[i]:
X[i], X[i+1] = X[i+1], X[i]
Y[i], Y[i+1] = Y[i+1], Y[i]
return X, Y

\n

X = [3, -2, 2, 1]
Y = [4, 2, 1, 3]
print(sortuj_szczyty(X, Y))

\n

Posortowane: D(-2,2), A(1,3), B(3,4), C(2,1)

\n

X = [-2, 1, 3, 2], Y = [2, 3, 4, 1]

\n

Sposób 3 - sortowanie przez wybieranie (selection sort)

\n

Alternatywa - w każdym przejściu wybieramy minimum z reszty i wymieniamy z pozycją k:

\n

dla k = 1, 2, , n-1 wykonuj:
min_idx ← k
dla i = k+1, , n wykonuj:
jeżeli X[i]/Y[i] < X[min_idx]/Y[min_idx]:
min_idx ← i
zamień X[k] z X[min_idx]
zamień Y[k] z Y[min_idx]

\n

C++ (selection sort):
```cpp
void sortuj(int X[], int Y[], int n) {
for (int k = 0; k < n - 1; k++) {
int min_idx = k;
for (int i = k + 1; i < n; i++) {
// X[i]/Y[i] < X[min_idx]/Y[min_idx]
if ((long long)X[i] * Y[min_idx] < (long long)X[min_idx] * Y[i]) {
min_idx = i;
}
}
if (min_idx != k) {
int tx = X[k]; X[k] = X[min_idx]; X[min_idx] = tx;
int ty = Y[k]; Y[k] = Y[min_idx]; Y[min_idx] = ty;
}
}
}

\n

Sposób 4 - sortowanie przez wstawianie (insertion sort)

\n

dla k = 2, , n wykonuj:
i ← k
dopóki i > 1 oraz X[i]/Y[i] < X[i-1]/Y[i-1] wykonuj:
zamień X[i] z X[i-1]
zamień Y[i] z Y[i-1]
i ← i - 1

\n

Pascal:
```pascal
procedure InsertionSort(var X, Y: array of LongInt; n: Integer);
var k, i, tx, ty: Integer;
begin
for k := 1 to n - 1 do begin
i := k;
while (i > 0) and (X[i] * Y[i-1] < X[i-1] * Y[i]) do begin
tx := X[i]; X[i] := X[i-1]; X[i-1] := tx;
ty := Y[i]; Y[i] := Y[i-1]; Y[i-1] := ty;
i := i - 1;
end;
end;
end;

\n

Reference informatyczny - sortowanie

\n
Reference - Sortowanie bąbelkowe (bubble sort):
- Powtarza n-1 razy: porównuje sąsiadów i zamienia jeśli nieuporządkowani.
- Złożoność: O(n²) najgorszy/średni, O(n) najlepszy (z flagą "swap").
- Pamięć: O(1) dodatkowa (in-place).
- Stabilność: stabilny (nie zamienia równych).

Reference - Sortowanie przez wybieranie (selection sort):
- W każdym przejściu wybiera minimum i zamienia z pozycją k.
- Złożoność: O(n²) zawsze.
- Niestabilny (zamiana minimum z pozycją k niszczy kolejność).

Reference - Sortowanie przez wstawianie (insertion sort):
- Bierze kolejny element i wstawia go w odpowiednie miejsce wśród posortowanych.
- Złożoność: O(n²) najgorszy, O(n) najlepszy (dane już posortowane).
- Stabilny, in-place, adaptywny.

Reference - Sortowanie z funkcją porównawczą (klucz):
- Zamiast a[i] < a[j] używamy klucz(a[i]) < klucz(a[j]).
- Tu: klucz(i) = X[i] / Y[i].
- Synchronicznie zamieniamy WSZYSTKIE elementy powiązane z indeksem (tu X i Y).
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 2.2, max 4 pkt):
- 1 pkt - poprawna konstrukcja zewnętrznej pętli sortowania
- 1 pkt - poprawna konstrukcja wewnętrznej pętli
- 1 pkt - poprawne porównanie elementów (iloraz X/Y)
- 1 pkt - poprawna zamiana elementów uwzględniająca OBA X i Y

Uwaga: za algorytm o złożoności WIĘKSZEJ niż kwadratowa - maksymalnie 3 pkt.
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n\n

Dla maksymalnej oceny (4 pkt) wystarcza kwadratowa - to jest mile widziane przez klucz CKE.

"}]}