{"id":"informatyka-2019-maj-matura-rozszerzona/zad/2.2","paper_id":"informatyka-2019-maj-matura-rozszerzona","number":"2.2","points":2,"ptype":"open","subject":"informatyka","category":"matura","year":2019,"month":"maj","level":"rozszerzona","text":"Zadanie 2.2. (0-2)\nUzupełnij poniższą tabelę - przeanalizuj podane w niej wywołania funkcji pisz. Podaj napisy\nwypisywane w wyniku wywołania funkcji pisz z zadanymi parametrami oraz łączną liczbę\nwywołań tej funkcji.\nPierwsze wywołanie\nfunkcji pisz\nNapisy wypisane w wyniku wywołania\nfunkcji pisz\nŁączna liczba\nwywołań funkcji\npisz\npisz(\"\", 3, 2)\npisz(\"\", 2, 3)","answer":null,"answer_text":"Zadanie 2.2. (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;\n11) opisuje podstawowe algorytmy\ni stosuje:\na) algorytmy na tekstach, […]\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ź, w tym:\n1 p. - za każde poprawnie uzupełnione dwa pola tabeli.\nUwaga: teksty wypisane przez funkcję mogą być zapisane w jednym wierszu lub jeden pod\ndrugim - nie zmienia to oceny.\n0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.\nPoprawna odpowiedź\nwywołanie\nfunkcji\ntekst wypisany przez\nfunkcję pisz()\nliczba wywołań\nfunkcji pisz()\npisz(\"\", 3, 2)\n000\n001\n010\n011\n100\n101\n110\n111\n15 (1+2+4+8)\npisz(\"\", 2, 3)\n00\n01\n02\n10\n11\n12\n20\n21\n22\n13 (1+3+9)","solution":"## Poprawna odpowiedź\n\n| Wywołanie | Wypisane napisy | Łączna liczba wywołań |\n| pisz(\"\", 3, 2) | **000, 001, 010, 011, 100, 101, 110, 111** | **15** |\n| pisz(\"\", 2, 3) | **00, 01, 02, 10, 11, 12, 20, 21, 22** | **13** |\n\n## Sposób 1 - analiza pisz(\"\", 3, 2)\n\n**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.\n\nW porządku pre-order (najpierw i=0, potem i=1):\n\"\" → \"0\" → \"00\" → \"000\" (wypisz)\n\"001\" (wypisz)\n\"01\" → \"010\" (wypisz)\n\"011\" (wypisz)\n\"1\" → \"10\" → \"100\" (wypisz)\n\"101\" (wypisz)\n\"11\" → \"110\" (wypisz)\n\"111\" (wypisz)\n\nWypisane: **000, 001, 010, 011, 100, 101, 110, 111** (binarne liczby 0-7).\n\n**Liczba wywołań - liczenie po poziomach:**\n- poziom 0 (\"\"): 1 wywołanie\n- poziom 1 (\"0\", \"1\"): 2 wywołania\n- poziom 2 (\"00\", \"01\", \"10\", \"11\"): 4 wywołania\n- poziom 3 (liście, 8 napisów): 8 wywołań\n\nSuma: **1 + 2 + 4 + 8 = 15** wywołań.\n\n## Sposób 2 - analiza pisz(\"\", 2, 3)\n\nFunkcja generuje wszystkie napisy długości n=2 nad alfabetem {0, 1, 2} (k=3). Liczba liści = 3² = 9.\n\nW porządku pre-order (i=0, potem 1, potem 2):\n\"\" → \"0\" → \"00\" (wypisz)\n\"01\" (wypisz)\n\"02\" (wypisz)\n\"1\" → \"10\" (wypisz)\n\"11\" (wypisz)\n\"12\" (wypisz)\n\"2\" → \"20\" (wypisz)\n\"21\" (wypisz)\n\"22\" (wypisz)\n\nWypisane: **00, 01, 02, 10, 11, 12, 20, 21, 22**.\n\n**Liczba wywołań po poziomach:**\n- poziom 0: 1 wywołanie\n- poziom 1: 3 wywołania (\"0\", \"1\", \"2\")\n- poziom 2 (liście): 9 wywołań\n\nSuma: **1 + 3 + 9 = 13**.\n\n## Sposób 3 - implementacja Python (weryfikacja)\n\n```python\ndef pisz(s, n, k, wynik, licznik):\nlicznik[0] += 1\nif len(s) == n:\nwynik.append(s)\nreturn\nfor i in range(k):\npisz(s + str(i), n, k, wynik, licznik)\n\nlicznik = [0]; wynik = []\npisz(\"\", 3, 2, wynik, licznik)\nprint(wynik)\n# ['000', '001', '010', '011', '100', '101', '110', '111']\nprint(\"liczba wywołań:\", licznik[0]) # 15\n\nlicznik = [0]; wynik = []\npisz(\"\", 2, 3, wynik, licznik)\nprint(wynik)\n# ['00', '01', '02', '10', '11', '12', '20', '21', '22']\nprint(\"liczba wywołań:\", licznik[0]) # 13\n\n## Reference informatyczny - wzór na liczbę wywołań\n\n> Reference - Sumowanie szeregu geometrycznego:\n> - Liczba wywołań pisz(\"\", n, k) = 1 + k + k² + + kⁿ.\n> - To suma szeregu geometrycznego: **(kⁿ⁺¹ - 1) / (k - 1)** dla k ≠ 1.\n> - Dla n=3, k=2: (2⁴ - 1)/(2 - 1) = 15 ✓.\n> - Dla n=2, k=3: (3³ - 1)/(3 - 1) = 26/2 = 13 ✓.\n> - Liczba liści (wypisanych napisów) = **kⁿ**.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 2.2, max 2 pkt):\n> - **2 pkt** - wszystkie 4 pola tabeli poprawne\n> - **1 pkt** - za każde 2 poprawnie uzupełnione pola\n> - **0 pkt** - błędna lub brak\n>\n> Uwaga: teksty wypisane mogą być w jednym wierszu lub jeden pod drugim.\n\n## Typowe pułapki\n\n- **Pomylenie kolejności wypisywania** - pre-order daje wzrost \"leksykograficzny\": 000 < 001 < 010 < 011\n- **Liczenie tylko liści (8 lub 9) zamiast wszystkich wywołań** - wynikają z tego błędne 8 (zamiast 15) lub 9 (zamiast 13).\n- **Liczenie tylko węzłów wewnętrznych** - pomijanie liści.\n- **Pomylenie kolejności n i k**: pisz(\"\", 3, 2) ≠ pisz(\"\", 2, 3).\n- **Brak wypisania niektórych ścieżek** - łatwo zgubić jakąś gałąź.\n\n## Złożoność obliczeniowa\n\n- Czas: **O((kⁿ⁺¹ - 1)/(k - 1))** = **Θ(kⁿ)** dla k > 1.\n- Pamięć stosu: O(n).\n- Dla pisz(\"\", 3, 2): 15 wywołań, 8 wypisań.\n- Dla pisz(\"\", 2, 3): 13 wywołań, 9 wypisań.","image":"img/informatyka-2019-maj-matura-rozszerzona/zad-2.2.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.2. (0-2)
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)

","answer_text_html":"

Zadanie 2.2. (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 podstawowe algorytmy
\n

i stosuje:
a) algorytmy na tekstach, […]

\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ź, w tym:
1 p. - za każde poprawnie uzupełnione dwa pola tabeli.
Uwaga: teksty wypisane przez funkcję mogą być zapisane w jednym wierszu lub jeden pod
drugim - nie zmienia to oceny.
0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.
Poprawna odpowiedź
wywołanie
funkcji
tekst wypisany przez
funkcję pisz()
liczba wywołań
funkcji pisz()
pisz("", 3, 2)
000
001
010
011
100
101
110
111
15 (1+2+4+8)
pisz("", 2, 3)
00
01
02
10
11
12
20
21
22
13 (1+3+9)

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

Poprawna odpowiedź

\n

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

\n

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

\n

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.

\n

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)

\n

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

\n

Liczba wywołań - liczenie po poziomach:

\n\n

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

\n

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

\n

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

\n

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)

\n

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

\n

Liczba wywołań po poziomach:

\n\n

Suma: 1 + 3 + 9 = 13.

\n

Sposób 3 - implementacja Python (weryfikacja)

\n

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

\n

licznik = [0]; wynik = []
pisz("", 3, 2, wynik, licznik)
print(wynik)

\n

['000', '001', '010', '011', '100', '101', '110', '111']

\n

print("liczba wywołań:", licznik[0]) # 15

\n

licznik = [0]; wynik = []
pisz("", 2, 3, wynik, licznik)
print(wynik)

\n

['00', '01', '02', '10', '11', '12', '20', '21', '22']

\n

print("liczba wywołań:", licznik[0]) # 13

\n

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

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

Schemat oceniania CKE

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

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}