{"id":"informatyka-2016-maj-matura-rozszerzona/zad/2.1","paper_id":"informatyka-2016-maj-matura-rozszerzona","number":"2.1","points":2,"ptype":"closed","subject":"informatyka","category":"matura","year":2016,"month":"maj","level":"rozszerzona","text":"Zadanie 2.1. (0-2)\nDana jest liczba n = 6 oraz tablica A = [4,6,3,5,2,1]. Podaj kolejność elementów w tablicy A\npo wykonaniu funkcji przestaw(A).\nMiejsce na obliczenia.\nOdp. A =\nMIN_1R","answer":"A","answer_text":"Zadanie 2.1. (0-2)\nIII. Rozwiązywanie problemów i\npodejmowanie decyzji […], z zastosowaniem\npodejścia algorytmicznego.\n5. Rozwiązywanie problemów i podejmowanie\ndecyzji […], stosowanie podejścia algorytmicznego.\nZdający:\n2) stosuje podejście algorytmiczne do rozwiązywania\nproblemu;\n7) opracowuje i przeprowadza wszystkie etapy\nprowadzące do otrzymania poprawnego rozwiązania\nproblemu: od sformułowania specyfikacji problemu\npo testowanie rozwiązania;\n11) opisuje podstawowe algorytmy i stosuje: […]\nb) algorytmy wyszukiwania i porządkowania\n(sortowania);\n17) Zdający ocenia zgodność algorytmu ze\nspecyfikacją problemu.\nSchemat punktowania\n2 p. - za poprawną odpowiedź.\n0 p. - za odpowiedź błędną albo brak odpowiedzi.\nPoprawna odpowiedź\nA=[3,2,1,5,6,4]\nUwaga: Nie przyznaje się 1 p.","solution":"## Poprawna odpowiedź\n\n**A = [3, 2, 1, 5, 6, 4]**\n\n## Sposób 1 - symulacja krok po kroku\n\n**Stan początkowy:** A = [4, 6, 3, 5, 2, 1], n = 6.\n- klucz ← A[1] = **4**\n- w ← 1\n\nFunkcja iteruje k od 2 do 6. Gdy A[k] < klucz (4), wykonuje zamień(A[w], A[k]) i inkrementuje w.\n\n| k | A[k] | A[k] < 4? | Akcja | w przed | Stan A po | w po |\n| 2 | 6 | NIE | - | 1 | [4,6,3,5,2,1] | 1 |\n| 3 | 3 | TAK | zamień(A[1], A[3]) | 1 | [**3**,6,**4**,5,2,1] | 2 |\n| 4 | 5 | NIE | - | 2 | [3,6,4,5,2,1] | 2 |\n| 5 | 2 | TAK | zamień(A[2], A[5]) | 2 | [3,**2**,4,5,**6**,1] | 3 |\n| 6 | 1 | TAK | zamień(A[3], A[6]) | 3 | [3,2,**1**,5,6,**4**] | 4 |\n\n**Stan końcowy: A = [3, 2, 1, 5, 6, 4]** ✓\n\n## Sposób 2 - weryfikacja warunku partycji\n\nKlucz to **4** (wartość początkowa A[1]). Po wykonaniu funkcji oczekujemy:\n- W lewej części wszystkie wartości **< 4**: w wyniku [3, 2, 1] (indeksy 1-3) - wszystkie < 4 ✓\n- W prawej części wartości **≥ 4**: [5, 6, 4] (indeksy 4-6) - wszystkie ≥ 4 ✓\n\nIndeks granicy `w` na końcu = 4 → pozycja pierwszego elementu prawej części.\n\nW lewej części znajdują się WSZYSTKIE 3 elementy z A mniejsze od 4 (czyli 3, 2, 1). Pozostałe (6, 5, oraz sam klucz 4) są w prawej części, ale w innej kolejności niż początkowo - bo zostały przesunięte przez kolejne `zamień`.\n\n## Sposób 3 - implementacja Python (do weryfikacji)\n\n```python\ndef przestaw(A):\nn = len(A)\nklucz = A[0] # A[1] przy indeksowaniu od 1 = A[0] w Pythonie\nw = 0\nfor k in range(1, n):\nif A[k] < klucz:\nA[w], A[k] = A[k], A[w]\nw += 1\nreturn A\n\nA = [4, 6, 3, 5, 2, 1]\nprint(przestaw(A)) # [3, 2, 1, 5, 6, 4]\n\n## Reference informatyczny - partycja Lomuto\n\n> Reference - Algorytm partycji (Lomuto):\n> - Algorytm `przestaw` to **wariant partycji Lomuto** używanej w quicksort.\n> - Idea: indeks `w` wskazuje pierwszą pozycję w \"prawej\" części. Wszystko PRZED `w` to elementy mniejsze od klucza.\n> - **Klasyczna wersja Lomuto** używa ostatniego elementu jako pivot; tutaj klucz to pierwszy element, więc partycja nie kończy się umieszczeniem klucza na właściwej pozycji.\n> - **Złożoność**: O(n) - jedno przejście przez tablicę.\n> - **Niestabilność**: elementy równe i większe od klucza mogą zmienić kolejność (np. tu 6 i 5 wymieszały się z kluczem 4).\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 2.1, max 2 pkt):\n> - **2 pkt** - poprawna odpowiedź A = [3, 2, 1, 5, 6, 4]\n> - **0 pkt** - odpowiedź błędna albo brak\n>\n> **Uwaga: NIE PRZYZNAJE SIĘ 1 punktu** - odpowiedź musi być w pełni poprawna.\n\n## Typowe pułapki\n\n- **Mylenie kierunku porównania** - `A[k] < klucz` (ostro mniejszy, nie ≤). Element równy kluczowi trafia do prawej części.\n- **Inkrementacja `w` przy braku zamiany** - `w` rośnie TYLKO po wykonaniu zamiany.\n- **Inicjalizacja w = 0 lub w = 2** - poprawne to **w = 1** (start od miejsca klucza A[1]).\n- **Iteracja od k = 1** zamiast k = 2 - wtedy klucz zamieniłby się ze sobą.\n- **Pomyłka z indeksowaniem od 0** w Pythonie/C++ vs od 1 w pseudokodzie CKE.\n- **Pomyłka w stanie tablicy** po zamianach - łatwo pomylić, który element gdzie powędrował. Najlepiej rysować tablicę po każdej iteracji.\n\n## Złożoność obliczeniowa\n\n- Pętla iteruje od k = 2 do n: **O(n)** iteracji.\n- W każdej iteracji stały koszt: porównanie, ewentualna zamiana (3 przypisania), inkrementacja.\n- **Łączna złożoność: O(n)** czas, **O(1)** pamięć dodatkowa (in-place).","image":"img/informatyka-2016-maj-matura-rozszerzona/zad-2.1.webp","solution_image":null,"topics":null,"page_from":4,"source":"ocr","answer_source":"ocr","answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2016 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 2.1. (0-2)
Dana jest liczba n = 6 oraz tablica A = [4,6,3,5,2,1]. Podaj kolejność elementów w tablicy A
po wykonaniu funkcji przestaw(A).
Miejsce na obliczenia.
Odp. A =
MIN_1R

","answer_text_html":"

Zadanie 2.1. (0-2)
III. Rozwiązywanie problemów i
podejmowanie decyzji […], z zastosowaniem
podejścia algorytmicznego.

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

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

\n
  1. stosuje podejście algorytmiczne do rozwiązywania
\n

problemu;

\n
  1. opracowuje i przeprowadza wszystkie etapy
\n

prowadzące do otrzymania poprawnego rozwiązania
problemu: od sformułowania specyfikacji problemu
po testowanie rozwiązania;

\n
  1. opisuje podstawowe algorytmy i stosuje: […]
\n

b) algorytmy wyszukiwania i porządkowania
(sortowania);

\n
  1. Zdający ocenia zgodność algorytmu ze
\n

specyfikacją problemu.
Schemat punktowania
2 p. - za poprawną odpowiedź.
0 p. - za odpowiedź błędną albo brak odpowiedzi.
Poprawna odpowiedź
A=[3,2,1,5,6,4]
Uwaga: Nie przyznaje się 1 p.

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

Poprawna odpowiedź

\n

A = [3, 2, 1, 5, 6, 4]

\n

Sposób 1 - symulacja krok po kroku

\n

Stan początkowy: A = [4, 6, 3, 5, 2, 1], n = 6.

\n\n

Funkcja iteruje k od 2 do 6. Gdy A[k] < klucz (4), wykonuje zamień(A[w], A[k]) i inkrementuje w.

\n

| k | A[k] | A[k] < 4? | Akcja | w przed | Stan A po | w po |
| 2 | 6 | NIE | - | 1 | [4,6,3,5,2,1] | 1 |
| 3 | 3 | TAK | zamień(A[1], A[3]) | 1 | [3,6,4,5,2,1] | 2 |
| 4 | 5 | NIE | - | 2 | [3,6,4,5,2,1] | 2 |
| 5 | 2 | TAK | zamień(A[2], A[5]) | 2 | [3,2,4,5,6,1] | 3 |
| 6 | 1 | TAK | zamień(A[3], A[6]) | 3 | [3,2,1,5,6,4] | 4 |

\n

Stan końcowy: A = [3, 2, 1, 5, 6, 4] ✓

\n

Sposób 2 - weryfikacja warunku partycji

\n

Klucz to 4 (wartość początkowa A[1]). Po wykonaniu funkcji oczekujemy:

\n\n

Indeks granicy w na końcu = 4 → pozycja pierwszego elementu prawej części.

\n

W lewej części znajdują się WSZYSTKIE 3 elementy z A mniejsze od 4 (czyli 3, 2, 1). Pozostałe (6, 5, oraz sam klucz 4) są w prawej części, ale w innej kolejności niż początkowo - bo zostały przesunięte przez kolejne zamień.

\n

Sposób 3 - implementacja Python (do weryfikacji)

\n

```python
def przestaw(A):
n = len(A)
klucz = A[0] # A[1] przy indeksowaniu od 1 = A[0] w Pythonie
w = 0
for k in range(1, n):
if A[k] < klucz:
A[w], A[k] = A[k], A[w]
w += 1
return A

\n

A = [4, 6, 3, 5, 2, 1]
print(przestaw(A)) # [3, 2, 1, 5, 6, 4]

\n

Reference informatyczny - partycja Lomuto

\n
Reference - Algorytm partycji (Lomuto):
- Algorytm przestaw to wariant partycji Lomuto używanej w quicksort.
- Idea: indeks w wskazuje pierwszą pozycję w "prawej" części. Wszystko PRZED w to elementy mniejsze od klucza.
- Klasyczna wersja Lomuto używa ostatniego elementu jako pivot; tutaj klucz to pierwszy element, więc partycja nie kończy się umieszczeniem klucza na właściwej pozycji.
- Złożoność: O(n) - jedno przejście przez tablicę.
- Niestabilność: elementy równe i większe od klucza mogą zmienić kolejność (np. tu 6 i 5 wymieszały się z kluczem 4).
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 2.1, max 2 pkt):
- 2 pkt - poprawna odpowiedź A = [3, 2, 1, 5, 6, 4]
- 0 pkt - odpowiedź błędna albo brak

Uwaga: NIE PRZYZNAJE SIĘ 1 punktu - odpowiedź musi być w pełni poprawna.
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}