{"id":"informatyka-2016-maj-matura-rozszerzona/zad/2.2","paper_id":"informatyka-2016-maj-matura-rozszerzona","number":"2.2","points":1,"ptype":"open","subject":"informatyka","category":"matura","year":2016,"month":"maj","level":"rozszerzona","text":"Zadanie 2.2. (0-1)\nPodaj przykład siedmioelementowej tablicy A, dla której funkcja przestaw(A) dokładnie\n5 razy wykona zamień.\nMiejsce na obliczenia.\nOdp. A =","answer":null,"answer_text":"Zadanie 2.2. (0-1)\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\n1 p. - za poprawną odpowiedź.\n0 p. - za podanie odpowiedzi z tablicą większą niż 7-elementową lub odpowiedź błędną albo brak\nodpowiedzi.\nPrzykładowa odpowiedź\n[8,1,2,3,4,5,9]\nUwaga\nPoprawną odpowiedzią jest podanie dowolnej siedmioelementowej tablicy, w której dokładnie pięć\nelementów z pozycji 2…7 jest mniejszych od elementu pierwszego.","solution":"## Poprawna odpowiedź\n\n**A = [8, 1, 2, 3, 4, 5, 9]**\n\n## Sposób 1 - analiza warunku zamiany\n\n**Kiedy `zamień` jest wykonywany?** Tylko gdy `A[k] < klucz`, gdzie `klucz = A[1]`.\n\nDla tablicy 7-elementowej iterujemy k od 2 do 7 (6 razy). Aby `zamień` wykonał się **dokładnie 5 razy**, dokładnie 5 z elementów A[2 7] musi być **mniejszych od A[1]**.\n\n**Konstrukcja przykładu:**\n1. Wybierz dużą wartość jako klucz: np. **A[1] = 8**.\n2. Wstaw 5 wartości MNIEJSZYCH od 8 na pozycjach 2-7: np. 1, 2, 3, 4, 5.\n3. Wstaw 1 wartość WIĘKSZĄ lub równą 8 na jednej z pozycji 2-7: np. **A[7] = 9**.\n\n**A = [8, 1, 2, 3, 4, 5, 9]** → 5 elementów (1, 2, 3, 4, 5) < klucza 8; jeden (9) ≥ 8.\n\n## Sposób 2 - weryfikacja symulacją\n\n**Stan:** A = [8, 1, 2, 3, 4, 5, 9], klucz = 8, w = 1.\n\n| k | A[k] | < 8? | zamień(A[w], A[k]) | A po | w po |\n| 2 | 1 | TAK | zamień(A[1], A[2]) | [1,8,2,3,4,5,9] | 2 |\n| 3 | 2 | TAK | zamień(A[2], A[3]) | [1,2,8,3,4,5,9] | 3 |\n| 4 | 3 | TAK | zamień(A[3], A[4]) | [1,2,3,8,4,5,9] | 4 |\n| 5 | 4 | TAK | zamień(A[4], A[5]) | [1,2,3,4,8,5,9] | 5 |\n| 6 | 5 | TAK | zamień(A[5], A[6]) | [1,2,3,4,5,8,9] | 6 |\n| 7 | 9 | NIE | - | [1,2,3,4,5,8,9] | 6 |\n\n**Liczba zamian: 5** ✓\n\n## Sposób 3 - inne poprawne przykłady\n\nKażda tablica `[K, a, b, c, d, e, X]` gdzie:\n- `K` to klucz (dowolna wartość),\n- `a, b, c, d, e` to 5 wartości mniejszych od K (mogą być takie same),\n- `X` to 1 wartość ≥ K,\n- pozycje 5 mniejszych i 1 większego mogą być w dowolnej kolejności wśród A[2 7].\n\n**Inne poprawne odpowiedzi:**\n- A = [10, 1, 1, 1, 1, 1, 10]\n- A = [5, 3, 2, 9, 1, 4, 0] → wartości < 5: 3, 2, 1, 4, 0 (5 sztuk); ≥ 5: 9 (jeden)\n- A = [100, 99, 50, 1, 200, 25, 30]\n\n```python\ndef policz_zamiany(A):\nklucz = A[0]\nzamiany = 0\nfor k in range(1, len(A)):\nif A[k] < klucz:\nzamiany += 1\nreturn zamiany\n\nprint(policz_zamiany([8, 1, 2, 3, 4, 5, 9])) # 5\nprint(policz_zamiany([10, 1, 1, 1, 1, 1, 10])) # 5\n\n## Reference informatyczny - liczba operacji w algorytmach partycji\n\n> Reference - Analiza operacji partycji:\n> - Liczba wywołań `zamień` w `przestaw` = liczba elementów A[2 n] mniejszych od A[1].\n> - **Maksimum**: gdy wszystkie n-1 elementów są < klucza → n-1 zamian.\n> - **Minimum**: gdy żaden element nie jest < klucza → 0 zamian (tablica posortowana niemalejąco, klucz na pierwszej pozycji).\n> - Tutaj dokładnie 5 z 6 elementów po prawej musi być mniejszych.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 2.2, max 1 pkt):\n> - **1 pkt** - dowolny poprawny przykład (klucz + 5 mniejszych + 1 ≥ klucz wśród A[2 7])\n> - **0 pkt** - tablica większa/mniejsza niż 7 elementów ALBO odpowiedź błędna ALBO brak\n\n## Typowe pułapki\n\n- **Tablica nie 7-elementowa** - punkt nie zostanie przyznany. Klucz CKE wyraźnie: \"7-elementowej tablicy\".\n- **6 mniejszych** zamiast 5 - wynikiem byłoby 6 zamian, nie 5.\n- **4 mniejsze** - wynikiem byłoby 4 zamiany.\n- **Pomylenie ostrej nierówności** - wartość RÓWNA kluczowi NIE wywoła zamian (warunek to `<`, nie `≤`).\n- **Klucz na innej pozycji niż A[1]** - definicja jasno mówi `klucz ← A[1]`, więc klucz to ZAWSZE pierwszy element.\n\n## Złożoność obliczeniowa\n\n- Konstrukcja przykładu: O(1).\n- Weryfikacja przykładu (symulacja): O(n) = O(7) = O(1).","image":"img/informatyka-2016-maj-matura-rozszerzona/zad-2.2.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 2016 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 2.2. (0-1)
Podaj przykład siedmioelementowej tablicy A, dla której funkcja przestaw(A) dokładnie
5 razy wykona zamień.
Miejsce na obliczenia.
Odp. A =

","answer_text_html":"

Zadanie 2.2. (0-1)
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
1 p. - za poprawną odpowiedź.
0 p. - za podanie odpowiedzi z tablicą większą niż 7-elementową lub odpowiedź błędną albo brak
odpowiedzi.
Przykładowa odpowiedź
[8,1,2,3,4,5,9]
Uwaga
Poprawną odpowiedzią jest podanie dowolnej siedmioelementowej tablicy, w której dokładnie pięć
elementów z pozycji 2…7 jest mniejszych od elementu pierwszego.

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

Poprawna odpowiedź

\n

A = [8, 1, 2, 3, 4, 5, 9]

\n

Sposób 1 - analiza warunku zamiany

\n

Kiedy zamień jest wykonywany? Tylko gdy A[k] < klucz, gdzie klucz = A[1].

\n

Dla tablicy 7-elementowej iterujemy k od 2 do 7 (6 razy). Aby zamień wykonał się dokładnie 5 razy, dokładnie 5 z elementów A[2 7] musi być mniejszych od A[1].

\n

Konstrukcja przykładu:

\n
  1. Wybierz dużą wartość jako klucz: np. A[1] = 8.
  2. Wstaw 5 wartości MNIEJSZYCH od 8 na pozycjach 2-7: np. 1, 2, 3, 4, 5.
  3. Wstaw 1 wartość WIĘKSZĄ lub równą 8 na jednej z pozycji 2-7: np. A[7] = 9.
\n

A = [8, 1, 2, 3, 4, 5, 9] → 5 elementów (1, 2, 3, 4, 5) < klucza 8; jeden (9) ≥ 8.

\n

Sposób 2 - weryfikacja symulacją

\n

Stan: A = [8, 1, 2, 3, 4, 5, 9], klucz = 8, w = 1.

\n

| k | A[k] | < 8? | zamień(A[w], A[k]) | A po | w po |
| 2 | 1 | TAK | zamień(A[1], A[2]) | [1,8,2,3,4,5,9] | 2 |
| 3 | 2 | TAK | zamień(A[2], A[3]) | [1,2,8,3,4,5,9] | 3 |
| 4 | 3 | TAK | zamień(A[3], A[4]) | [1,2,3,8,4,5,9] | 4 |
| 5 | 4 | TAK | zamień(A[4], A[5]) | [1,2,3,4,8,5,9] | 5 |
| 6 | 5 | TAK | zamień(A[5], A[6]) | [1,2,3,4,5,8,9] | 6 |
| 7 | 9 | NIE | - | [1,2,3,4,5,8,9] | 6 |

\n

Liczba zamian: 5 ✓

\n

Sposób 3 - inne poprawne przykłady

\n

Każda tablica [K, a, b, c, d, e, X] gdzie:

\n\n

Inne poprawne odpowiedzi:

\n\n

```python
def policz_zamiany(A):
klucz = A[0]
zamiany = 0
for k in range(1, len(A)):
if A[k] < klucz:
zamiany += 1
return zamiany

\n

print(policz_zamiany([8, 1, 2, 3, 4, 5, 9])) # 5
print(policz_zamiany([10, 1, 1, 1, 1, 1, 10])) # 5

\n

Reference informatyczny - liczba operacji w algorytmach partycji

\n
Reference - Analiza operacji partycji:
- Liczba wywołań zamień w przestaw = liczba elementów A[2 n] mniejszych od A[1].
- Maksimum: gdy wszystkie n-1 elementów są < klucza → n-1 zamian.
- Minimum: gdy żaden element nie jest < klucza → 0 zamian (tablica posortowana niemalejąco, klucz na pierwszej pozycji).
- Tutaj dokładnie 5 z 6 elementów po prawej musi być mniejszych.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 2.2, max 1 pkt):
- 1 pkt - dowolny poprawny przykład (klucz + 5 mniejszych + 1 ≥ klucz wśród A[2 7])
- 0 pkt - tablica większa/mniejsza niż 7 elementów ALBO odpowiedź błędna ALBO brak
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}