{"id":"informatyka-2026-maj-matura-rozszerzona/zad/1.3","paper_id":"informatyka-2026-maj-matura-rozszerzona","number":"1.3","points":3,"ptype":"open","subject":"informatyka","category":"matura","year":2026,"month":"maj","level":"rozszerzona","text":"Zadanie 1.3. (0-3)\nUzupełnij tabelę. W drugiej kolumnie podaj liczbę wywołań rekurencyjnych funkcji A dla\nkażdej wartości n podanej w tabeli (drugiego argumentu wywołania funkcji, pierwszy jest\nnieistotny w tym zadaniu). W trzeciej kolumnie podaj wyrażenie, którego wartość jest równa\ndrugiemu argumentowi funkcji w i-tym wywołaniu rekurencyjnym dla wszystkich wartości i\nwiększych bądź równych 1 i mniejszych bądź równych całkowitej liczbie wywołań.\nn - drugi argument\nwywołania funkcji\nliczba wywołań\nrekurencyjnych\nwartość drugiego argumentu A w i-tym\nwywołaniu rekurencyjnym\n8\n3\n8\n2i ( lub 23 ̶ i\n)\n2k\n2k - 1\ngdzie k jest pewną liczbą całkowitą dodatnią większą od 2.\nMiejsce na obliczenia (brudnopis)\n1.3.\n0-1-\n2-3\nMINP-R0_100","answer":null,"answer_text":"Zadanie 1.3. (0-3)\nWymagania ogólne\nWymagania szczegółowe\nI. Rozumienie, analizowanie\ni rozwiązywanie problemów.\nII. Programowanie i rozwiązywanie\nproblemów z wykorzystaniem komputera\ni innych urządzeń cyfrowych.\nZdający:\nI.4) do realizacji rozwiązania problemu\ndobiera odpowiednią metodę lub technikę\nalgorytmiczną i struktury danych.\nI+II.3) objaśnia, a także porównuje\npodstawowe metody i techniki\nalgorytmiczne oraz struktury danych,\nwykorzystując przy tym przykłady\nproblemów i algorytmów, w szczególności:\nb) rekurencję.\nP.I.3) sprawdza poprawność działania\nalgorytmów dla przykładowych danych.\nP.II.1) projektuje i programuje rozwiązania\nproblemów z różnych dziedzin […].\nZasady oceniania\n3 pkt - odpowiedź poprawna w 4 polach tabeli.\n2 pkt - odpowiedź poprawna w 3 polach tabeli.\n1 pkt - odpowiedź poprawna w 2 polach tabeli.\n0 pkt - odpowiedź niepoprawna albo brak rozwiązania.\nPoprawna odpowiedź\nliczba wywołań\nrekurencyjnych\nwartość drugiego\nargumentu A w i-tym\nwywołaniu rekurencyjnym\n3\n8\n2i ( lub 23 ̶ i\n)\nk\n2k ̶ i\nk - 1\n2k ̶ i - 1 ( lub ⌊\n2k-1\n2i ⌋)\nZasady oceniania rozwiązań zadań","solution":"| n | liczba wywołań | drugi argument w i-tym wywołaniu | |---|---|---| | 8 | 3 | 8/2ⁱ (lub 2³⁻ⁱ) | | 2ᵏ | **k** | **2ᵏ⁻ⁱ** | | 2ᵏ − 1 | **k − 1** | **2ᵏ⁻ⁱ − 1** |","image":"img/informatyka-2026-maj-matura-rozszerzona/zad-1.3.webp","solution_image":null,"topics":"rekurencja, analiza algorytmu, zlozonosc logarytmiczna","page_from":6,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturaonline","text_source":"ocr","source_label":"Informatyka · Matura · maj 2026 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 1.3. (0-3)
Uzupełnij tabelę. W drugiej kolumnie podaj liczbę wywołań rekurencyjnych funkcji A dla
każdej wartości n podanej w tabeli (drugiego argumentu wywołania funkcji, pierwszy jest
nieistotny w tym zadaniu). W trzeciej kolumnie podaj wyrażenie, którego wartość jest równa
drugiemu argumentowi funkcji w i-tym wywołaniu rekurencyjnym dla wszystkich wartości i
większych bądź równych 1 i mniejszych bądź równych całkowitej liczbie wywołań.
n - drugi argument
wywołania funkcji
liczba wywołań
rekurencyjnych
wartość drugiego argumentu A w i-tym
wywołaniu rekurencyjnym
8
3
8
2i ( lub 23 ̶ i
)
2k
2k - 1
gdzie k jest pewną liczbą całkowitą dodatnią większą od 2.
Miejsce na obliczenia (brudnopis)
1.3.
0-1-
2-3
MINP-R0_100

","answer_text_html":"

Zadanie 1.3. (0-3)
Wymagania ogólne
Wymagania szczegółowe
I. Rozumienie, analizowanie
i rozwiązywanie problemów.
II. Programowanie i rozwiązywanie
problemów z wykorzystaniem komputera
i innych urządzeń cyfrowych.
Zdający:
I.4) do realizacji rozwiązania problemu
dobiera odpowiednią metodę lub technikę
algorytmiczną i struktury danych.
I+II.3) objaśnia, a także porównuje
podstawowe metody i techniki
algorytmiczne oraz struktury danych,
wykorzystując przy tym przykłady
problemów i algorytmów, w szczególności:
b) rekurencję.
P.I.3) sprawdza poprawność działania
algorytmów dla przykładowych danych.
P.II.1) projektuje i programuje rozwiązania
problemów z różnych dziedzin […].
Zasady oceniania
3 pkt - odpowiedź poprawna w 4 polach tabeli.
2 pkt - odpowiedź poprawna w 3 polach tabeli.
1 pkt - odpowiedź poprawna w 2 polach tabeli.
0 pkt - odpowiedź niepoprawna albo brak rozwiązania.
Poprawna odpowiedź
liczba wywołań
rekurencyjnych
wartość drugiego
argumentu A w i-tym
wywołaniu rekurencyjnym
3
8
2i ( lub 23 ̶ i
)
k
2k ̶ i
k - 1
2k ̶ i - 1 ( lub ⌊
2k-1
2i ⌋)
Zasady oceniania rozwiązań zadań

","solutions":[{"source":"maturaonline","label":"matura-online.pl","kind":"text","html":"

| n | liczba wywołań | drugi argument w i-tym wywołaniu | |---|---|---| | 8 | 3 | 8/2ⁱ (lub 2³⁻ⁱ) | | 2ᵏ | k | 2ᵏ⁻ⁱ | | 2ᵏ − 1 | k − 1 | 2ᵏ⁻ⁱ − 1 |

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

Poprawna odpowiedź: dla n = 3 → 3 wywołania; dla n = 2ᵏ → k+1 wywołań; wartość drugiego argumentu w i-tym wywołaniu: dla n = 8 → 2^(3-i), ogólnie dla n = 2ᵏ → 2^(k-i); ostatnia komórka (dla n = 2ᵏ - 1): 2^(k-i) - 1

\n

Liczba wywołań dla n = 3. $3$ nieparzyste $\\Rightarrow$ argument $\\tfrac{3-1}{2}=1$: mamy $A(\\cdot,1)$ - koniec. Zliczając wywołania z tabeli (jak w przykładzie z zadania) otrzymujemy 3 wywołania rekurencyjne.

\n

Liczba wywołań dla n = 2ᵏ. Argument jest cały czas parzysty, dzielimy przez 2: $2^k\\to2^{k-1}\\to\\dots\\to2^1\\to2^0=1$. Od $2^k$ do $2^0$ jest $k$ kroków dzielenia, a ostatnie wywołanie kończące ($n=1$) daje łącznie k + 1 wywołań.

\n

Wartość drugiego argumentu w i-tym wywołaniu. Dla $n=2^k$ w kroku $i$ argument zmalał $i$ razy przez połowienie: $\\;2^{k}/2^{i}=2^{\\,k-i}$. Dla $n=8=2^3$ daje to $2^{\\,3-i}$.

\n

Ostatnia komórka (dla n = 2ᵏ - 1). Gdy $n=2^k-1$ (liczba nieparzysta, same jedynki w zapisie binarnym), w każdym kroku stosujemy gałąź $\\tfrac{n-1}{2}$: $2^k-1\\to 2^{k-1}-1\\to\\dots$, więc w $i$-tym wywołaniu argument wynosi $\\mathbf{2^{\\,k-i}-1}$.

\n

Zasady oceniania CKE

\n"}]}