# Informatyka — zadanie 2.3

> Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2019-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 2019 (rozszerzona)
- rok: 2019
- poziom: rozszerzona
- typ: open
- punkty: 2
- działy: Programowanie i algorytmika, programowanie

## Treść

Kontekst - patrz zadania 2.1 i 2.2 (funkcja pisz).

Podaj wzór na łączną liczbę wywołań funkcji pisz w wyniku wywołania pisz("", n, k).

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

## Poprawna odpowiedź

**Wzór na łączną liczbę wywołań:**

$$
T(n, k) = 1 + k + k^2 + k^3 + \ldots + k^n = \frac{k^{n+1} - 1}{k - 1}
$$

(dla k = 1 wzór ten się degeneruje; wtedy T(n, 1) = n + 1.)

Alternatywne równoważne zapisy:
- `(k^(n+1) - 1) / (k - 1)`
- `(1 - k^(n+1)) / (1 - k)`
- `1 + k + k^2 + + k^n`
- `Σ k^i dla i = 0 n`

## Sposób 1 - analiza poziomami drzewa

Funkcja `pisz("", n, k)` buduje **pełne drzewo k-arne głębokości n**. Każde wywołanie na poziomie i (gdzie i = 0, 1, , n) odpowiada jednemu napisowi długości i.

**Liczba wywołań na poziomie i = k^i** (liczba ciągów długości i nad alfabetem k-elementowym):

| Poziom | Liczba wywołań |
| 0 (korzeń) | k⁰ = 1 |
| 1 | k¹ = k |
| 2 | k² |
| n (liście) | kⁿ |

**Suma wszystkich poziomów:**

$$T(n,k) = \sum_{i=0}^{n} k^i = 1 + k + k^2 + \ldots + k^n$$

## Sposób 2 - wzór sumy szeregu geometrycznego

Zastosujmy wzór na sumę szeregu geometrycznego z pierwszym wyrazem a=1 i ilorazem q=k:

$$S_n = a \cdot \frac{q^{n+1} - 1}{q - 1} = \frac{k^{n+1} - 1}{k - 1}, \quad k \ne 1$$

**Weryfikacja na danych z zadania 2.2:**
- pisz("", 3, 2): (2⁴ - 1)/(2 - 1) = 15 ✓
- pisz("", 2, 3): (3³ - 1)/(3 - 1) = 26/2 = 13 ✓
- pisz("", 2, 2): (2³ - 1)/(2 - 1) = 7 ✓ (z zad. 2.1)

## Sposób 3 - wzór rekurencyjny i jego rozwinięcie

Niech T(n, k) = liczba wywołań pisz(s, n, k), gdzie dł(s) = 0 (lub równoważnie pisz(s, n-dł(s), k) dla dowolnego s).

**Rekurencja:**
- Bazowo: T(0, k) = 1 (tylko jedno wywołanie - od razu wypisuje).
- Ogólnie: T(n, k) = 1 (samo wywołanie) + k razy poddrzewa: T(n, k) = 1 + k · T(n-1, k).

Rozwiązanie:
- T(0, k) = 1
- T(1, k) = 1 + k
- T(2, k) = 1 + k(1 + k) = 1 + k + k²
- T(n, k) = 1 + k + k² + + kⁿ ✓

## Reference informatyczny - suma szeregu geometrycznego

> Reference - Szereg geometryczny:
> - Suma: 1 + q + q² + + qⁿ = **(qⁿ⁺¹ - 1) / (q - 1)** dla q ≠ 1.
> - Dla q = 1: suma = n + 1.
> - Liczba węzłów pełnego drzewa k-arnego głębokości n: **(kⁿ⁺¹ - 1) / (k - 1)**.
> - Liczba liści: **kⁿ**.
> - Liczba węzłów wewnętrznych: T(n,k) - kⁿ = (kⁿ - 1) / (k - 1).

## Schemat oceniania CKE

> Klucz CKE (zadanie 2.3, max 2 pkt):
> - **2 pkt** - pełna poprawna odpowiedź (dowolna z równoważnych form)
> - **1 pkt** - liczba mniejsza o 1 lub indeks szeregu n-1 zamiast n (np. 1+k+ +k^(n-1) zamiast 1+k+ +kⁿ)
> - **0 pkt** - błędna lub brak
>
> Uwaga: odpowiedź może być zapisana także w postaci sumy ze znakiem Σ.

## Typowe pułapki

- **Liczenie tylko liści (kⁿ) zamiast wszystkich wywołań** - typowy błąd: "funkcja wypisuje kⁿ napisów więc tyle jest wywołań".
- **Pomylenie n+1 i n w wykładniku**: 1+k+ +k^(n-1) (suma do n-1) zamiast do kⁿ.
- **Dzielenie przez (k-1) i zapominanie o przypadku k=1** (chociaż w treści mamy k ∈ [2 10], więc k ≥ 2).
- **Mylenie głębokości drzewa**: drzewo ma głębokość n, ale jego poziomy są ponumerowane 0, 1, , n - czyli n+1 poziomów.

## Złożoność obliczeniowa

- T(n, k) = **Θ(kⁿ)** - dominujący człon w sumie geometrycznej.
- Dla k=2: T(n,2) = 2ⁿ⁺¹ - 1 - wykładnicza w n.
- Pamięć stosu rekurencji: O(n).

## Linki

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

## Podobne zadania

- [Zadanie 3.3](https://matura.lol/question/informatyka-2018-maj-matura-stara-rozszerzona/zad/3.3) — Zadanie 3.3. (0-1) Dana jest funkcja rekurencyjna: ሺݔሻ= ൜1 ݈݀ܽ ݔ≤1 ݔ+݂ ሺݔ ݀݅ ݒ 2ሻ ݈݀ܽ ݔ> 1 gdzie x jest nieujemną liczbą całkowitą, a operacja x div 2 oznacza c
- [Zadanie 1](https://matura.lol/question/informatyka-2011-maj-matura-podstawowa/zad/1) — Zadanie 1. Zegar (5 pkt) Na jednej z uczelni informatycznych nad wejściem do auli umieszczony został elektroniczny zegar odliczający sekundy od rozpoczęcia wykł
- [Zadanie 5](https://matura.lol/question/informatyka-2010-maj-matura-podstawowa-2/zad/5) — Zadanie 5. Upusty (10 pkt) Producenci A i B sprzedają pewien towar po 12,00 zł za sztukę. Producent A daje odbiorcom 15% upustu przy zakupie do 500 sztuk oraz 2

_Ostatnia aktualizacja danych: 2026-10-03_