{"id":"informatyka-2017-maj-matura-rozszerzona/zad/2.2","paper_id":"informatyka-2017-maj-matura-rozszerzona","number":"2.2","points":2,"ptype":"closed","subject":"informatyka","category":"matura","year":2017,"month":"maj","level":"rozszerzona","text":"Zadanie 2.2. (0-2)\nDana jest dodatnia liczba całkowita k. Jaka jest najmniejsza dodatnia liczba całkowita x, dla\nktórej obliczanie wartości licz(x) wymaga dokładnie k wywołań funkcji licz, licząc także\npierwsze wywołanie licz(x)? Podkreśl prawidłową odpowiedź.\nPrzykład: obliczenie licz(13) wymaga dokładnie 4 wywołań funkcji licz.\nA) x = k2\nB) x = 2k-1\nC) x = k+1\nD) x = 2k","answer":"B","answer_text":"Zadanie 2.2. (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;\n18) oblicza liczbę operacji wykonywanych\nprzez algorytm;\nSchemat punktowania\n2 p. - za prawidłową odpowiedź 2k-1 .\n1 p. - za odpowiedź: 2k.\n0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.\nPoprawna odpowiedź:\n2k-1","solution":"## Poprawna odpowiedź\n\n**B: x = 2^(k-1)**\n\n## Sposób 1 - analiza głębokości rekurencji\n\nFunkcja `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:\n\nx → x div 2 → (x div 2) div 2 → → 1\n\nTo dokładnie **liczba bitów x w zapisie binarnym** = ⌊log₂ x⌋ + 1.\n\nDla dokładnie k wywołań chcemy: ⌊log₂ x⌋ + 1 = k, czyli **⌊log₂ x⌋ = k - 1**, czyli x ma dokładnie k bitów.\n\nNajmniejsza liczba o k bitach to **2^(k-1)** (np. 1, 10, 100, 1000, w binarnym = 1, 2, 4, 8, ).\n\n## Sposób 2 - weryfikacja na przykładach\n\n### k = 1 wywołanie → x = 1\nNajmniejszy x dla 1 wywołania: x=1 (warunek bazowy). Sprawdzenie wzorów:\n- A: k² = 1 ✓\n- B: 2^(k-1) = 2^0 = 1 ✓\n- C: k+1 = 2 (za duże, x=1 wystarczy)\n- D: 2^k = 2 (za duże)\n\nDla k=1 dwa wzory pasują, więc trzeba większego k:\n\n### k = 4 wywołania (z przykładu w treści: licz(13) wymaga 4 wywołań)\n13 = 1101 (4 bity). Najmniejszy x z 4 bitami:\n- 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 ✓\n- A: k² = 16 = 10000₂ (5 bitów) - za duże\n- C: k+1 = 5 = 101₂ (3 bity, czyli 3 wywołania) - za mało\n- D: 2^k = 16 (5 bitów) - za duże\n\n**Najmniejszy x z 4 wywołaniami = 8 = 2^(k-1).** ✓ Wzór B poprawny.\n\n### k = 5\n- B: 2^4 = 16 = 10000₂ (5 bitów) ✓\n- D: 2^5 = 32 = 100000₂ (6 bitów = 6 wywołań) ✗\n\n## Sposób 3 - dlaczego inne opcje błędne\n\n| Opcja | Wzór | Dlaczego błędna |\n| A | k² | k² rośnie kwadratowo, log₂(k²) = 2·log₂ k ≠ k-1 |\n| **B** | **2^(k-1)** | **POPRAWNA** - to najmniejsza liczba o k bitach |\n| C | k+1 | k+1 ma w bin ok. log₂(k+1) bitów ≪ k |\n| D | 2^k | 2^k ma k+1 bitów → k+1 wywołań (o jedno za dużo) |\n\n## Reference algorytmiczny - głębokość rekurencji binarnej\n\n> Reference - Rekurencja po dzieleniu na 2:\n> - Funkcja typu f(x) = f(x div 2) + ma głębokość log₂(x) + 1.\n> - Najmniejsza liczba o n bitach to 2^(n-1).\n> - Największa liczba o n bitach to 2^n - 1.\n> - Liczba k-bitowa: 2^(k-1) ≤ x ≤ 2^k - 1.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 2.2, max 2 pkt):\n> - **2 pkt** - za odpowiedź **B (x = 2^(k-1))**\n> - **1 pkt** - za 2^k (opcja D - wykazuje zrozumienie, ale przesunięcie o 1)\n> - **0 pkt** - A, C albo brak\n\n## Typowe pułapki\n\n- **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].\n- **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.\n- **Pomylenie kierunku log** - log₂(x) to wykładnik, nie liczba bitów (różnica 1).\n\n## Złożoność obliczeniowa\n\n- Liczba wywołań rekurencyjnych w licz(x): **⌊log₂ x⌋ + 1** (czyli liczba bitów x).\n- Czas każdego wywołania: O(1). Łączny czas: **O(log x)**.\n- Pamięć stosu: O(log x).","image":"img/informatyka-2017-maj-matura-rozszerzona/zad-2.2.webp","solution_image":null,"topics":null,"page_from":5,"source":"ocr","answer_source":"maturazai","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.2. (0-2)
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ź.
Przykład: obliczenie licz(13) wymaga dokładnie 4 wywołań funkcji licz.
A) x = k2
B) x = 2k-1
C) x = k+1
D) x = 2k

","answer_text_html":"

Zadanie 2.2. (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;

\n
  1. oblicza liczbę operacji wykonywanych
\n

przez algorytm;
Schemat punktowania
2 p. - za prawidłową odpowiedź 2k-1 .
1 p. - za odpowiedź: 2k.
0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.
Poprawna odpowiedź:
2k-1

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

Poprawna odpowiedź

\n

B: x = 2^(k-1)

\n

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

\n

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:

\n

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

\n

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

\n

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

\n

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

\n

Sposób 2 - weryfikacja na przykładach

\n
k = 1 wywołanie → x = 1
\n

Najmniejszy x dla 1 wywołania: x=1 (warunek bazowy). Sprawdzenie wzorów:

\n\n

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

\n
k = 4 wywołania (z przykładu w treści: licz(13) wymaga 4 wywołań)
\n

13 = 1101 (4 bity). Najmniejszy x z 4 bitami:

\n\n

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

\n
k = 5
\n\n

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

\n

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

\n

Reference algorytmiczny - głębokość rekurencji binarnej

\n
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.
\n

Schemat oceniania CKE

\n
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
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}