# Informatyka — zadanie 2.3

> Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2017-05/zad/2.3
> 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

## Treść

Zadanie 2.3. (0-2)
Podaj najmniejszą liczbę całkowitą x większą od 100, dla której wynikiem wywołania
licz(x) będzie 0.
Odpowiedź:
Miejsce na obliczenia
Wypełnia
egzaminator
Nr zadania
2.1.
2.2.
2.3.
Maks. liczba pkt.
2
2
2
Uzyskana liczba pkt.
MIN_1R

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

## Poprawna odpowiedź

**x = 135**

135 w binarnym to **10000111** (8 bitów, 4 jedynki, 4 zera). licz(135) = 4 - 4 = 0.

## Sposób 1 - wykorzystanie wzoru z 2.1

Z zadania 2.1 wiemy: **licz(x) = (liczba jedynek w bin(x)) - (liczba zer w bin(x))**.

licz(x) = 0 oznacza: **liczba jedynek = liczba zer** w zapisie binarnym x.

**Wniosek:** x musi mieć parzystą liczbę bitów (2k bitów: k jedynek i k zer). Najmłodszy bit może być 0 lub 1, najstarszy zawsze 1.

## Sposób 2 - szukamy najmniejszego x > 100

100 w binarnym = 1100100 (7 bitów). Szukamy x > 100 z równą liczbą 0 i 1.

Liczby 8-bitowe (najmniejsza = 128 = 10000000) zakres: 128-255.

Dla x = 128, 129, , 135 sprawdzamy:
- 128 = 10000000: 1 jedynka, 7 zer → licz = -6
- 129 = 10000001: 2 j, 6 z → -4
- 130 = 10000010: 2 j, 6 z → -4
- 131 = 10000011: 3 j, 5 z → -2
- 132 = 10000100: 2 j, 6 z → -4
- 133 = 10000101: 3 j, 5 z → -2
- 134 = 10000110: 3 j, 5 z → -2
- **135 = 10000111: 4 j, 4 z → licz = 0** ✓

Mniejsze liczby? Sprawdźmy też 7-bitowe (64-127):
- Liczba 7-bitowa ma 7 bitów; równa liczba 0 i 1 wymaga **parzystej liczby bitów** - niemożliwe!
- Wszystkie 7-bitowe mają licz(x) parzyste? Tak: 7 = 1 + 6 lub 3 + 4 lub 5 + 2 lub 7 + 0 → różnica nieparzysta. Niemożliwe licz = 0.

Więc x > 100 z licz = 0 musi być co najmniej 8-bitowe, czyli x ≥ 128. Sprawdzone - najmniejsze takie x to **135**.

## Sposób 3 - weryfikacja symulacją (Python)

```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 range(101, 200):
if licz(x) == 0:
print(x)
break
# wynik: 135

Symulacja licz(135) krok po kroku:
- licz(135): bit=1 → w = licz(67), wynik = w+1
- licz(67): bit=1 → w = licz(33), wynik = w+1
- licz(33): bit=1 → w = licz(16), wynik = w+1
- licz(16): bit=0 → w = licz(8), wynik = w-1
- licz(8): bit=0 → w = licz(4), wynik = w-1
- licz(4): bit=0 → w = licz(2), wynik = w-1
- licz(2): bit=0 → w = licz(1), wynik = w-1
- licz(1) = 1
- licz(2) = 0; licz(4) = -1; licz(8) = -2; licz(16) = -3
- licz(33) = -3 + 1 = -2
- licz(67) = -2 + 1 = -1
- licz(135) = -1 + 1 = **0** ✓

## Reference algorytmiczny - bilans bitów

> Reference - bilans bitów w zapisie binarnym:
> - Suma j + z = liczba bitów (długość zapisu).
> - Różnica j - z = licz(x) (z zadania 2.1).
> - Aby j = z konieczne: parzysta długość zapisu. Najmniejsze x o takiej własności i > 100 to liczba 8-bitowa, najmłodsza spełniająca to 10000111 = 135.

## Schemat oceniania CKE

> Klucz CKE (zadanie 2.3, max 2 pkt):
> - **2 pkt** - za **135**
> - **1 pkt** - za inną liczbę x > 100, dla której licz(x) = 0 (np. 139, 141, 142, 147, )
> - **0 pkt** - błąd lub brak

## Typowe pułapki

- **Próba 100-127** - żadna 7-bitowa liczba nie da licz = 0 (nieparzysta długość).
- **Pominięcie wymogu „>100"** - 51 = 110011 daje licz = 0, ale 51 < 100.
- **Błąd rachunkowy w zliczeniu bitów** - 135 = 128 + 4 + 2 + 1 = 10000111 (bit 7 + bity 0-2).

## Złożoność obliczeniowa

- Bezpośrednie szukanie x w pętli: O((x_wynik - 100) · log x_wynik) ≈ O(35 · 8) = O(280) - trywialne.

## Linki

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

## 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_