{"id":"informatyka-2012-maj-matura-podstawowa/zad/1","paper_id":"informatyka-2012-maj-matura-podstawowa","number":"1","points":null,"ptype":"open","subject":"informatyka","category":"matura","year":2012,"month":"maj","level":"podstawowa","text":"Zadanie 1. Fibonacci (7 pkt)\nPoniższa funkcja rekurencyjna Fib oblicza k-ty wyraz ciągu Fibonacciego.\nDane: k - liczba naturalna większa od zera\nFunkcja\n\nFib k\n1. Jeżeli\n1\nk  lub\n2\nk \n, to wynikiem jest 1.\n2. Jeżeli\n2\nk \n, to wynikiem jest\n\n\n\n\n1\n2\nFib k\nFib k\n\n\n\nPrzykład:\nZgodnie z powyższą definicją funkcji Fib mamy:\n\n\n\n\n\n\n\n\n4\n3\n2\n2\n1\n2\n1\n1\n1\n3\nFib\nFib\nFib\nFib\nFib\nFib\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\na) Uzupełnij tabelę, wpisując dla podanych argumentów k wartości obliczane przez funkcję\nFib .\nk\n\nFib k\n1\n1\n2\n1\n3\n2\n8\n11\nPoziom podstawowy - część I\n3\nb) Wywołanie funkcji\n\nFib k dla\n2\nk \npowoduje dwa kolejne wywołania tej funkcji\nz mniejszymi argumentami, które z kolei mogą wymagać kolejnych wywołań Fib , itd.\nProces ten można zilustrować za pomocą tzw. drzewa wywołań rekurencyjnych. Poniżej\nprezentujemy drzewo wywołań rekurencyjnych dla\n5\nk \n. W węzłach drzewa znajdują się\nargumenty wywołań.\nNarysuj drzewo wywołań rekurencyjnych dla\n\n6\nFib\n5\n3\n4\n3\n2\n2\n1\n2\n1\n4\nPoziom podstawowy - część I\nc) k-ty wyraz ciągu Fibonacciego można wyznaczyć iteracyjnie w następujący sposób:\nDane: k - liczba naturalna większa od zera\nAlgorytm:\n1.\n1,\n_1\n1,\n2\nFi\nFi\ni\n\n\n\n2. dopóki i\nk\n\npom\nFi\n\n_1\nFi\nFi\nFi\n\n\n_1\nFi\npom\n\n1\ni\ni\n\n3. wypisz Fi\nZdefiniujmy następujący ciąg:\n\nPierwszy i drugi wyraz ciągu są równe 1.\n\nJeśli\n2\nk \ni k jest parzyste, to k-ty wyraz jest sumą trzech wyrazów\ngo poprzedzających.\n\nJeśli\n2\nk \ni k jest nieparzyste, to k-ty wyraz jest równy wyrazowi o numerze \n\n1\nk \nKilka pierwszych wyrazów tego ciągu podano w poniższej tabeli.\nk\n1\n2\n3\n4\n5\n6\n7\n8\nk-ty wyraz\n1\n1\n1\n3\n3\n7\n7\n17\nZapisz algorytm (w postaci listy kroków, schematu blokowego lub w wybranym języku\nprogramowania), który dla danej wartości k wyznacza k-ty wyraz opisanego powyżej ciągu.\nZapisz rozwiązanie w postaci iteracyjnej.\nSpecyfikacja:\nDane: k - liczba naturalna większa od zera\nWynik: k-ty wyraz ciągu zdefiniowanego powyżej\nAlgorytm:\nPoziom podstawowy - część I\n5\nNr zadania\n1a\n1b\n1c\nMaks. liczba pkt\n2\n1\n4\nWypełnia\negzaminator Uzyskana liczba pkt\n6\nPoziom podstawowy - część I","answer":null,"answer_text":"Zadanie 1. a) (0-2)\nObszar standardów\nOpis wymagań\nWiadomości i rozumienie\nZnajomość podstawowych algorytmów i technik\nalgorytmicznych - rekurencji (I.7)\nPoprawna odpowiedź:\nk\nFib(k)\n8\n21\n11\n89\n2 p. - za podanie dwóch poprawnych odpowiedzi\n1 p. - za podanie jednej poprawnej odpowiedzi\n0 p. - za podanie niepoprawnej odpowiedzi albo jej brak\nZadanie 1. b) (0-1)\nWiadomości i rozumienie\nWyodrębnianie elementów składowych algorytmu (I.7)\nPoprawna odpowiedź:\n1 p. - za poprawne narysowanie drzewa wywołań\n0 p. - za niepoprawny rysunek drzewa wywołań albo brak odpowiedzi\nZadanie 1. c) (0-4)\nKorzystanie z informacji\nZastosowanie podstawowych algorytmów w rozwiązywaniu\nproblemów informatycznych (II.5)\n4\n3\n2\n2\n1\n5\n3\n4\n3\n2\n2\n1\n2\n1\n6\nKryteria oceniania odpowiedzi - poziom podstawowy\n3\nPrzykładowe poprawne odpowiedzi:\nPrzykład 1.\n1,\n_1\n1,\n2\nFi\nFi\ni\n\n\n\ndopóki i\nk\n\njeżeli \n\n1 mod 2\n0\ni \n\nto\npom\nFi\n\n_1\n_ 2\nFi\nFi\nFi\nFi\n\n\n\n_ 2\n_1\nFi\nFi\n\n_1\nFi\npom\n\nw przeciwnym razie\n_ 2\n_1\nFi\nFi\n\n_1\nFi\nFi\n\n1\ni\ni\n\nwypisz Fi\nPrzykład 2\n\n\n1\n1,\n2\n1\nTab\nTab\n\n\n3\ni \ndopóki i\nk\n\njeżeli mod 2\n0\ni\n\nto\n\n\n\n\n\n\n\n3\n2\n1\nTab i\nTab i\nTab i\nTab i\n\n\n\n\n\n\nw przeciwnym razie\n\n\n1\nTab i\nTab i\n\n\n1\ni\ni\n\nwypisz\n\nTab i\n4 p. - za w pełni poprawny algorytm, w tym:\nza poprawne rozróżnianie wyrazów parzystych i nieparzystych - 1 p.\nza poprawne obliczanie wyróżnianych wyrazów nieparzystych - 1 p.\nza poprawne obliczanie wyróżnianych wyrazów parzystych - 1 p.\nza poprawną konstrukcję pętli umożliwiającej obliczanie wszystkich elementów (wraz\nz trzema pierwszymi elementami) - 1 p.\n0 p. - za błędny algorytm, algorytm rekurencyjny albo brak odpowiedzi","solution":null,"image":"img/informatyka-2012-maj-matura-podstawowa/zad-1.webp","solution_image":null,"topics":null,"page_from":2,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":null,"text_source":"ocr","source_label":"Informatyka · Matura · maj 2012 (podstawowa)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 1. Fibonacci (7 pkt)
Poniższa funkcja rekurencyjna Fib oblicza k-ty wyraz ciągu Fibonacciego.
Dane: k - liczba naturalna większa od zera
Funkcja

Fib k

\n
  1. Jeżeli
\n

1
k  lub
2
k 
, to wynikiem jest 1.

\n
  1. Jeżeli
\n

2
k 
, to wynikiem jest




1
2
Fib k
Fib k



Przykład:
Zgodnie z powyższą definicją funkcji Fib mamy:








4
3
2
2
1
2
1
1
1
3
Fib
Fib
Fib
Fib
Fib
Fib















a) Uzupełnij tabelę, wpisując dla podanych argumentów k wartości obliczane przez funkcję
Fib .
k

Fib k
1
1
2
1
3
2
8
11
Poziom podstawowy - część I
3
b) Wywołanie funkcji

Fib k dla
2
k 
powoduje dwa kolejne wywołania tej funkcji
z mniejszymi argumentami, które z kolei mogą wymagać kolejnych wywołań Fib , itd.
Proces ten można zilustrować za pomocą tzw. drzewa wywołań rekurencyjnych. Poniżej
prezentujemy drzewo wywołań rekurencyjnych dla
5
k 
. W węzłach drzewa znajdują się
argumenty wywołań.
Narysuj drzewo wywołań rekurencyjnych dla

6
Fib
5
3
4
3
2
2
1
2
1
4
Poziom podstawowy - część I
c) k-ty wyraz ciągu Fibonacciego można wyznaczyć iteracyjnie w następujący sposób:
Dane: k - liczba naturalna większa od zera
Algorytm:
1.
1,
_1
1,
2
Fi
Fi
i


\n
  1. dopóki i
\n

k

pom
Fi

_1
Fi
Fi
Fi


_1
Fi
pom

1
i
i


\n
  1. wypisz Fi
\n

Zdefiniujmy następujący ciąg:

Pierwszy i drugi wyraz ciągu są równe 1.

Jeśli
2
k 
i k jest parzyste, to k-ty wyraz jest sumą trzech wyrazów
go poprzedzających.

Jeśli
2
k 
i k jest nieparzyste, to k-ty wyraz jest równy wyrazowi o numerze 

1
k 
Kilka pierwszych wyrazów tego ciągu podano w poniższej tabeli.
k
1
2
3
4
5
6
7
8
k-ty wyraz
1
1
1
3
3
7
7
17
Zapisz algorytm (w postaci listy kroków, schematu blokowego lub w wybranym języku
programowania), który dla danej wartości k wyznacza k-ty wyraz opisanego powyżej ciągu.
Zapisz rozwiązanie w postaci iteracyjnej.
Specyfikacja:
Dane: k - liczba naturalna większa od zera
Wynik: k-ty wyraz ciągu zdefiniowanego powyżej
Algorytm:
Poziom podstawowy - część I
5
Nr zadania
1a
1b
1c
Maks. liczba pkt
2
1
4
Wypełnia
egzaminator Uzyskana liczba pkt
6
Poziom podstawowy - część I

","answer_text_html":"

Zadanie 1. a) (0-2)
Obszar standardów
Opis wymagań
Wiadomości i rozumienie
Znajomość podstawowych algorytmów i technik
algorytmicznych - rekurencji (I.7)
Poprawna odpowiedź:
k
Fib(k)
8
21
11
89
2 p. - za podanie dwóch poprawnych odpowiedzi
1 p. - za podanie jednej poprawnej odpowiedzi
0 p. - za podanie niepoprawnej odpowiedzi albo jej brak
Zadanie 1. b) (0-1)
Wiadomości i rozumienie
Wyodrębnianie elementów składowych algorytmu (I.7)
Poprawna odpowiedź:
1 p. - za poprawne narysowanie drzewa wywołań
0 p. - za niepoprawny rysunek drzewa wywołań albo brak odpowiedzi
Zadanie 1. c) (0-4)
Korzystanie z informacji
Zastosowanie podstawowych algorytmów w rozwiązywaniu
problemów informatycznych (II.5)
4
3
2
2
1
5
3
4
3
2
2
1
2
1
6
Kryteria oceniania odpowiedzi - poziom podstawowy
3
Przykładowe poprawne odpowiedzi:
Przykład 1.
1,
_1
1,
2
Fi
Fi
i



dopóki i
k

jeżeli 

1 mod 2
0
i 

to
pom
Fi

_1
_ 2
Fi
Fi
Fi
Fi



_ 2
_1
Fi
Fi

_1
Fi
pom

w przeciwnym razie
_ 2
_1
Fi
Fi

_1
Fi
Fi

1
i
i

wypisz Fi
Przykład 2


1
1,
2
1
Tab
Tab


3
i 
dopóki i
k

jeżeli mod 2
0
i

to







3
2
1
Tab i
Tab i
Tab i
Tab i






w przeciwnym razie


1
Tab i
Tab i


1
i
i

wypisz

Tab i
4 p. - za w pełni poprawny algorytm, w tym:
za poprawne rozróżnianie wyrazów parzystych i nieparzystych - 1 p.
za poprawne obliczanie wyróżnianych wyrazów nieparzystych - 1 p.
za poprawne obliczanie wyróżnianych wyrazów parzystych - 1 p.
za poprawną konstrukcję pętli umożliwiającej obliczanie wszystkich elementów (wraz
z trzema pierwszymi elementami) - 1 p.
0 p. - za błędny algorytm, algorytm rekurencyjny albo brak odpowiedzi

","solutions":[]}