{"id":"informatyka-2011-maj-matura-rozszerzona/zad/1","paper_id":"informatyka-2011-maj-matura-rozszerzona","number":"1","points":null,"ptype":"open","subject":"informatyka","category":"matura","year":2011,"month":"maj","level":"rozszerzona","text":"Zadanie 1. Długość napisów binarnych (7 pkt)\nOpisana poniżej funkcja rekurencyjna wyznacza, dla liczby naturalnej\n, długość napisu\nuzyskanego przez sklejenie binarnych reprezentacji liczb naturalnych od 1 do\n0\nn \n1\nn \nFunkcja\n\nsklej n\nkrok 1. jeśli\n, to podaj 0 jako wynik i zakończ działanie\n1\n\nn\nkrok 2. jeśli n parzysta, to wynikiem jest\n\n\n1\n2\n/ 2\nn\nsklej n\n\n\nkrok 3. jeśli n nieparzysta, to wynikiem jest\n\n\n\n\n\n\n\n\n1\n1 / 2\n1\nn\nsklej\nn\nsklej\nn\n\n\n\n\n/ 2\nWykonaj polecenia a)-c):\na) Wykonanie funkcji sklej można przedstawić w postaci drzewa wywołań rekurencyjnych\nilustrującego wszystkie wywołania funkcji po jej uruchomieniu dla zadanego argumentu.\nPoniższy rysunek przedstawia takie drzewo dla wywołania\n\n5\nsklej\n\n5\nsklej\n\n2\nsklej\n\n3\nsklej\nNarysuj analogiczne drzewo dla wywołania\n\n7\nsklej\n\n1\nsklej\n\n1\nsklej\n\n2\nsklej\n\n1\nsklej\nPoziom rozszerzony - część I\n3\nb) Uzupełnij poniższą tabelę, podając wartości funkcji sklej dla wskazanych argumentów.\nn\n\nsklej n\n1\n0\n2\n1\n3\n4\n5\n6\nc) Chcemy wypełnić tablicę \n\n1\ns\nn w taki sposób, że \n\ns i\nsklej i\n\ndla każdego 1\ni\nn\n\nPodaj algorytm wypełniający tablicę s odpowiednimi wartościami bez wywoływania\nfunkcji sklej, tzn. bez użycia rekurencji. Zauważ, że jeśli poprawnie wyliczone są już\nwartości \n\n\n1 , ,\n1\ns\ns i \n, to można z nich skorzystać przy wyznaczaniu \ns i .\nZapisz swój algorytm w postaci listy kroków, schematu blokowego lub w wybranym\njęzyku programowania, który wybrałeś/aś na egzamin.\nSpecyfikacja:\nDane: liczba naturalna\n0\nn \nWynik: tablica \n\n1\ns\nn o wartościach \n\ns i\nsklej i\n\n, dla 1\ni\nn\n\nAlgorytm:\nPoziom rozszerzony - część I\n4\nPoziom rozszerzony - część I\n5","answer":null,"answer_text":"Zadanie 1. a) (0-1)\nObszar standardów\nOpis wymagań\nWiadomości i rozumienie\nZnajomość wybranych struktur danych\nPoprawna odpowiedź\n1 p. - za podanie poprawnej odpowiedzi\n0 p. - za podanie niepoprawnej odpowiedzi albo jej brak\nZadanie 1. b) (0-2)\nKorzystanie z informacji\nObliczenie kolejnych wartości funkcji dla wskazanych\nargumentów\nPoprawna odpowiedź\nn\n( )\nsklej n\n1\n0\n2\n1\n3\n3\n4\n5\n5\n8\n6\n11\n2 p. - za poprawne uzupełnienie wartości funkcji w tabeli\n1 p. - za uzupełnienie wartości funkcji w tabelce z jednym błędem\n0 p. - za wypełnioną tabelę z więcej niż jednym błędem albo brak odpowiedzi\n( )\n4\nsklej\n( )\n3\nsklej\n( )\n2\nsklej\n( )1\nsklej\n( )\n2\nsklej\n( )1\nsklej\n( )\n7\nsklej\n( )\n1\nsklej\nKryteria oceniania odpowiedzi\n3\nZadanie 1. c) (0-4)\nKorzystanie z informacji\nDobranie najlepszego algorytmu i odpowiednich struktur\ndanych (w tym struktury dynamicznej) do rozwiązania\npostawionego problemu\nPrzykładowy algorytm\n#include \nusing namespace std;\nint main()\n{\nint n;\nint * s;\ncin >> n;\ns = new int[n+1];\ns[1] = 0;\nfor(int i=2;i<=n;++i)\n{\nif(i%2 == 0)\ns[i] = i-1+2*s[i/2];\nelse\ns[i] = i-1+s[(i-1)/2]+s[(i+1)/2];\n}\n}\n4 p. - za w pełni poprawny algorytm, w tym:\nza poprawną inicjację zmiennych - 1 p.\nza poprawne obliczanie elementów parzystych - 1 p.\nza poprawne obliczanie elementów nieparzystych - 1 p.\nza poprawne podstawienia w tablicy - 1 p.\n0 p. - za błędny algorytm albo brak odpowiedzi\nKryteria oceniania odpowiedzi\n4","solution":null,"image":"img/informatyka-2011-maj-matura-rozszerzona/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 2011 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 1. Długość napisów binarnych (7 pkt)
Opisana poniżej funkcja rekurencyjna wyznacza, dla liczby naturalnej
, długość napisu
uzyskanego przez sklejenie binarnych reprezentacji liczb naturalnych od 1 do
0
n 
1
n 
Funkcja

sklej n
krok 1. jeśli
, to podaj 0 jako wynik i zakończ działanie
1

n
krok 2. jeśli n parzysta, to wynikiem jest


1
2
/ 2
n
sklej n


krok 3. jeśli n nieparzysta, to wynikiem jest








1
1 / 2
1
n
sklej
n
sklej
n




/ 2
Wykonaj polecenia a)-c):
a) Wykonanie funkcji sklej można przedstawić w postaci drzewa wywołań rekurencyjnych
ilustrującego wszystkie wywołania funkcji po jej uruchomieniu dla zadanego argumentu.
Poniższy rysunek przedstawia takie drzewo dla wywołania

5
sklej

5
sklej

2
sklej

3
sklej
Narysuj analogiczne drzewo dla wywołania

7
sklej

1
sklej

1
sklej

2
sklej

1
sklej
Poziom rozszerzony - część I
3
b) Uzupełnij poniższą tabelę, podając wartości funkcji sklej dla wskazanych argumentów.
n

sklej n
1
0
2
1
3
4
5
6
c) Chcemy wypełnić tablicę 

1
s
n w taki sposób, że 

s i
sklej i

dla każdego 1
i
n

Podaj algorytm wypełniający tablicę s odpowiednimi wartościami bez wywoływania
funkcji sklej, tzn. bez użycia rekurencji. Zauważ, że jeśli poprawnie wyliczone są już
wartości 


1 , ,
1
s
s i 
, to można z nich skorzystać przy wyznaczaniu 
s i .
Zapisz swój algorytm w postaci listy kroków, schematu blokowego lub w wybranym
języku programowania, który wybrałeś/aś na egzamin.
Specyfikacja:
Dane: liczba naturalna
0
n 
Wynik: tablica 

1
s
n o wartościach 

s i
sklej i

, dla 1
i
n

Algorytm:
Poziom rozszerzony - część I
4
Poziom rozszerzony - część I
5

","answer_text_html":"

Zadanie 1. a) (0-1)
Obszar standardów
Opis wymagań
Wiadomości i rozumienie
Znajomość wybranych struktur danych
Poprawna odpowiedź
1 p. - za podanie poprawnej odpowiedzi
0 p. - za podanie niepoprawnej odpowiedzi albo jej brak
Zadanie 1. b) (0-2)
Korzystanie z informacji
Obliczenie kolejnych wartości funkcji dla wskazanych
argumentów
Poprawna odpowiedź
n
( )
sklej n
1
0
2
1
3
3
4
5
5
8
6
11
2 p. - za poprawne uzupełnienie wartości funkcji w tabeli
1 p. - za uzupełnienie wartości funkcji w tabelce z jednym błędem
0 p. - za wypełnioną tabelę z więcej niż jednym błędem albo brak odpowiedzi
( )
4
sklej
( )
3
sklej
( )
2
sklej
( )1
sklej
( )
2
sklej
( )1
sklej
( )
7
sklej
( )
1
sklej
Kryteria oceniania odpowiedzi
3
Zadanie 1. c) (0-4)
Korzystanie z informacji
Dobranie najlepszego algorytmu i odpowiednich struktur
danych (w tym struktury dynamicznej) do rozwiązania
postawionego problemu
Przykładowy algorytm
#include <iostream>
using namespace std;
int main()
{
int n;
int * s;
cin >> n;
s = new int[n+1];
s[1] = 0;
for(int i=2;i<=n;++i)
{
if(i%2 == 0)
s[i] = i-1+2*s[i/2];
else
s[i] = i-1+s[(i-1)/2]+s[(i+1)/2];
}
}
4 p. - za w pełni poprawny algorytm, w tym:
za poprawną inicjację zmiennych - 1 p.
za poprawne obliczanie elementów parzystych - 1 p.
za poprawne obliczanie elementów nieparzystych - 1 p.
za poprawne podstawienia w tablicy - 1 p.
0 p. - za błędny algorytm albo brak odpowiedzi
Kryteria oceniania odpowiedzi
4

","solutions":[]}