{"id":"informatyka-2019-maj-matura-rozszerzona/zad/2.3","paper_id":"informatyka-2019-maj-matura-rozszerzona","number":"2.3","points":2,"ptype":"open","subject":"informatyka","category":"matura","year":2019,"month":"maj","level":"rozszerzona","text":"Zadanie 2.3. (0-2)\nPodaj wzór na łączną liczbę wywołań funkcji pisz w wyniku wywołania pisz(\"\", n, k).\nWypełnia\negzaminator\nNr zadania\n2.1.\n2.2.\n2.3.\nMaks. liczba pkt.\n2\n2\n2\nUzyskana liczba pkt.\nMIN_1R","answer":null,"answer_text":"Zadanie 2.3. (0-2)\nWymagania ogólne\nWymagania szczegółowe\nIII. Rozwiązywanie problemów\ni podejmowanie decyzji […]\nz zastosowaniem podejścia algorytmicznego.\n5. Rozwiązywanie problemów\ni podejmowanie decyzji […], stosowanie\npodejścia algorytmicznego.\nZdający:\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 poprawną odpowiedź,\n1 p. - w przypadku podania w odpowiedzi liczby mniejszej o 1 lub gdy ostatni element szeregu\nw odpowiedzi ma indeks n-1 zamiast n (np. 1+k+k2+…+kn-1 zamiast 1+k+k2+…+kn),\n0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.\nUwaga: odpowiedź może być zapisana także w postaci sumy (ze znakiem ∑ ).\nPoprawna odpowiedź\n(kn+1 - 1)/(k - 1) lub (1 - kn+1)/(1- k) lub 1 + k + k2 + … + kn","solution":"## Poprawna odpowiedź\n\n**Wzór na łączną liczbę wywołań:**\n\n$$\nT(n, k) = 1 + k + k^2 + k^3 + \\ldots + k^n = \\frac{k^{n+1} - 1}{k - 1}\n$$\n\n(dla k = 1 wzór ten się degeneruje; wtedy T(n, 1) = n + 1.)\n\nAlternatywne równoważne zapisy:\n- `(k^(n+1) - 1) / (k - 1)`\n- `(1 - k^(n+1)) / (1 - k)`\n- `1 + k + k^2 + + k^n`\n- `Σ k^i dla i = 0 n`\n\n## Sposób 1 - analiza poziomami drzewa\n\nFunkcja `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.\n\n**Liczba wywołań na poziomie i = k^i** (liczba ciągów długości i nad alfabetem k-elementowym):\n\n| Poziom | Liczba wywołań |\n| 0 (korzeń) | k⁰ = 1 |\n| 1 | k¹ = k |\n| 2 | k² |\n| n (liście) | kⁿ |\n\n**Suma wszystkich poziomów:**\n\n$$T(n,k) = \\sum_{i=0}^{n} k^i = 1 + k + k^2 + \\ldots + k^n$$\n\n## Sposób 2 - wzór sumy szeregu geometrycznego\n\nZastosujmy wzór na sumę szeregu geometrycznego z pierwszym wyrazem a=1 i ilorazem q=k:\n\n$$S_n = a \\cdot \\frac{q^{n+1} - 1}{q - 1} = \\frac{k^{n+1} - 1}{k - 1}, \\quad k \\ne 1$$\n\n**Weryfikacja na danych z zadania 2.2:**\n- pisz(\"\", 3, 2): (2⁴ - 1)/(2 - 1) = 15 ✓\n- pisz(\"\", 2, 3): (3³ - 1)/(3 - 1) = 26/2 = 13 ✓\n- pisz(\"\", 2, 2): (2³ - 1)/(2 - 1) = 7 ✓ (z zad. 2.1)\n\n## Sposób 3 - wzór rekurencyjny i jego rozwinięcie\n\nNiech 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).\n\n**Rekurencja:**\n- Bazowo: T(0, k) = 1 (tylko jedno wywołanie - od razu wypisuje).\n- Ogólnie: T(n, k) = 1 (samo wywołanie) + k razy poddrzewa: T(n, k) = 1 + k · T(n-1, k).\n\nRozwiązanie:\n- T(0, k) = 1\n- T(1, k) = 1 + k\n- T(2, k) = 1 + k(1 + k) = 1 + k + k²\n- T(n, k) = 1 + k + k² + + kⁿ ✓\n\n## Reference informatyczny - suma szeregu geometrycznego\n\n> Reference - Szereg geometryczny:\n> - Suma: 1 + q + q² + + qⁿ = **(qⁿ⁺¹ - 1) / (q - 1)** dla q ≠ 1.\n> - Dla q = 1: suma = n + 1.\n> - Liczba węzłów pełnego drzewa k-arnego głębokości n: **(kⁿ⁺¹ - 1) / (k - 1)**.\n> - Liczba liści: **kⁿ**.\n> - Liczba węzłów wewnętrznych: T(n,k) - kⁿ = (kⁿ - 1) / (k - 1).\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 2.3, max 2 pkt):\n> - **2 pkt** - pełna poprawna odpowiedź (dowolna z równoważnych form)\n> - **1 pkt** - liczba mniejsza o 1 lub indeks szeregu n-1 zamiast n (np. 1+k+ +k^(n-1) zamiast 1+k+ +kⁿ)\n> - **0 pkt** - błędna lub brak\n>\n> Uwaga: odpowiedź może być zapisana także w postaci sumy ze znakiem Σ.\n\n## Typowe pułapki\n\n- **Liczenie tylko liści (kⁿ) zamiast wszystkich wywołań** - typowy błąd: \"funkcja wypisuje kⁿ napisów więc tyle jest wywołań\".\n- **Pomylenie n+1 i n w wykładniku**: 1+k+ +k^(n-1) (suma do n-1) zamiast do kⁿ.\n- **Dzielenie przez (k-1) i zapominanie o przypadku k=1** (chociaż w treści mamy k ∈ [2 10], więc k ≥ 2).\n- **Mylenie głębokości drzewa**: drzewo ma głębokość n, ale jego poziomy są ponumerowane 0, 1, , n - czyli n+1 poziomów.\n\n## Złożoność obliczeniowa\n\n- T(n, k) = **Θ(kⁿ)** - dominujący człon w sumie geometrycznej.\n- Dla k=2: T(n,2) = 2ⁿ⁺¹ - 1 - wykładnicza w n.\n- Pamięć stosu rekurencji: O(n).","image":"img/informatyka-2019-maj-matura-rozszerzona/zad-2.3.webp","solution_image":null,"topics":null,"page_from":5,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2019 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 2.3. (0-2)
Podaj wzór na łączną liczbę wywołań funkcji pisz w wyniku wywołania pisz("", n, k).
Wypełnia
egzaminator
Nr zadania
2.1.
2.2.
2.3.
Maks. liczba pkt.
2
2
2
Uzyskana liczba pkt.
MIN_1R

","answer_text_html":"

Zadanie 2.3. (0-2)
Wymagania ogólne
Wymagania szczegółowe
III. Rozwiązywanie problemów
i podejmowanie decyzji […]
z zastosowaniem podejścia algorytmicznego.

\n
  1. Rozwiązywanie problemów
\n

i podejmowanie decyzji […], stosowanie
podejścia algorytmicznego.
Zdający:

\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 poprawną odpowiedź,
1 p. - w przypadku podania w odpowiedzi liczby mniejszej o 1 lub gdy ostatni element szeregu
w odpowiedzi ma indeks n-1 zamiast n (np. 1+k+k2+…+kn-1 zamiast 1+k+k2+…+kn),
0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.
Uwaga: odpowiedź może być zapisana także w postaci sumy (ze znakiem ∑ ).
Poprawna odpowiedź
(kn+1 - 1)/(k - 1) lub (1 - kn+1)/(1- k) lub 1 + k + k2 + … + kn

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

Poprawna odpowiedź

\n

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

\n
T(n,k)=1+k+k2+k3+…+kn=kn+1−1k−1
\n

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

\n

Alternatywne równoważne zapisy:

\n\n

Sposób 1 - analiza poziomami drzewa

\n

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.

\n

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

\n

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

\n

Suma wszystkich poziomów:

\n
T(n,k)=∑i=0nki=1+k+k2+…+kn
\n

Sposób 2 - wzór sumy szeregu geometrycznego

\n

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

\n
Sn=a·qn+1−1q−1=kn+1−1k−1,k≠1
\n

Weryfikacja na danych z zadania 2.2:

\n\n

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

\n

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

\n

Rekurencja:

\n\n

Rozwiązanie:

\n\n

Reference informatyczny - suma szeregu geometrycznego

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

Schemat oceniania CKE

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

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}