{"id":"informatyka-2016-maj-matura-rozszerzona/zad/2.3","paper_id":"informatyka-2016-maj-matura-rozszerzona","number":"2.3","points":3,"ptype":"open","subject":"informatyka","category":"matura","year":2016,"month":"maj","level":"rozszerzona","text":"Zadanie 2.3. (0-3)\nTablica A[1 100] zawiera wszystkie liczby całkowite z przedziału <1, 100> w następującej\nkolejności:\nA = [10, 20, 30, , 100, 9, 19, 29, , 99, 8, 18, 28, , 98, , 1, 11, 21, , 91].\n(najpierw rosnąco wszystkie liczby kończące się na 0, potem rosnąco liczby kończące się\nna 9, potem na 8 itd.)\nPodaj wartość zmiennej w oraz wartości trzech pierwszych elementów tablicy A (A[1], A[2],\nA[3]), po wykonaniu funkcji przestaw(A).\nMiejsce na obliczenia.\nOdp. w =\nA[1] = , A[2] = A[3] =\nWypełnia\negzaminator\nNr zadania\n2.1.\n2.2.\n2.3.\nMaks. liczba pkt.\n2\n1\n3\nUzyskana liczba pkt.\nMIN_1R","answer":null,"answer_text":"Zadanie 2.3. (0-3)\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\n3 p. - za odpowiedź poprawną, w tym:\n- 1 p. - za poprawną wartość w\n- 2 p. - za poprawne wszystkie trzy wartości A[1], A[2] i A[3].\n0 p. - za odpowiedź błędną albo brak odpowiedzi.\nPoprawna odpowiedź\nw = 10\nA[1] = 9\nA[2] = 8\nA[3] = 7\nUwaga\nZa poprawne dwie z trzech wartości A[1], A[2] i A[3] - 1 punkt.","solution":"## Poprawna odpowiedź\n\n**w = 10**\n\n**A[1] = 9, A[2] = 8, A[3] = 7**\n\n## Sposób 1 - analiza struktury tablicy\n\n**Struktura tablicy A[1 100]:**\n- A[1 10] = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] (kończące się na 0)\n- A[11 20] = [9, 19, 29, 39, 49, 59, 69, 79, 89, 99] (kończące się na 9)\n- A[21 30] = [8, 18, 28, 38, 48, 58, 68, 78, 88, 98] (kończące się na 8)\n- A[91 100] = [1, 11, 21, 31, 41, 51, 61, 71, 81, 91] (kończące się na 1)\n\n**Klucz = A[1] = 10.**\n\n**Ile elementów A[2 100] jest mniejszych od 10?** To liczby ze zbioru {1, 2, 3, 4, 5, 6, 7, 8, 9} = **9 elementów**.\n\n**Pozycje tych 9 elementów w tablicy:**\n- 9 → A[11] (pierwszy element grupy kończących się na 9, czyli najmniejsza wartość w tej grupie)\n- 8 → A[21]\n- 7 → A[31]\n- 6 → A[41]\n- 5 → A[51]\n- 4 → A[61]\n- 3 → A[71]\n- 2 → A[81]\n- 1 → A[91]\n\n## Sposób 2 - symulacja kluczowych kroków\n\nIterujemy k od 2 do 100. Pierwsze 9 elementów mniejszych od 10 napotykamy na pozycjach 11, 21, 31, 41, 51, 61, 71, 81, 91.\n\n**Krok dla k = 11 (A[11] = 9 < 10):** zamień(A[1], A[11]). Stan przed: A[1]=10, A[2 10]=[20,30, ,100], A[11]=9. Stan po:\n- A[1] = **9**\n- A[11] = 10\n- w → 2\n\n**Krok dla k = 21 (A[21] = 8 < 10):** zamień(A[2], A[21]). Przed: A[2] = 20, A[21] = 8. Po:\n- A[2] = **8**\n- A[21] = 20\n- w → 3\n\n**Krok dla k = 31 (A[31] = 7 < 10):** zamień(A[3], A[31]). Przed: A[3] = 30, A[31] = 7. Po:\n- A[3] = **7**\n- A[31] = 30\n- w → 4\n\nKolejne zamiany umieszczają 6, 5, 4, 3, 2, 1 na pozycjach A[4] A[9], a w rośnie do 10.\n\n**Po wszystkich 9 zamianach: w = 10.**\n\n## Sposób 3 - implementacja Python (weryfikacja)\n\n```python\n# Konstrukcja tablicy A\nA = []\nfor ostatnia_cyfra in [0, 9, 8, 7, 6, 5, 4, 3, 2, 1]:\nfor tens in range(0, 10):\nliczba = tens * 10 + ostatnia_cyfra\nif liczba == 0:\nliczba = 100 # przyjmujemy 100 w grupie \"kończą się na 0\"\nA.append(liczba)\n\n# Sprawdźmy pierwszych 11 elementów\nprint(A[:11]) # [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 9]\n\n# Wykonaj funkcję przestaw\nklucz = A[0]\nw = 0\nfor k in range(1, len(A)):\nif A[k] < klucz:\nA[w], A[k] = A[k], A[w]\nw += 1\n\nprint(\"w =\", w + 1) # w w pseudokodzie indeksowany od 1\nprint(\"A[1 3] =\", A[0], A[1], A[2]) # 9 8 7\n\nWynik:\nw = 10\nA[1 3] = 9 8 7\n\n## Reference informatyczny - partycja Lomuto na konkretnej tablicy\n\n> Reference - Stan końcowy partycji `przestaw`:\n> - Po pętli `w - 1` to liczba elementów `A[2 n]` mniejszych od klucza.\n> - Zatem **w = (liczba mniejszych) + 1**.\n> - Tutaj: 9 mniejszych → **w = 10**.\n> - W lewej części A[1 w-1] = A[1 9] znajdują się wszystkie elementy < klucza, w **kolejności, w jakiej zostały napotkane** podczas iteracji.\n> - Bo iterujemy k = 11, 21, 31, , 91 i wstawiamy 9, 8, 7, , 1 - **kolejność: 9, 8, 7, 6, 5, 4, 3, 2, 1**.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 2.3, max 3 pkt):\n> - **1 pkt** za poprawną wartość w = 10\n> - **2 pkt** za poprawne wszystkie trzy A[1], A[2], A[3] (= 9, 8, 7)\n> - **Uwaga: 2 z 3 wartości A[1] A[3] dają 1 pkt**\n> - **0 pkt** za odpowiedź błędną\n\n## Typowe pułapki\n\n- **Pomylenie kolejności kończących się na cyfry** - w pseudokodzie problemu cyfry są: 0, 9, 8, 7, (NIE rosnąco 1, 2, 3, ).\n- **Liczenie elementów ≤ 10** zamiast < 10 - to dałoby 10 elementów, ale klucz 10 nie jest < 10, więc i tak 9.\n- **Założenie, że tablica jest pomieszana losowo** - tu jest deterministyczna struktura ułożona w bloki.\n- **Pomyłka z wartościami zamienianymi** - pierwsza zamiana to A[1]↔A[11], wstawiająca 9 na pozycję 1 (nie A[2]↔A[11]).\n- **Off-by-one w w**: w startuje od 1; po każdej zamianie rośnie o 1. Po 9 zamianach w = 1 + 9 = 10.\n\n## Złożoność obliczeniowa\n\n- Algorytm O(n) = O(100) operacji.\n- Liczba zamian: 9 (= liczba elementów < klucza).","image":"img/informatyka-2016-maj-matura-rozszerzona/zad-2.3.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.3. (0-3)
Tablica A[1 100] zawiera wszystkie liczby całkowite z przedziału <1, 100> w następującej
kolejności:
A = [10, 20, 30, , 100, 9, 19, 29, , 99, 8, 18, 28, , 98, , 1, 11, 21, , 91].
(najpierw rosnąco wszystkie liczby kończące się na 0, potem rosnąco liczby kończące się
na 9, potem na 8 itd.)
Podaj wartość zmiennej w oraz wartości trzech pierwszych elementów tablicy A (A[1], A[2],
A[3]), po wykonaniu funkcji przestaw(A).
Miejsce na obliczenia.
Odp. w =
A[1] = , A[2] = A[3] =
Wypełnia
egzaminator
Nr zadania
2.1.
2.2.
2.3.
Maks. liczba pkt.
2
1
3
Uzyskana liczba pkt.
MIN_1R

","answer_text_html":"

Zadanie 2.3. (0-3)
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
3 p. - za odpowiedź poprawną, w tym:

\n\n

0 p. - za odpowiedź błędną albo brak odpowiedzi.
Poprawna odpowiedź
w = 10
A[1] = 9
A[2] = 8
A[3] = 7
Uwaga
Za poprawne dwie z trzech wartości A[1], A[2] i A[3] - 1 punkt.

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

Poprawna odpowiedź

\n

w = 10

\n

A[1] = 9, A[2] = 8, A[3] = 7

\n

Sposób 1 - analiza struktury tablicy

\n

Struktura tablicy A[1 100]:

\n\n

Klucz = A[1] = 10.

\n

Ile elementów A[2 100] jest mniejszych od 10? To liczby ze zbioru {1, 2, 3, 4, 5, 6, 7, 8, 9} = 9 elementów.

\n

Pozycje tych 9 elementów w tablicy:

\n\n

Sposób 2 - symulacja kluczowych kroków

\n

Iterujemy k od 2 do 100. Pierwsze 9 elementów mniejszych od 10 napotykamy na pozycjach 11, 21, 31, 41, 51, 61, 71, 81, 91.

\n

Krok dla k = 11 (A[11] = 9 < 10): zamień(A[1], A[11]). Stan przed: A[1]=10, A[2 10]=[20,30, ,100], A[11]=9. Stan po:

\n\n

Krok dla k = 21 (A[21] = 8 < 10): zamień(A[2], A[21]). Przed: A[2] = 20, A[21] = 8. Po:

\n\n

Krok dla k = 31 (A[31] = 7 < 10): zamień(A[3], A[31]). Przed: A[3] = 30, A[31] = 7. Po:

\n\n

Kolejne zamiany umieszczają 6, 5, 4, 3, 2, 1 na pozycjach A[4] A[9], a w rośnie do 10.

\n

Po wszystkich 9 zamianach: w = 10.

\n

Sposób 3 - implementacja Python (weryfikacja)

\n

```python

\n

Konstrukcja tablicy A

\n

A = []
for ostatnia_cyfra in [0, 9, 8, 7, 6, 5, 4, 3, 2, 1]:
for tens in range(0, 10):
liczba = tens * 10 + ostatnia_cyfra
if liczba == 0:
liczba = 100 # przyjmujemy 100 w grupie "kończą się na 0"
A.append(liczba)

\n

Sprawdźmy pierwszych 11 elementów

\n

print(A[:11]) # [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 9]

\n

Wykonaj funkcję przestaw

\n

klucz = A[0]
w = 0
for k in range(1, len(A)):
if A[k] < klucz:
A[w], A[k] = A[k], A[w]
w += 1

\n

print("w =", w + 1) # w w pseudokodzie indeksowany od 1
print("A[1 3] =", A[0], A[1], A[2]) # 9 8 7

\n

Wynik:
w = 10
A[1 3] = 9 8 7

\n

Reference informatyczny - partycja Lomuto na konkretnej tablicy

\n
Reference - Stan końcowy partycji przestaw:
- Po pętli w - 1 to liczba elementów A[2 n] mniejszych od klucza.
- Zatem w = (liczba mniejszych) + 1.
- Tutaj: 9 mniejszych → w = 10.
- W lewej części A[1 w-1] = A[1 9] znajdują się wszystkie elementy < klucza, w kolejności, w jakiej zostały napotkane podczas iteracji.
- Bo iterujemy k = 11, 21, 31, , 91 i wstawiamy 9, 8, 7, , 1 - kolejność: 9, 8, 7, 6, 5, 4, 3, 2, 1.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 2.3, max 3 pkt):
- 1 pkt za poprawną wartość w = 10
- 2 pkt za poprawne wszystkie trzy A[1], A[2], A[3] (= 9, 8, 7)
- Uwaga: 2 z 3 wartości A[1] A[3] dają 1 pkt
- 0 pkt za odpowiedź błędną
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}