# Informatyka — zadanie 2.2

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

## Treść

Kontekst - patrz zadanie 2.1 (funkcja pisz).

Uzupełnij poniższą tabelę - przeanalizuj podane w niej wywołania funkcji pisz. Podaj napisy wypisywane w wyniku wywołania funkcji pisz z zadanymi parametrami oraz łączną liczbę wywołań tej funkcji.

Pierwsze wywołanie funkcji pisz | Napisy wypisane w wyniku wywołania funkcji pisz | Łączna liczba wywołań funkcji pisz
pisz("", 3, 2) | ? | ?
pisz("", 2, 3) | ? | ?

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

## Poprawna odpowiedź

| Wywołanie | Wypisane napisy | Łączna liczba wywołań |
| pisz("", 3, 2) | **000, 001, 010, 011, 100, 101, 110, 111** | **15** |
| pisz("", 2, 3) | **00, 01, 02, 10, 11, 12, 20, 21, 22** | **13** |

## Sposób 1 - analiza pisz("", 3, 2)

**Co wypisze?** Funkcja generuje wszystkie napisy długości n=3 nad alfabetem {0, 1} (bo k=2). Liczba liści = 2³ = 8 napisów.

W porządku pre-order (najpierw i=0, potem i=1):
"" → "0" → "00" → "000" (wypisz)
"001" (wypisz)
"01" → "010" (wypisz)
"011" (wypisz)
"1" → "10" → "100" (wypisz)
"101" (wypisz)
"11" → "110" (wypisz)
"111" (wypisz)

Wypisane: **000, 001, 010, 011, 100, 101, 110, 111** (binarne liczby 0-7).

**Liczba wywołań - liczenie po poziomach:**
- poziom 0 (""): 1 wywołanie
- poziom 1 ("0", "1"): 2 wywołania
- poziom 2 ("00", "01", "10", "11"): 4 wywołania
- poziom 3 (liście, 8 napisów): 8 wywołań

Suma: **1 + 2 + 4 + 8 = 15** wywołań.

## Sposób 2 - analiza pisz("", 2, 3)

Funkcja generuje wszystkie napisy długości n=2 nad alfabetem {0, 1, 2} (k=3). Liczba liści = 3² = 9.

W porządku pre-order (i=0, potem 1, potem 2):
"" → "0" → "00" (wypisz)
"01" (wypisz)
"02" (wypisz)
"1" → "10" (wypisz)
"11" (wypisz)
"12" (wypisz)
"2" → "20" (wypisz)
"21" (wypisz)
"22" (wypisz)

Wypisane: **00, 01, 02, 10, 11, 12, 20, 21, 22**.

**Liczba wywołań po poziomach:**
- poziom 0: 1 wywołanie
- poziom 1: 3 wywołania ("0", "1", "2")
- poziom 2 (liście): 9 wywołań

Suma: **1 + 3 + 9 = 13**.

## Sposób 3 - implementacja Python (weryfikacja)

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

licznik = [0]; wynik = []
pisz("", 3, 2, wynik, licznik)
print(wynik)
# ['000', '001', '010', '011', '100', '101', '110', '111']
print("liczba wywołań:", licznik[0]) # 15

licznik = [0]; wynik = []
pisz("", 2, 3, wynik, licznik)
print(wynik)
# ['00', '01', '02', '10', '11', '12', '20', '21', '22']
print("liczba wywołań:", licznik[0]) # 13

## Reference informatyczny - wzór na liczbę wywołań

> Reference - Sumowanie szeregu geometrycznego:
> - Liczba wywołań pisz("", n, k) = 1 + k + k² + + kⁿ.
> - To suma szeregu geometrycznego: **(kⁿ⁺¹ - 1) / (k - 1)** dla k ≠ 1.
> - Dla n=3, k=2: (2⁴ - 1)/(2 - 1) = 15 ✓.
> - Dla n=2, k=3: (3³ - 1)/(3 - 1) = 26/2 = 13 ✓.
> - Liczba liści (wypisanych napisów) = **kⁿ**.

## Schemat oceniania CKE

> Klucz CKE (zadanie 2.2, max 2 pkt):
> - **2 pkt** - wszystkie 4 pola tabeli poprawne
> - **1 pkt** - za każde 2 poprawnie uzupełnione pola
> - **0 pkt** - błędna lub brak
>
> Uwaga: teksty wypisane mogą być w jednym wierszu lub jeden pod drugim.

## Typowe pułapki

- **Pomylenie kolejności wypisywania** - pre-order daje wzrost "leksykograficzny": 000 < 001 < 010 < 011
- **Liczenie tylko liści (8 lub 9) zamiast wszystkich wywołań** - wynikają z tego błędne 8 (zamiast 15) lub 9 (zamiast 13).
- **Liczenie tylko węzłów wewnętrznych** - pomijanie liści.
- **Pomylenie kolejności n i k**: pisz("", 3, 2) ≠ pisz("", 2, 3).
- **Brak wypisania niektórych ścieżek** - łatwo zgubić jakąś gałąź.

## Złożoność obliczeniowa

- Czas: **O((kⁿ⁺¹ - 1)/(k - 1))** = **Θ(kⁿ)** dla k > 1.
- Pamięć stosu: O(n).
- Dla pisz("", 3, 2): 15 wywołań, 8 wypisań.
- Dla pisz("", 2, 3): 13 wywołań, 9 wypisań.

## Linki

- [dane JSON](https://matura.lol/api/question/maturazai-informatyka-inf-2019-05/zad/2.2)
- [otwórz w wyszukiwarce](https://matura.lol/?problem=maturazai-informatyka-inf-2019-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_