{"id":"informatyka-2019-maj-matura-rozszerzona/zad/1.1","paper_id":"informatyka-2019-maj-matura-rozszerzona","number":"1.1","points":5,"ptype":"open","subject":"informatyka","category":"matura","year":2019,"month":"maj","level":"rozszerzona","text":"Zadanie 1.1. (0-5)\nNapisz algorytm (w postaci listy kroków, w pseudokodzie lub w wybranym języku\nprogramowania), który dla danego ciągu liczb zapisanych przez dzieci znajdzie pierwszą liczbę\nzapisaną przez Jasia. Zakładamy, że każde z dzieci zapisało co najmniej jedną liczbę.\nPrzy ocenie będzie brana pod uwagę złożoność czasowa Twojego algorytmu. Maksymalną\nliczbę punktów uzyskasz za algorytm o złożoności lepszej niż liniowa.\nUwaga: W zapisie algorytmu możesz wykorzystać tylko operacje arytmetyczne (dodawanie,\nodejmowanie, mnożenie, dzielenie, dzielenie całkowite, reszta z dzielenia), instrukcje\nporównania, instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane\nfunkcje, wykorzystujące wyżej wymienione operacje.\nSpecyfikacja:\nDane:\nn\n- liczba całkowita większa od 1\nA[1 n]\n- tablica zawierająca ciąg n liczb zapisanych przez dzieci (najpierw\nwszystkie liczby nieparzyste, a potem wszystkie liczby parzyste)\nWynik:\nw\n- pierwsza od lewej parzysta liczba w tablicy A\nPrzykład:\nDane:\nn = 10\nA[1 n] = ሼ5, 99, 3, 7, 111, 13, 4, 24, 4, 8ሽ\nWynik:\nw = 4\nMIN_1R","answer":null,"answer_text":"Zadanie 1.1. (0-5)\nWymagania ogólne\nWymagania szczegółowe\nIII. Rozwiązywanie problemów\ni podejmowanie decyzji […]\nz zastosowaniem podejś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), […]\n16) opisuje własności algorytmów na\npodstawie ich analizy;\n17) ocenia zgodność algorytmu ze\nspecyfikacją problemu;\n18) oblicza liczbę operacji wykonywanych\nprzez algorytm;\n20) bada efektywność komputerowych\nrozwiązań problemów.\nSchemat punktowania\n5 p. - za poprawny algorytm o złożoności czasowej lepszej niż liniowa, w tym:\n1 p. - prawidłowy warunek pętli,\n1 p. - prawidłowe wyznaczenie podziału ciągu liczb,\n1 p. - prawidłowe wyznaczenie początku podciągu liczb,\n1 p. - prawidłowe wyznaczenie końca podciągu liczb,\n1 p. - prawidłowe wyznaczenie pierwszego elementu parzystego w A[] (lub jego indeksu).\n3 p. - za poprawny algorytm o złożoności czasowej liniowej, w tym:\n1 p. - za prawidłowy przebieg pętli,\n1 p. - za sprawdzenie warunku (parzystości liczby),\n1 p. - prawidłowe wyznaczenie pierwszego elementu parzystego w A[] (lub jego\nindeksu).\n0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.\nUwaga: Za każde inne poprawne rozwiązanie o złożoności lepszej niż liniowa przyznajemy\nmaksymalnie 5 punktów, a o złożoności liniowej - maksymalnie 3 punkty.\nPrzykładowe rozwiązania\nAlgorytm o złożoności logarytmicznej - wyszukiwanie binarne (w języku c++)\np ←1\nk ← n\ndopóki p n) i--;\nreturn i;\n}\nint wyszukiwanie(){\nint p = pier(n) - 1;\nint i = p;\nwhile(i < n)\n{\nif(A[i] % 2 == 0){\nint j = i;\nwhile(A[j] % 2 == 0) j--;\nreturn j + 1;\n}\nif(i + p > n) i = n - 1;\ni += p;\n}\n}\nw=A[wyszukiwanie()];","solution":"## Poprawna odpowiedź\n\n**Algorytm wyszukiwania binarnego (zmodyfikowanego) - złożoność O(log n):**\n\np ← 1\nk ← n\ndopóki p < k wykonuj\ns ← (p + k) div 2\njeżeli A[s] mod 2 = 1\np ← s + 1\nw przeciwnym przypadku\nk ← s\nw ← A[p]\n\n## Sposób 1 - wyszukiwanie binarne O(log n) [maksymalna punktacja]\n\n**Kluczowa obserwacja:** ciąg ma strukturę `[nieparzyste, nieparzyste, , parzyste, parzyste, ]`. Szukamy **granicy** między częścią nieparzystą a parzystą - czyli pierwszego indeksu z liczbą parzystą. Tak posortowany ciąg (najpierw 1, potem 0 dla parzystości) idealnie nadaje się do **wyszukiwania binarnego** - szukamy pierwszego wystąpienia 0.\n\n**Idea:** utrzymujemy przedział `[p, k]` zawierający szukaną pierwszą parzystą:\n- środek `s = (p+k) div 2`.\n- jeśli `A[s]` jest nieparzyste (mod 2 = 1) → granica jest po prawej: `p ← s+1`.\n- jeśli `A[s]` jest parzyste → granica może być w `s` lub wcześniej: `k ← s` (NIE `s-1`, bo `s` to kandydat!).\n- pętla kończy się gdy `p = k` → `A[p]` to pierwsza parzysta.\n\n**Python:**\n```python\ndef pierwsza_parzysta(A, n):\np, k = 0, n - 1 # indeksowanie od 0 w Python\nwhile p < k:\ns = (p + k) // 2\nif A[s] % 2 == 1:\np = s + 1\nelse:\nk = s\nreturn A[p]\n\nA = [5, 99, 3, 7, 111, 13, 4, 24, 4, 8]\nprint(pierwsza_parzysta(A, len(A))) # 4\n\n**Pascal (indeksowanie od 1 jak w CKE):**\n```pascal\nfunction PierwszaParzysta(var A: array of LongInt; n: Integer): LongInt;\nvar p, k, s: Integer;\nbegin\np := 1; k := n;\nwhile p < k do\nbegin\ns := (p + k) div 2;\nif A[s] mod 2 = 1 then\np := s + 1\nelse\nk := s;\nend;\nPierwszaParzysta := A[p];\nend;\n\n**C++:**\n```cpp\nint pierwszaParzysta(int A[], int n) {\nint p = 1, k = n;\nwhile (p < k) {\nint s = (p + k) / 2;\nif (A[s] % 2 == 1) p = s + 1;\nelse k = s;\n}\nreturn A[p];\n}\n\n**Weryfikacja na przykładzie:** A = [5,99,3,7,111,13,4,24,4,8], n=10.\n- p=1, k=10 → s=5, A[5]=111 nieparzysta → p=6.\n- p=6, k=10 → s=8, A[8]=24 parzysta → k=8.\n- p=6, k=8 → s=7, A[7]=4 parzysta → k=7.\n- p=6, k=7 → s=6, A[6]=13 nieparzysta → p=7.\n- p=7, k=7 → pętla kończy. w = A[7] = 4 ✓\n\n## Sposób 2 - wyszukiwanie liniowe O(n) [max 3 pkt]\n\nNajprostsza wersja - przeglądamy tablicę od lewej, zwracamy pierwszy element parzysty:\n\ndla i od 1 do n wykonuj\njeżeli A[i] mod 2 = 0\nw ← A[i]\nzakończ\n\n**Python:**\n```python\ndef liniowo(A):\nfor x in A:\nif x % 2 == 0:\nreturn x\n\nDziała poprawnie, ale klucz CKE nagradza maksymalnie 3 pkt zamiast 5 - uczyć się więc rozwiązania binarnego.\n\n## Reference informatyczny - wyszukiwanie binarne\n\n> Reference - Binary Search w wariancie \"znajdź pierwsze wystąpienie\":\n> - Klasyczne wyszukiwanie binarne szuka **dokładnej wartości** - tutaj szukamy **granicy** (pierwszy element spełniający warunek).\n> - Niezmiennik pętli: w przedziale `[p, k]` znajduje się szukana wartość.\n> - WAŻNE: gdy `A[s]` spełnia warunek (parzyste), ustawiamy `k = s` (NIE `s-1`!), bo `s` może być odpowiedzią.\n> - Złożoność: **O(log n)** - w każdej iteracji przedział kurczy się dwukrotnie.\n> - Wymagania: monotoniczność warunku (od pewnego momentu wszystkie elementy spełniają warunek).\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 1.1, max 5 pkt):\n> - **5 pkt** - algorytm o złożoności lepszej niż liniowa (binarka):\n> - 1 pkt - prawidłowy warunek pętli (`p < k`)\n> - 1 pkt - prawidłowe wyznaczenie podziału ciągu (s = (p+k) div 2)\n> - 1 pkt - prawidłowe wyznaczenie początku podciągu (p ← s+1)\n> - 1 pkt - prawidłowe wyznaczenie końca podciągu (k ← s)\n> - 1 pkt - prawidłowe wyznaczenie pierwszego parzystego (w ← A[p])\n> - **3 pkt** - algorytm liniowy:\n> - 1 pkt - prawidłowy przebieg pętli\n> - 1 pkt - sprawdzenie warunku parzystości\n> - 1 pkt - wyznaczenie pierwszego parzystego\n> - **0 pkt** - błędna lub brak odpowiedzi\n\n## Typowe pułapki\n\n- **`k ← s-1` zamiast `k ← s`** - gubimy kandydata; pętla może minąć poprawny indeks.\n- **`p ← s` zamiast `p ← s+1`** - pętla nie kończy się gdy A[s] nieparzysta i p == s.\n- **Warunek `p ≤ k`** zamiast `p < k` - niepotrzebna dodatkowa iteracja, ryzyko out-of-bounds.\n- **Off-by-one indeksowanie** - CKE używa od 1, Python/C++ od 0.\n- **Test parzystości** `A[s] mod 2 = 0` vs `A[s] mod 2 = 1` - łatwo pomylić kierunek.\n- **Brak założenia, że co najmniej jedna parzysta liczba istnieje** - algorytm tego nie sprawdza, ale w treści mamy gwarancję (Jaś zapisał co najmniej jedną liczbę).\n\n## Złożoność obliczeniowa\n\n- **Czas: O(log n)** - w każdej iteracji przedział `[p, k]` kurczy się o połowę.\n- **Pamięć: O(1)** - kilka zmiennych pomocniczych (p, k, s).\n- Dla porównania: rozwiązanie liniowe = O(n) (max 3 pkt w CKE).","image":"img/informatyka-2019-maj-matura-rozszerzona/zad-1.1.webp","solution_image":null,"topics":null,"page_from":2,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2019 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 1.1. (0-5)
Napisz algorytm (w postaci listy kroków, w pseudokodzie lub w wybranym języku
programowania), który dla danego ciągu liczb zapisanych przez dzieci znajdzie pierwszą liczbę
zapisaną przez Jasia. Zakładamy, że każde z dzieci zapisało co najmniej jedną liczbę.
Przy ocenie będzie brana pod uwagę złożoność czasowa Twojego algorytmu. Maksymalną
liczbę punktów uzyskasz za algorytm o złożoności lepszej niż liniowa.
Uwaga: W zapisie algorytmu możesz wykorzystać tylko operacje arytmetyczne (dodawanie,
odejmowanie, mnożenie, dzielenie, dzielenie całkowite, reszta z dzielenia), instrukcje
porównania, instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane
funkcje, wykorzystujące wyżej wymienione operacje.
Specyfikacja:
Dane:
n

\n\n

A[1 n]

\n\n

wszystkie liczby nieparzyste, a potem wszystkie liczby parzyste)
Wynik:
w

\n\n

Przykład:
Dane:
n = 10
A[1 n] = ሼ5, 99, 3, 7, 111, 13, 4, 24, 4, 8ሽ
Wynik:
w = 4
MIN_1R

","answer_text_html":"

Zadanie 1.1. (0-5)
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), […]

\n
  1. opisuje własności algorytmów na
\n

podstawie ich analizy;

\n
  1. ocenia zgodność algorytmu ze
\n

specyfikacją problemu;

\n
  1. oblicza liczbę operacji wykonywanych
\n

przez algorytm;

\n
  1. bada efektywność komputerowych
\n

rozwiązań problemów.
Schemat punktowania
5 p. - za poprawny algorytm o złożoności czasowej lepszej niż liniowa, w tym:
1 p. - prawidłowy warunek pętli,
1 p. - prawidłowe wyznaczenie podziału ciągu liczb,
1 p. - prawidłowe wyznaczenie początku podciągu liczb,
1 p. - prawidłowe wyznaczenie końca podciągu liczb,
1 p. - prawidłowe wyznaczenie pierwszego elementu parzystego w A[] (lub jego indeksu).
3 p. - za poprawny algorytm o złożoności czasowej liniowej, w tym:
1 p. - za prawidłowy przebieg pętli,
1 p. - za sprawdzenie warunku (parzystości liczby),
1 p. - prawidłowe wyznaczenie pierwszego elementu parzystego w A[] (lub jego
indeksu).
0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.
Uwaga: Za każde inne poprawne rozwiązanie o złożoności lepszej niż liniowa przyznajemy
maksymalnie 5 punktów, a o złożoności liniowej - maksymalnie 3 punkty.
Przykładowe rozwiązania
Algorytm o złożoności logarytmicznej - wyszukiwanie binarne (w języku c++)
p ←1
k ← n
dopóki p <k wykonuj
s ← (p + k) div 2
jeżeli ( A[s] mod 2 = 1 )
p ← s + 1
w przeciwnym przypadku
k ← s
w ← A[p]
Algorytm o złożoności logarytmicznej - wyszukiwanie binarne (w języku Python)
def szukaj_bin(A):
lewy, prawy = 1, n
while lewy < prawy:
środkowy = (lewy + prawy) // 2
if A[środkowy] % 2 != 0:
lewy = środkowy + 1
else:
prawy = środkowy
return prawy
Algorytm o złożoności liniowej - wyszukiwanie liniowe
p ←1
dopóki A[p] mod 2 = 1 wykonuj
p ← p + 1
w ← A[p]
Algorytm o złożoności pierwiastkowej
int pier(int n){
int i = 1;
while(i * i < n) i++;
if(i * i > n) i--;
return i;
}
int wyszukiwanie(){
int p = pier(n) - 1;
int i = p;
while(i < n)
{
if(A[i] % 2 == 0){
int j = i;
while(A[j] % 2 == 0) j--;
return j + 1;
}
if(i + p > n) i = n - 1;
i += p;
}
}
w=A[wyszukiwanie()];

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

Poprawna odpowiedź

\n

Algorytm wyszukiwania binarnego (zmodyfikowanego) - złożoność O(log n):

\n

p ← 1
k ← n
dopóki p < k wykonuj
s ← (p + k) div 2
jeżeli A[s] mod 2 = 1
p ← s + 1
w przeciwnym przypadku
k ← s
w ← A[p]

\n

Sposób 1 - wyszukiwanie binarne O(log n) [maksymalna punktacja]

\n

Kluczowa obserwacja: ciąg ma strukturę [nieparzyste, nieparzyste, , parzyste, parzyste, ]. Szukamy granicy między częścią nieparzystą a parzystą - czyli pierwszego indeksu z liczbą parzystą. Tak posortowany ciąg (najpierw 1, potem 0 dla parzystości) idealnie nadaje się do wyszukiwania binarnego - szukamy pierwszego wystąpienia 0.

\n

Idea: utrzymujemy przedział [p, k] zawierający szukaną pierwszą parzystą:

\n\n

Python:
```python
def pierwsza_parzysta(A, n):
p, k = 0, n - 1 # indeksowanie od 0 w Python
while p < k:
s = (p + k) // 2
if A[s] % 2 == 1:
p = s + 1
else:
k = s
return A[p]

\n

A = [5, 99, 3, 7, 111, 13, 4, 24, 4, 8]
print(pierwsza_parzysta(A, len(A))) # 4

\n

Pascal (indeksowanie od 1 jak w CKE):
```pascal
function PierwszaParzysta(var A: array of LongInt; n: Integer): LongInt;
var p, k, s: Integer;
begin
p := 1; k := n;
while p < k do
begin
s := (p + k) div 2;
if A[s] mod 2 = 1 then
p := s + 1
else
k := s;
end;
PierwszaParzysta := A[p];
end;

\n

C++:
```cpp
int pierwszaParzysta(int A[], int n) {
int p = 1, k = n;
while (p < k) {
int s = (p + k) / 2;
if (A[s] % 2 == 1) p = s + 1;
else k = s;
}
return A[p];
}

\n

Weryfikacja na przykładzie: A = [5,99,3,7,111,13,4,24,4,8], n=10.

\n\n

Sposób 2 - wyszukiwanie liniowe O(n) [max 3 pkt]

\n

Najprostsza wersja - przeglądamy tablicę od lewej, zwracamy pierwszy element parzysty:

\n

dla i od 1 do n wykonuj
jeżeli A[i] mod 2 = 0
w ← A[i]
zakończ

\n

Python:
```python
def liniowo(A):
for x in A:
if x % 2 == 0:
return x

\n

Działa poprawnie, ale klucz CKE nagradza maksymalnie 3 pkt zamiast 5 - uczyć się więc rozwiązania binarnego.

\n

Reference informatyczny - wyszukiwanie binarne

\n
Reference - Binary Search w wariancie "znajdź pierwsze wystąpienie":
- Klasyczne wyszukiwanie binarne szuka dokładnej wartości - tutaj szukamy granicy (pierwszy element spełniający warunek).
- Niezmiennik pętli: w przedziale [p, k] znajduje się szukana wartość.
- WAŻNE: gdy A[s] spełnia warunek (parzyste), ustawiamy k = s (NIE s-1!), bo s może być odpowiedzią.
- Złożoność: O(log n) - w każdej iteracji przedział kurczy się dwukrotnie.
- Wymagania: monotoniczność warunku (od pewnego momentu wszystkie elementy spełniają warunek).
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 1.1, max 5 pkt):
- 5 pkt - algorytm o złożoności lepszej niż liniowa (binarka):
- 1 pkt - prawidłowy warunek pętli (p < k)
- 1 pkt - prawidłowe wyznaczenie podziału ciągu (s = (p+k) div 2)
- 1 pkt - prawidłowe wyznaczenie początku podciągu (p ← s+1)
- 1 pkt - prawidłowe wyznaczenie końca podciągu (k ← s)
- 1 pkt - prawidłowe wyznaczenie pierwszego parzystego (w ← A[p])
- 3 pkt - algorytm liniowy:
- 1 pkt - prawidłowy przebieg pętli
- 1 pkt - sprawdzenie warunku parzystości
- 1 pkt - wyznaczenie pierwszego parzystego
- 0 pkt - błędna lub brak odpowiedzi
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}