{"id":"informatyka-2016-maj-matura-rozszerzona/zad/3.2","paper_id":"informatyka-2016-maj-matura-rozszerzona","number":"3.2","points":1,"ptype":"true_false","subject":"informatyka","category":"matura","year":2016,"month":"maj","level":"rozszerzona","text":"Zadanie 3.2. (0-1)\nDana jest funkcja f określona wzorem rekurencyjnym\n( )\n(\n)\n( )\n1\n4\n1\n1\ndla\n1\n1\nf\nf n\nn\nf n\n\n\n≥\n\n\nWtedy:\n1.\n( )\n1\n8\n3\nf\nP\nF\n2.\n( )\n3\n9\n4\nf\nP\nF\n3.\n(\n)\n10\n4\nf\nP\nF\n4.\n(\n)\n1\n100\n3\nf\nP\nF\nMiejsce na obliczenia.\nMIN_1R","answer":null,"answer_text":"Zadanie 3.2. (0-1)\nIII. Rozwiązywanie problemów i\npodejmowanie decyzji […], z zastosowaniem\npodejścia algorytmicznego.\n5. Rozwiązywanie problemów i podejmowanie\ndecyzji […], stosowanie podejścia algorytmicznego.\nZdający:\n9) stosuje rekurencję w prostych sytuacjach\nproblemowych.\nSchemat punktowania\n1 p. - za wskazanie czterech poprawnych odpowiedzi.\n0 p. - za odpowiedź niepełną lub błędną albo za brak odpowiedzi.\nPoprawna odpowiedź\nF, P, P, F.","solution":"## Poprawna odpowiedź\n\n**1) F, 2) P, 3) P, 4) F**\n\n## Sposób 1 - wyznaczenie cyklu funkcji\n\n**Obliczamy kolejne wartości:**\n\n- f(1) = **4**\n- f(2) = 1 / (1 - 4) = 1 / (-3) = **-1/3**\n- f(3) = 1 / (1 - (-1/3)) = 1 / (4/3) = **3/4**\n- f(4) = 1 / (1 - 3/4) = 1 / (1/4) = **4** ← powtarza się f(1)\n- f(5) = f(2) = -1/3\n- f(6) = f(3) = 3/4\n- f(7) = f(4) = 4\n\n**Funkcja jest cykliczna z okresem 3!** Wartość f(n) zależy tylko od `(n - 1) mod 3`:\n- `(n - 1) mod 3 = 0` → f(n) = **4**\n- `(n - 1) mod 3 = 1` → f(n) = **-1/3**\n- `(n - 1) mod 3 = 2` → f(n) = **3/4**\n\n## Sposób 2 - sprawdzenie poszczególnych stwierdzeń\n\n### f(8) = 1/3?\n(8 - 1) mod 3 = 7 mod 3 = 1 → f(8) = **-1/3**, NIE 1/3.\n**→ F (Fałsz).** Wartość to -1/3, nie +1/3 (uwaga na znak!).\n\n### f(9) = 3/4?\n(9 - 1) mod 3 = 8 mod 3 = 2 → f(9) = **3/4**. ✓\n**→ P (Prawda).**\n\n### f(10) = 4?\n(10 - 1) mod 3 = 9 mod 3 = 0 → f(10) = **4**. ✓\n**→ P (Prawda).**\n\n### f(100) = -1/3?\n(100 - 1) mod 3 = 99 mod 3 = 0 → f(100) = **4**, NIE -1/3.\n**→ F (Fałsz).**\n\n## Sposób 3 - implementacja Python (weryfikacja)\n\n```python\nfrom fractions import Fraction\n\ndef f(n):\nval = Fraction(4)\nfor _ in range(n - 1):\nval = Fraction(1) / (Fraction(1) - val)\nreturn val\n\nfor n in [1, 2, 3, 4, 8, 9, 10, 100]:\nprint(f\"f({n}) = {f(n)}\")\n\nWynik:\nf(1) = 4\nf(2) = -1/3\nf(3) = 3/4\nf(4) = 4\nf(8) = -1/3\nf(9) = 3/4\nf(10) = 4\nf(100) = 4\n\n## Reference informatyczny - rekurencja cykliczna\n\n> Reference - Funkcje cykliczne:\n> - Jeżeli ciąg rekurencyjny `a_{n+1} = g(a_n)` powraca do wartości startowej po k krokach (`a_{1+k} = a_1`), to ma **okres k**.\n> - Wtedy `a_n` zależy tylko od `(n - 1) mod k`.\n> - W tym zadaniu k = 3; cykl to (4, -1/3, 3/4, 4, -1/3, 3/4, ).\n>\n> Reference - Iterowane przekształcenia ułamkowe (Möbius transformations):\n> - Funkcja `g(x) = 1/(1-x)` to przekształcenie Möbiusa z okresem 3 (działa to dla bardzo wielu wartości startowych).\n> - Cyklem 3-elementowym tej funkcji są: x, 1/(1-x), (x-1)/x. Dla x=4 daje to dokładnie 4 → -1/3 → 3/4 → 4.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 3.2, max 1 pkt):\n> - **1 pkt** - wszystkie 4 odpowiedzi poprawne: F, P, P, F\n> - **0 pkt** - odpowiedź niepełna lub błędna\n\n## Typowe pułapki\n\n- **Pominięcie znaku minus** - f(8) = -1/3, a stwierdzenie mówi +1/3. Łatwo przeoczyć.\n- **Zła wartość mod dla 99** - niektórzy uczniowie zakładają `99 mod 3 ≠ 0`, ale 99 = 33·3, więc 99 mod 3 = **0**.\n- **Liczenie ręcznie do f(100)** zamiast skorzystać z okresu - strata czasu i ryzyko błędu rachunkowego.\n- **Mylenie `n` z `(n-1)`** w wyznaczaniu pozycji w cyklu - formula używa **(n-1) mod 3** bo f(1) startuje cykl.\n- **Niesprawdzenie cyklu** - niektórzy uczniowie obliczają f(8) krok po kroku, zamiast zauważyć powtarzanie po 3 iteracjach.\n\n## Złożoność obliczeniowa\n\n- Naiwne wyznaczanie f(n): O(n) iteracji.\n- Z wykorzystaniem cyklu: **O(1)** po wykryciu okresu.","image":"img/informatyka-2016-maj-matura-rozszerzona/zad-3.2.webp","solution_image":null,"topics":null,"page_from":6,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2016 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 3.2. (0-1)
Dana jest funkcja f określona wzorem rekurencyjnym
( )
(
)
( )
1
4
1
1
dla
1
1
f
f n
n
f n


≥


Wtedy:
1.
( )
1
8
3
f
P
F
2.
( )
3
9
4
f
P
F
3.
(
)
10
4
f
P
F
4.
(
)
1
100
3
f
P
F
Miejsce na obliczenia.
MIN_1R

","answer_text_html":"

Zadanie 3.2. (0-1)
III. Rozwiązywanie problemów i
podejmowanie decyzji […], z zastosowaniem
podejścia algorytmicznego.

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

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

\n
  1. stosuje rekurencję w prostych sytuacjach
\n

problemowych.
Schemat punktowania
1 p. - za wskazanie czterech poprawnych odpowiedzi.
0 p. - za odpowiedź niepełną lub błędną albo za brak odpowiedzi.
Poprawna odpowiedź
F, P, P, F.

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

Poprawna odpowiedź

\n

1) F, 2) P, 3) P, 4) F

\n

Sposób 1 - wyznaczenie cyklu funkcji

\n

Obliczamy kolejne wartości:

\n\n

Funkcja jest cykliczna z okresem 3! Wartość f(n) zależy tylko od (n - 1) mod 3:

\n\n

Sposób 2 - sprawdzenie poszczególnych stwierdzeń

\n
f(8) = 1/3?
\n

(8 - 1) mod 3 = 7 mod 3 = 1 → f(8) = -1/3, NIE 1/3.
→ F (Fałsz). Wartość to -1/3, nie +1/3 (uwaga na znak!).

\n
f(9) = 3/4?
\n

(9 - 1) mod 3 = 8 mod 3 = 2 → f(9) = 3/4. ✓
→ P (Prawda).

\n
f(10) = 4?
\n

(10 - 1) mod 3 = 9 mod 3 = 0 → f(10) = 4. ✓
→ P (Prawda).

\n
f(100) = -1/3?
\n

(100 - 1) mod 3 = 99 mod 3 = 0 → f(100) = 4, NIE -1/3.
→ F (Fałsz).

\n

Sposób 3 - implementacja Python (weryfikacja)

\n

```python
from fractions import Fraction

\n

def f(n):
val = Fraction(4)
for _ in range(n - 1):
val = Fraction(1) / (Fraction(1) - val)
return val

\n

for n in [1, 2, 3, 4, 8, 9, 10, 100]:
print(f"f({n}) = {f(n)}")

\n

Wynik:
f(1) = 4
f(2) = -1/3
f(3) = 3/4
f(4) = 4
f(8) = -1/3
f(9) = 3/4
f(10) = 4
f(100) = 4

\n

Reference informatyczny - rekurencja cykliczna

\n
Reference - Funkcje cykliczne:
- Jeżeli ciąg rekurencyjny a_{n+1} = g(a_n) powraca do wartości startowej po k krokach (a_{1+k} = a_1), to ma okres k.
- Wtedy a_n zależy tylko od (n - 1) mod k.
- W tym zadaniu k = 3; cykl to (4, -1/3, 3/4, 4, -1/3, 3/4, ).

Reference - Iterowane przekształcenia ułamkowe (Möbius transformations):
- Funkcja g(x) = 1/(1-x) to przekształcenie Möbiusa z okresem 3 (działa to dla bardzo wielu wartości startowych).
- Cyklem 3-elementowym tej funkcji są: x, 1/(1-x), (x-1)/x. Dla x=4 daje to dokładnie 4 → -1/3 → 3/4 → 4.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 3.2, max 1 pkt):
- 1 pkt - wszystkie 4 odpowiedzi poprawne: F, P, P, F
- 0 pkt - odpowiedź niepełna lub błędna
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}