{"id":"informatyka-2017-maj-matura-rozszerzona/zad/2.1","paper_id":"informatyka-2017-maj-matura-rozszerzona","number":"2.1","points":2,"ptype":"open","subject":"informatyka","category":"matura","year":2017,"month":"maj","level":"rozszerzona","text":"Zadanie 2.1. (0-2)\nUzupełnij tabelę - podaj wartość licz(x) dla podanych argumentów x.\nx\nlicz(x)\n11\n2\n13\n21\n32\nMiejsce na obliczenia\nMIN_1R","answer":null,"answer_text":"Zadanie 2.1. (0-2)\nIII. Rozwiązywanie problemów\ni podejmowanie decyzji […],\nz zastosowaniem podejścia algorytmicznego.\n5) posługuje się podstawowymi technikami\nalgorytmicznymi;\n9) stosuje rekurencję w prostych sytuacjach\nproblemowych\n16) opisuje własności algorytmów na\npodstawie ich analizy;\n17) ocenia zgodność algorytmu ze\nspecyfikacją problemu;\nSchemat punktowania\n2 p. - za podanie trzech poprawnych wartości.\n1 p. - za podanie dwóch poprawnych wartości.\n0 p. - za podanie jednej poprawnej wartości albo za brak odpowiedzi.\nPoprawna odpowiedź:\nx\nlicz(x)\n13\n2\n21\n1\n32\n-4","solution":"## Poprawna odpowiedź\n\n| x | licz(x) |\n| 11 | 2 |\n| 13 | **2** |\n| 21 | **1** |\n| 32 | **-4** |\n\n## Sposób 1 - kluczowa obserwacja\n\nFunkcja `licz(x)` to **suma cyfr binarnych z modyfikowaną wagą**: każda jedynka w zapisie binarnym x daje +1, każde zero daje -1, a najstarszy bit (zawsze 1) startuje od wartości 1. Krótko: **licz(x) = (liczba jedynek w bin(x)) - (liczba zer w bin(x), pomijając wiodące zera) + ** Lepiej: rozwińmy rekurencję.\n\nDla x = 1: zwraca 1.\nDla x > 1: w := licz(x div 2); jeśli x mod 2 = 1 (czyli ostatni bit jest 1) → zwróć w+1; w przeciwnym razie (ostatni bit 0) → zwróć w-1.\n\nWięc każda cyfra binarna x (czytana od najmłodszej, ale pomijając najstarszą - ta startuje wartością 1):\n- bit 1 → dodaje +1\n- bit 0 → odejmuje 1\n\n**Wzór:** licz(x) = 1 + (liczba_jedynek_w_bin(x) - 1) - (liczba_zer_w_bin(x)) = liczba_jedynek - liczba_zer.\n\nUwaga: najstarszy bit (zawsze 1 dla x > 0) liczy się raz, ale w sumie wszystkie jedynki dają +1 każda, zera dają -1 każda. Plus startowa wartość 1 z licz(1) Sprawdźmy.\n\n## Sposób 2 - symulacja krok po kroku\n\n### x = 11 (kontrola)\n11 w binarnym: **1011**\n- licz(11): 11 mod 2 = 1 → w = licz(5), wynik = w + 1\n- licz(5): 5 mod 2 = 1 → w = licz(2), wynik = w + 1\n- licz(2): 2 mod 2 = 0 → w = licz(1), wynik = w - 1\n- licz(1) = 1\n- licz(2) = 1 - 1 = 0\n- licz(5) = 0 + 1 = 1\n- licz(11) = 1 + 1 = **2** ✓\n\n### x = 13\n13 w binarnym: **1101**\n- licz(13): 13 mod 2 = 1 → w = licz(6), wynik = w + 1\n- licz(6): 6 mod 2 = 0 → w = licz(3), wynik = w - 1\n- licz(3): 3 mod 2 = 1 → w = licz(1), wynik = w + 1\n- licz(1) = 1\n- licz(3) = 1 + 1 = 2\n- licz(6) = 2 - 1 = 1\n- licz(13) = 1 + 1 = **2** ✓\n\n### x = 21\n21 w binarnym: **10101**\n- licz(21): 21 mod 2 = 1 → w = licz(10), wynik = w + 1\n- licz(10): 10 mod 2 = 0 → w = licz(5), wynik = w - 1\n- licz(5): 5 mod 2 = 1 → w = licz(2), wynik = w + 1\n- licz(2): 2 mod 2 = 0 → w = licz(1), wynik = w - 1\n- licz(1) = 1\n- licz(2) = 1 - 1 = 0\n- licz(5) = 0 + 1 = 1\n- licz(10) = 1 - 1 = 0\n- licz(21) = 0 + 1 = **1** ✓\n\n### x = 32\n32 w binarnym: **100000**\n- licz(32): 32 mod 2 = 0 → w = licz(16), wynik = w - 1\n- licz(16): 16 mod 2 = 0 → w = licz(8), wynik = w - 1\n- licz(8): 8 mod 2 = 0 → w = licz(4), wynik = w - 1\n- licz(4): 4 mod 2 = 0 → w = licz(2), wynik = w - 1\n- licz(2): 2 mod 2 = 0 → w = licz(1), wynik = w - 1\n- licz(1) = 1\n- licz(2) = 1 - 1 = 0\n- licz(4) = 0 - 1 = -1\n- licz(8) = -1 - 1 = -2\n- licz(16) = -2 - 1 = -3\n- licz(32) = -3 - 1 = **-4** ✓\n\n## Sposób 3 - wzór ogólny\n\nDla x w zapisie binarnym mającym `j` jedynek i `z` zer:\n**licz(x) = j - z**\n\nWeryfikacja:\n- 11 = 1011: j=3, z=1 → 3-1 = 2 ✓\n- 13 = 1101: j=3, z=1 → 3-1 = 2 ✓\n- 21 = 10101: j=3, z=2 → 3-2 = 1 ✓\n- 32 = 100000: j=1, z=5 → 1-5 = **-4** ✓\n\n**Implementacja Python (weryfikacja):**\n```python\ndef licz(x):\nif x == 1:\nreturn 1\nw = licz(x // 2)\nif x % 2 == 1:\nreturn w + 1\nelse:\nreturn w - 1\n\nfor x in [11, 13, 21, 32]:\nprint(x, licz(x)) # 11 2, 13 2, 21 1, 32 -4\n\n## Reference algorytmiczny - rekurencja binarna\n\n> Reference - rekurencja po cyfrach binarnych:\n> - Wzorzec: `f(x) = f(x div 2) ± coś` rozwija cyfry binarne x.\n> - Głębokość rekurencji = liczba bitów x = ⌊log₂ x⌋ + 1.\n> - Funkcja licz: zlicza różnicę między liczbą jedynek a zer w bin(x).\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 2.1, max 2 pkt):\n> - **2 pkt** - za 3 poprawne wartości (z 3 wymaganych: 13, 21, 32)\n> - **1 pkt** - za 2 poprawne\n> - **0 pkt** - za 1 poprawną albo brak\n\n## Typowe pułapki\n\n- **Znak -4 dla x = 32** - łatwo zapomnieć, że funkcja może zwracać liczby ujemne (samo licz(2) = 0, licz(4) = -1).\n- **Pomylenie x mod 2 z x div 2** - pierwsze daje ostatni bit (0/1), drugie usuwa ostatni bit.\n- **Niewłaściwy warunek bazowy** - `if x = 1` (nie x = 0!) zwraca 1.\n\n## Złożoność obliczeniowa\n\n- **Czas: O(log x)** - głębokość rekurencji to liczba bitów x.\n- **Pamięć: O(log x)** - stos rekurencji.","image":"img/informatyka-2017-maj-matura-rozszerzona/zad-2.1.webp","solution_image":null,"topics":null,"page_from":4,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2017 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 2.1. (0-2)
Uzupełnij tabelę - podaj wartość licz(x) dla podanych argumentów x.
x
licz(x)
11
2
13
21
32
Miejsce na obliczenia
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. posługuje się podstawowymi technikami
\n

algorytmicznymi;

\n
  1. stosuje rekurencję w prostych sytuacjach
\n

problemowych

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

podstawie ich analizy;

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

specyfikacją problemu;
Schemat punktowania
2 p. - za podanie trzech poprawnych wartości.
1 p. - za podanie dwóch poprawnych wartości.
0 p. - za podanie jednej poprawnej wartości albo za brak odpowiedzi.
Poprawna odpowiedź:
x
licz(x)
13
2
21
1
32
-4

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

Poprawna odpowiedź

\n

| x | licz(x) |
| 11 | 2 |
| 13 | 2 |
| 21 | 1 |
| 32 | -4 |

\n

Sposób 1 - kluczowa obserwacja

\n

Funkcja licz(x) to suma cyfr binarnych z modyfikowaną wagą: każda jedynka w zapisie binarnym x daje +1, każde zero daje -1, a najstarszy bit (zawsze 1) startuje od wartości 1. Krótko: licz(x) = (liczba jedynek w bin(x)) - (liczba zer w bin(x), pomijając wiodące zera) + Lepiej: rozwińmy rekurencję.

\n

Dla x = 1: zwraca 1.
Dla x > 1: w := licz(x div 2); jeśli x mod 2 = 1 (czyli ostatni bit jest 1) → zwróć w+1; w przeciwnym razie (ostatni bit 0) → zwróć w-1.

\n

Więc każda cyfra binarna x (czytana od najmłodszej, ale pomijając najstarszą - ta startuje wartością 1):

\n\n

Wzór: licz(x) = 1 + (liczba_jedynek_w_bin(x) - 1) - (liczba_zer_w_bin(x)) = liczba_jedynek - liczba_zer.

\n

Uwaga: najstarszy bit (zawsze 1 dla x > 0) liczy się raz, ale w sumie wszystkie jedynki dają +1 każda, zera dają -1 każda. Plus startowa wartość 1 z licz(1) Sprawdźmy.

\n

Sposób 2 - symulacja krok po kroku

\n
x = 11 (kontrola)
\n

11 w binarnym: 1011

\n\n
x = 13
\n

13 w binarnym: 1101

\n\n
x = 21
\n

21 w binarnym: 10101

\n\n
x = 32
\n

32 w binarnym: 100000

\n\n

Sposób 3 - wzór ogólny

\n

Dla x w zapisie binarnym mającym j jedynek i z zer:
licz(x) = j - z

\n

Weryfikacja:

\n\n

Implementacja Python (weryfikacja):
```python
def licz(x):
if x == 1:
return 1
w = licz(x // 2)
if x % 2 == 1:
return w + 1
else:
return w - 1

\n

for x in [11, 13, 21, 32]:
print(x, licz(x)) # 11 2, 13 2, 21 1, 32 -4

\n

Reference algorytmiczny - rekurencja binarna

\n
Reference - rekurencja po cyfrach binarnych:
- Wzorzec: f(x) = f(x div 2) ± coś rozwija cyfry binarne x.
- Głębokość rekurencji = liczba bitów x = ⌊log₂ x⌋ + 1.
- Funkcja licz: zlicza różnicę między liczbą jedynek a zer w bin(x).
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 2.1, max 2 pkt):
- 2 pkt - za 3 poprawne wartości (z 3 wymaganych: 13, 21, 32)
- 1 pkt - za 2 poprawne
- 0 pkt - za 1 poprawną albo brak
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}