{"id":"informatyka-2008-maj-matura-rozszerzona/zad/1","paper_id":"informatyka-2008-maj-matura-rozszerzona","number":"1","points":null,"ptype":"open","subject":"informatyka","category":"matura","year":2008,"month":"maj","level":"rozszerzona","text":"Zadanie 1. Potęgi (14 pkt)\nW poniższej tabelce podane są wartości kolejnych potęg liczby 2:\nk\n0\n1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n2k\n1\n2\n4\n8\n16\n32\n64\n128\n256\n512\n1024\nCiąg a=(a0, a1, a2, ) definiujemy następująco:\nak = reszta z dzielenia liczby 2k przez 10\ndla k = 0, 1, 2,\na) Korzystając z definicji, podaj 16 pierwszych wyrazów ciągu a. Wyniki umieść\nw poniższej tabelce:\nk\n0\n1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n11\n12\n13\n14\n15\nak\nUwaga: w dalszej części tego zadania możesz przyjąć, że operacje arytmetyczne na liczbach\ncałkowitych (dodawanie, odejmowanie, mnożenie, dzielenie całkowite, reszta\nz dzielenia) wykonywane są w czasie stałym, niezależnie od wielkości argumentów.\nb) W wybranej przez siebie notacji (lista kroków, schemat blokowy lub język\nprogramowania) podaj algorytm, który dla danej nieujemnej liczby całkowitej k\nwyznacza resztę z dzielenia liczby\nk\n2 przez 10. Np. dla\n15\nk\nwynikiem działania\nTwojego algorytmu powinno być 8.\nPrzy ocenie Twojego rozwiązania będzie brana pod uwagę zarówno poprawność\nzaproponowanego algorytmu, jak i jego złożoność czasowa, czyli liczba operacji\narytmetycznych wykonywanych w trakcie obliczania wyniku.\nSpecyfikacja:\nDane: Liczba całkowita\n0\n≥\nk\nWynik: Reszta z dzielenia\nk\n2 przez 10.\nAlgorytm\nPoziom rozszerzony - część I\n3\n4\nPoziom rozszerzony - część I\nc) Podaj w wybranej przez siebie notacji (lista kroków, schemat blokowy lub język\nprogramowania) algorytm obliczania liczby\nn\na , gdy a jest liczbą całkowitą, natomiast n\njest potęgą liczby 2 (\nk\nn\n2\ndla pewnej liczby całkowitej\n0\n≥\nk\n). Przy ocenie Twojego\nrozwiązania będzie brana pod uwagę złożoność czasowa (w zależności jedynie od n)\nzaproponowanego algorytmu, czyli liczba operacji arytmetycznych wykonywanych\nw trakcie obliczania wyniku.\nWskazówka: zauważ, że\n2\n2\nn\nn\nn\na\na\na\n⋅\n, dla n>1.\nSpecyfikacja:\nDane: Liczby całkowite a i n, gdzie\nk\nn\n2\ndla pewnej liczby całkowitej\n0\n≥\nk\nWynik: Liczba\nn\na .\nAlgorytm\nPoziom rozszerzony - część I\n5\nNr zadania\n1 a)\n1 b)\n1 c)\nMaks. liczba pkt\n2\n5\n7\nWypełnia\negzaminator! Uzyskana liczba pkt\n6\nPoziom rozszerzony - część I","answer":null,"answer_text":"1. Sprawdź,\nczy\narkusz\negzaminacyjny\nzawiera\n13 stron\n(zadania 1 - 3). Ewentualny brak zgłoś przewodniczącemu\nzespołu nadzorującego egzamin.","solution":null,"image":"img/informatyka-2008-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 2008 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 1. Potęgi (14 pkt)
W poniższej tabelce podane są wartości kolejnych potęg liczby 2:
k
0
1
2
3
4
5
6
7
8
9
10
2k
1
2
4
8
16
32
64
128
256
512
1024
Ciąg a=(a0, a1, a2, ) definiujemy następująco:
ak = reszta z dzielenia liczby 2k przez 10
dla k = 0, 1, 2,
a) Korzystając z definicji, podaj 16 pierwszych wyrazów ciągu a. Wyniki umieść
w poniższej tabelce:
k
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ak
Uwaga: w dalszej części tego zadania możesz przyjąć, że operacje arytmetyczne na liczbach
całkowitych (dodawanie, odejmowanie, mnożenie, dzielenie całkowite, reszta
z dzielenia) wykonywane są w czasie stałym, niezależnie od wielkości argumentów.
b) W wybranej przez siebie notacji (lista kroków, schemat blokowy lub język
programowania) podaj algorytm, który dla danej nieujemnej liczby całkowitej k
wyznacza resztę z dzielenia liczby
k
2 przez 10. Np. dla
15
k
wynikiem działania
Twojego algorytmu powinno być 8.
Przy ocenie Twojego rozwiązania będzie brana pod uwagę zarówno poprawność
zaproponowanego algorytmu, jak i jego złożoność czasowa, czyli liczba operacji
arytmetycznych wykonywanych w trakcie obliczania wyniku.
Specyfikacja:
Dane: Liczba całkowita
0
≥
k
Wynik: Reszta z dzielenia
k
2 przez 10.
Algorytm
Poziom rozszerzony - część I
3
4
Poziom rozszerzony - część I
c) Podaj w wybranej przez siebie notacji (lista kroków, schemat blokowy lub język
programowania) algorytm obliczania liczby
n
a , gdy a jest liczbą całkowitą, natomiast n
jest potęgą liczby 2 (
k
n
2
dla pewnej liczby całkowitej
0
≥
k
). Przy ocenie Twojego
rozwiązania będzie brana pod uwagę złożoność czasowa (w zależności jedynie od n)
zaproponowanego algorytmu, czyli liczba operacji arytmetycznych wykonywanych
w trakcie obliczania wyniku.
Wskazówka: zauważ, że
2
2
n
n
n
a
a
a
⋅
, dla n>1.
Specyfikacja:
Dane: Liczby całkowite a i n, gdzie
k
n
2
dla pewnej liczby całkowitej
0
≥
k
Wynik: Liczba
n
a .
Algorytm
Poziom rozszerzony - część I
5
Nr zadania
1 a)
1 b)
1 c)
Maks. liczba pkt
2
5
7
Wypełnia
egzaminator! Uzyskana liczba pkt
6
Poziom rozszerzony - część I

","answer_text_html":"
  1. Sprawdź,
\n

czy
arkusz
egzaminacyjny
zawiera
13 stron
(zadania 1 - 3). Ewentualny brak zgłoś przewodniczącemu
zespołu nadzorującego egzamin.

","solutions":[]}