# Informatyka — zadanie 2.2

> Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2017-05/zad/2.2
> 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: closed
- punkty: 2
- działy: Programowanie i algorytmika

## Treść

Kontekst - patrz zadanie 2.1.

Przykład: obliczenie licz(13) wymaga dokładnie 4 wywołań funkcji licz.

Dana jest dodatnia liczba całkowita k. Jaka jest najmniejsza dodatnia liczba całkowita x, dla której obliczanie wartości licz(x) wymaga dokładnie k wywołań funkcji licz, licząc także pierwsze wywołanie licz(x)? Podkreśl prawidłową odpowiedź.

A. x = k²
B. x = 2^(k-1)
C. x = k+1
D. x = 2^k

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

## Poprawna odpowiedź

**B: x = 2^(k-1)**

## Sposób 1 - analiza głębokości rekurencji

Funkcja `licz(x)` wywołuje się rekurencyjnie aż osiągnie x = 1. Każde wywołanie dzieli x przez 2 (`x div 2`). Liczba wywołań to długość ciągu:

x → x div 2 → (x div 2) div 2 → → 1

To dokładnie **liczba bitów x w zapisie binarnym** = ⌊log₂ x⌋ + 1.

Dla dokładnie k wywołań chcemy: ⌊log₂ x⌋ + 1 = k, czyli **⌊log₂ x⌋ = k - 1**, czyli x ma dokładnie k bitów.

Najmniejsza liczba o k bitach to **2^(k-1)** (np. 1, 10, 100, 1000, w binarnym = 1, 2, 4, 8, ).

## Sposób 2 - weryfikacja na przykładach

### k = 1 wywołanie → x = 1
Najmniejszy x dla 1 wywołania: x=1 (warunek bazowy). Sprawdzenie wzorów:
- A: k² = 1 ✓
- B: 2^(k-1) = 2^0 = 1 ✓
- C: k+1 = 2 (za duże, x=1 wystarczy)
- D: 2^k = 2 (za duże)

Dla k=1 dwa wzory pasują, więc trzeba większego k:

### k = 4 wywołania (z przykładu w treści: licz(13) wymaga 4 wywołań)
13 = 1101 (4 bity). Najmniejszy x z 4 bitami:
- B: 2^(4-1) = **2^3 = 8** = 1000₂ (4 bity). 8 div 2 = 4 (3 bity), 4 div 2 = 2 (2 bity), 2 div 2 = 1 (1 bit). Wywołania: licz(8), licz(4), licz(2), licz(1) = 4 ✓
- A: k² = 16 = 10000₂ (5 bitów) - za duże
- C: k+1 = 5 = 101₂ (3 bity, czyli 3 wywołania) - za mało
- D: 2^k = 16 (5 bitów) - za duże

**Najmniejszy x z 4 wywołaniami = 8 = 2^(k-1).** ✓ Wzór B poprawny.

### k = 5
- B: 2^4 = 16 = 10000₂ (5 bitów) ✓
- D: 2^5 = 32 = 100000₂ (6 bitów = 6 wywołań) ✗

## Sposób 3 - dlaczego inne opcje błędne

| Opcja | Wzór | Dlaczego błędna |
| A | k² | k² rośnie kwadratowo, log₂(k²) = 2·log₂ k ≠ k-1 |
| **B** | **2^(k-1)** | **POPRAWNA** - to najmniejsza liczba o k bitach |
| C | k+1 | k+1 ma w bin ok. log₂(k+1) bitów ≪ k |
| D | 2^k | 2^k ma k+1 bitów → k+1 wywołań (o jedno za dużo) |

## Reference algorytmiczny - głębokość rekurencji binarnej

> Reference - Rekurencja po dzieleniu na 2:
> - Funkcja typu f(x) = f(x div 2) + ma głębokość log₂(x) + 1.
> - Najmniejsza liczba o n bitach to 2^(n-1).
> - Największa liczba o n bitach to 2^n - 1.
> - Liczba k-bitowa: 2^(k-1) ≤ x ≤ 2^k - 1.

## Schemat oceniania CKE

> Klucz CKE (zadanie 2.2, max 2 pkt):
> - **2 pkt** - za odpowiedź **B (x = 2^(k-1))**
> - **1 pkt** - za 2^k (opcja D - wykazuje zrozumienie, ale przesunięcie o 1)
> - **0 pkt** - A, C albo brak

## Typowe pułapki

- **Pomylenie 2^k z 2^(k-1)** - częsty błąd off-by-one. Dla k wywołań x musi mieć dokładnie k bitów. Liczby k-bitowe to [2^(k-1), 2^k - 1].
- **Niezliczenie pierwszego wywołania** - treść mówi „licząc także pierwsze wywołanie licz(x)", więc dla x=1 mamy 1 wywołanie, nie 0.
- **Pomylenie kierunku log** - log₂(x) to wykładnik, nie liczba bitów (różnica 1).

## Złożoność obliczeniowa

- Liczba wywołań rekurencyjnych w licz(x): **⌊log₂ x⌋ + 1** (czyli liczba bitów x).
- Czas każdego wywołania: O(1). Łączny czas: **O(log x)**.
- Pamięć stosu: O(log x).

## Odpowiedź

**Odpowiedź:** B

_Rozwiązanie AI z maturazai.pl, weryfikowane z kluczem CKE — źródło nieoficjalne._

## Linki

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

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