# Informatyka — zadanie 2.1

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

## Treść

Zadanie 2. Analiza algorytmu

Przeanalizuj podaną funkcję pisz.

**Specyfikacja:**
Dane:
- s - napis
- n - liczba całkowita dodatnia, nie mniejsza niż długość napisu s
- k - liczba całkowita z zakresu [2 10]

Uwaga:
- dł(x) - daje w wyniku długość napisu x
- s1 + s2 - daje w wyniku złączenie napisów s1 i s2
- napis(p) - daje w wyniku napis będący zapisem dziesiętnym liczby całkowitej p

a) Uzupełnij miejsca oznaczone kropkami w drzewie wywołań funkcji pisz otrzymanym w wyniku wywołania pisz("",2,2).

b) W kwadratowych polach, przy węzłach drzewa, podaj odpowiednią kolejność wywołań funkcji pisz, tzn. przy pierwszym wywołaniu - 1, przy kolejnym - 2 itd.

Struktura drzewa wywołań pisz("",2,2):
- Korzeń: pisz("",2,2)
- pisz("0",2,2)
- pisz("00",2,2)
- pisz("01",2,2)
- pisz("1",2,2)
- ?
- ?

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

## Poprawna odpowiedź

**a) Brakujące węzły:** `pisz("10", 2, 2)` i `pisz("11", 2, 2)`.

**b) Kolejność wywołań:**

| Numer | Wywołanie |
| 1 | pisz("", 2, 2) |
| 2 | pisz("0", 2, 2) |
| 3 | pisz("00", 2, 2) |
| 4 | pisz("01", 2, 2) |
| 5 | pisz("1", 2, 2) |
| 6 | pisz("10", 2, 2) |
| 7 | pisz("11", 2, 2) |

**Drzewo z numeracją (pre-order DFS):**

[1] pisz("", 2, 2)
[2] pisz("0", 2, 2) [5] pisz("1", 2, 2)
[3] pisz("00") [4] pisz("01") [6] pisz("10") [7] pisz("11")

## Sposób 1 - symulacja rekurencji krok po kroku

Funkcja `pisz(s, n, k)`:
- jeśli `dł(s) = n` → wypisz s (warunek bazowy);
- inaczej → dla i = 0 k-1 wywołaj `pisz(s + napis(i), n, k)`.

Dla `pisz("", 2, 2)` (n=2, k=2):

**[1] pisz("", 2, 2):** dł("")=0 ≠ 2 → pętla `i=0,1`:
- i=0: wywołaj **[2] pisz("0", 2, 2)**:
- dł("0")=1 ≠ 2 → pętla i=0,1:
- i=0: **[3] pisz("00", 2, 2)** → dł("00")=2 → **wypisz "00"**.
- i=1: **[4] pisz("01", 2, 2)** → dł("01")=2 → **wypisz "01"**.
- i=1: wywołaj **[5] pisz("1", 2, 2)**:
- dł("1")=1 ≠ 2 → pętla i=0,1:
- i=0: **[6] pisz("10", 2, 2)** → dł("10")=2 → **wypisz "10"**.
- i=1: **[7] pisz("11", 2, 2)** → dł("11")=2 → **wypisz "11"**.

**Wypisany ciąg: 00, 01, 10, 11** (wszystkie binarne liczby 2-bitowe!).

## Sposób 2 - interpretacja jako pre-order DFS po drzewie pełnym

Funkcja `pisz` buduje **pełne drzewo k-arne** głębokości n. Liście to wszystkie napisy długości n nad alfabetem {0, 1, , k-1}, a wewnętrzne węzły to wszystkie krótsze prefiksy.

Kolejność wywołań to **pre-order traversal** (NLR): najpierw węzeł aktualny (wywołanie funkcji), potem rekurencyjnie poddrzewa od i=0 do i=k-1 (lewe do prawego).

**Implementacja Python (do weryfikacji):**
```python
licznik = [0]
kolejnosc = []

def pisz(s, n, k):
licznik[0] += 1
kolejnosc.append((licznik[0], s))
if len(s) == n:
print(s)
return
for i in range(k):
pisz(s + str(i), n, k)

pisz("", 2, 2)
for nr, s in kolejnosc:
print(nr, repr(s))
# 1 '' 2 '0' 3 '00' 4 '01' 5 '1' 6 '10' 7 '11'

## Reference informatyczny - pre-order DFS

> Reference - Drzewo wywołań rekurencji:
> - Każde wywołanie funkcji = węzeł drzewa. Wywołania zagnieżdżone = krawędzie.
> - Kolejność wywołań = **pre-order DFS** (NLR): najpierw węzeł, potem rekurencyjnie poddrzewa.
> - Liczba liści = liczba kombinacji ciągu długości n nad alfabetem k-elementowym = **k^n**.
> - Łączna liczba węzłów (wywołań) = 1 + k + k² + + k^n = **(k^(n+1) - 1) / (k - 1)**.

## Schemat oceniania CKE

> Klucz CKE (zadanie 2.1, max 2 pkt):
> - **2 pkt** - poprawna odpowiedź, w tym:
> - 1 pkt - poprawne uzupełnienie drzewa (pisz("10") i pisz("11"))
> - 1 pkt - prawidłowa kolejność wywołań (1-7)
> - **0 pkt** - błędna lub brak

## Typowe pułapki

- **Numerowanie tylko liści** zamiast wszystkich węzłów - kolejność powinna obejmować WSZYSTKIE wywołania.
- **Pomylenie pre-order z post-order** - w post-order: 3, 4, 2, 6, 7, 5, 1 (najpierw liście, na końcu korzeń).
- **Mylenie kolejności i=0,1** - najpierw idzie i=0 (lewa), potem i=1 (prawa).
- **Brakujące dopisanie cyfry**: pisz("") + i=1 → pisz("1"), NIE pisz("01").

## Złożoność obliczeniowa

- Liczba wywołań dla `pisz("", n, k)`: **(k^(n+1) - 1) / (k - 1)**.
- Dla pisz("", 2, 2): (2³ - 1)/(2 - 1) = 7 ✓.
- Czas pojedynczego wywołania (bez rekurencji): O(dł(s)) na konkatenację - łącznie O(n · k^n).
- Pamięć stosu rekurencji: O(n) (głębokość drzewa).

## Linki

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

## Podobne zadania

- [Zadanie 5.4](https://matura.lol/question/informatyka-2020-kwiecien-probna-rozszerzona-2/zad/5.4) — Zadanie 5.4. (0-4) Wykonaj zestawienie miesięczne (w okresie kwiecień - wrzesień 2015 roku) kosztów dolewanej wody z wodociągu. Weź pod uwagę, że cena 1 m3 (100
- [Zadanie 5.5](https://matura.lol/question/informatyka-2020-lipiec-matura-rozszerzona-2/zad/5.5) — Zadanie 5.5. (0-4) Podaj numer rejestracyjny samochodu klienta, który jako drugi zrezygnował z kolejki, oraz podaj, ilu łącznie klientów zrezygnowało z kolejki.
- [Zadanie 6.5](https://matura.lol/question/informatyka-2020-czerwiec-matura-rozszerzona-2/zad/6.5) — Zadanie 6.5. (0-4) Kapitan przy załadunku płacił za towar, a przy wyładunku otrzymywał za niego zapłatę. a) Przyjmij, że kapitan przed pierwszym rejsem miał w k
- [Zadanie 7.4](https://matura.lol/question/informatyka-2024-maj-matura-rozszerzona/zad/7.4) — Zadanie 7.4. (0-3) Hurtownia ma system premiowania klientów hurtowych. Klient otrzymuje przy zakupie rabat, którego wysokość zależy od łącznej ilości jabłek zak

_Ostatnia aktualizacja danych: 2026-10-03_