# Informatyka — zadanie 2.1

> Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2017-05/zad/2.1
> Wersja Markdown strony zadania (dla asystentów AI). Przy cytowaniu podaj matura.lol i link powyżej.

- arkusz: Informatyka · Matura · maj 2017 (rozszerzona)
- rok: 2017
- poziom: rozszerzona
- typ: open
- punkty: 2
- działy: Programowanie i algorytmika, algorytmy

## Treść

Zadanie 2. Rekurencja
Funkcja licz(x) przyjmuje jako argument dodatnią liczbę całkowitą x, natomiast jako wynik
daje pewną liczbę całkowitą.
licz(x)
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2)
jeżeli x mod 2 = 1
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1
Uwaga: div - dzielenie całkowite, mod - reszta z dzielenia całkowitego.

## Rozwiązanie — maturazai.pl (AI)

## Poprawna odpowiedź

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

## Sposób 1 - kluczowa obserwacja

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ę.

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.

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

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

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.

## Sposób 2 - symulacja krok po kroku

### x = 11 (kontrola)
11 w binarnym: **1011**
- licz(11): 11 mod 2 = 1 → w = licz(5), wynik = w + 1
- licz(5): 5 mod 2 = 1 → w = licz(2), wynik = w + 1
- licz(2): 2 mod 2 = 0 → w = licz(1), wynik = w - 1
- licz(1) = 1
- licz(2) = 1 - 1 = 0
- licz(5) = 0 + 1 = 1
- licz(11) = 1 + 1 = **2** ✓

### x = 13
13 w binarnym: **1101**
- licz(13): 13 mod 2 = 1 → w = licz(6), wynik = w + 1
- licz(6): 6 mod 2 = 0 → w = licz(3), wynik = w - 1
- licz(3): 3 mod 2 = 1 → w = licz(1), wynik = w + 1
- licz(1) = 1
- licz(3) = 1 + 1 = 2
- licz(6) = 2 - 1 = 1
- licz(13) = 1 + 1 = **2** ✓

### x = 21
21 w binarnym: **10101**
- licz(21): 21 mod 2 = 1 → w = licz(10), wynik = w + 1
- licz(10): 10 mod 2 = 0 → w = licz(5), wynik = w - 1
- licz(5): 5 mod 2 = 1 → w = licz(2), wynik = w + 1
- licz(2): 2 mod 2 = 0 → w = licz(1), wynik = w - 1
- licz(1) = 1
- licz(2) = 1 - 1 = 0
- licz(5) = 0 + 1 = 1
- licz(10) = 1 - 1 = 0
- licz(21) = 0 + 1 = **1** ✓

### x = 32
32 w binarnym: **100000**
- licz(32): 32 mod 2 = 0 → w = licz(16), wynik = w - 1
- licz(16): 16 mod 2 = 0 → w = licz(8), wynik = w - 1
- licz(8): 8 mod 2 = 0 → w = licz(4), wynik = w - 1
- licz(4): 4 mod 2 = 0 → w = licz(2), wynik = w - 1
- licz(2): 2 mod 2 = 0 → w = licz(1), wynik = w - 1
- licz(1) = 1
- licz(2) = 1 - 1 = 0
- licz(4) = 0 - 1 = -1
- licz(8) = -1 - 1 = -2
- licz(16) = -2 - 1 = -3
- licz(32) = -3 - 1 = **-4** ✓

## Sposób 3 - wzór ogólny

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

Weryfikacja:
- 11 = 1011: j=3, z=1 → 3-1 = 2 ✓
- 13 = 1101: j=3, z=1 → 3-1 = 2 ✓
- 21 = 10101: j=3, z=2 → 3-2 = 1 ✓
- 32 = 100000: j=1, z=5 → 1-5 = **-4** ✓

**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

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

## Reference algorytmiczny - rekurencja binarna

> 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).

## Schemat oceniania CKE

> 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

## Typowe pułapki

- **Znak -4 dla x = 32** - łatwo zapomnieć, że funkcja może zwracać liczby ujemne (samo licz(2) = 0, licz(4) = -1).
- **Pomylenie x mod 2 z x div 2** - pierwsze daje ostatni bit (0/1), drugie usuwa ostatni bit.
- **Niewłaściwy warunek bazowy** - `if x = 1` (nie x = 0!) zwraca 1.

## Złożoność obliczeniowa

- **Czas: O(log x)** - głębokość rekurencji to liczba bitów x.
- **Pamięć: O(log x)** - stos rekurencji.

## Linki

- [dane JSON](https://matura.lol/api/question/maturazai-informatyka-inf-2017-05/zad/2.1)
- [otwórz w wyszukiwarce](https://matura.lol/?problem=maturazai-informatyka-inf-2017-05%2Fzad%2F2.1)

## Podobne zadania

- [Zadanie 1](https://matura.lol/question/informatyka-2025-maj-matura-rozszerzona/zad/1) — Zadanie 1. Funkcja rekurencyjna Dana jest rekurencyjna funkcja przestaw, której parametrem jest nieujemna liczba całkowita: przestaw(n): r  n mod 100 a  r div
- [Zadanie 2](https://matura.lol/question/informatyka-2015-przykladowy-arkusz-cke-rozszerzona/zad/2) — Zadanie 2. (0-6) Całkowity pierwiastek kwadratowy Niech będzie dodatnią liczbą całkowitą. Całkowitym pierwiastkiem kwadratowym z liczby ݊ nazywamy dodatnią licz
- [Zadanie 5.2](https://matura.lol/question/informatyka-2015-maj-matura-stara-podstawowa-2/zad/5.2) — Zadanie 5.2. (6 pkt) Dla każdego słowa z pliku nowe.txt wypisz to słowo oraz dwie liczby rozdzielone spacją oznaczające: • liczbę wystąpień danego słowa w pliku
- [Zadanie 3](https://matura.lol/question/informatyka-2014-maj-matura-rozszerzona/zad/3) — Zadanie 3. (6 pkt) Przeanalizuj poniższy algorytm dla dodatniej liczby całkowitej n: jeżeli n = 1, to suma ← 1 w przeciwnym przypadku suma ← 1 + n i ← n - 1 dop

_Ostatnia aktualizacja danych: 2026-10-03_