{"id":"informatyka-2023-czerwiec-matura-rozszerzona/zad/1","paper_id":"informatyka-2023-czerwiec-matura-rozszerzona","number":"1","points":null,"ptype":"open","subject":"informatyka","category":"matura","year":2023,"month":"czerwiec","level":"rozszerzona","text":"Zadanie 1. Mnożenie\nNastępujący rekurencyjny algorytm mnożenia dwóch liczb całkowitych dodatnich x, y jest\nrealizowany z użyciem operacji arytmetycznych dodawania i dzielenia całkowitego przez 2.\niloczyn(x, y):\njeżeli y = 1\nwynikiem jest x\nw przeciwnym razie\nk  y div 2\nz  iloczyn(x, k)\njeżeli y mod 2 = 0\nwynikiem jest z + z\nw przeciwnym razie\nwynikiem jest x + z + z\nUwaga: x mod y oznacza resztę z dzielenia x przez y, natomiast x div y oznacza wynik\ndzielenia całkowitego x przez y.\nDla danych liczb x, y interesuje nas liczba wykonywanych operacji dodawania podczas\nobliczania wyniku funkcji iloczyn(x, y).\nPrzykład 1.\nDla liczb x=9 i y=11 algorytm wykonuje 5 dodawań. Działanie funkcji iloczyn(9, 11) można\nzilustrować w następujący sposób (w nawiasach obok wskazano liczbę wykonywanych\noperacji dodawania):\niloczyn(9, 11) = 9 + z + z, (dwa dodawania)\ngdzie z = iloczyn(9, 5)\niloczyn(9, 5) = 9 + z + z, (dwa dodawania)\ngdzie z = iloczyn(9, 2)\niloczyn(9, 2) = z + z, (jedno dodawanie)\ngdzie z = iloczyn(9, 1)\niloczyn(9, 1) = 9\nPoniższa tabela ilustruje obliczenia wykonywane podczas wywołania iloczyn(9, 11)\nNumer\nwywołania\nParametry\nwywołania\nObliczone k, z\nWynik\nx\ny\nk\nz\n1\n9\n11\n5\n45\n99 (9+45+45)\n2\n9\n5\n2\n18\n45 (9+18+18)\n3\n9\n2\n1\n9\n18 (9+9)\n4\n9\n1\n9\nMINP-R0_100","answer":null,"answer_text":"10\n45\n22\n220\n450","solution":null,"image":"img/informatyka-2023-czerwiec-matura-rozszerzona/zad-1.webp","solution_image":null,"topics":null,"page_from":4,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":null,"text_source":"ocr","source_label":"Informatyka · Matura · czerwiec 2023 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 1. Mnożenie
Następujący rekurencyjny algorytm mnożenia dwóch liczb całkowitych dodatnich x, y jest
realizowany z użyciem operacji arytmetycznych dodawania i dzielenia całkowitego przez 2.
iloczyn(x, y):
jeżeli y = 1
wynikiem jest x
w przeciwnym razie
k  y div 2
z  iloczyn(x, k)
jeżeli y mod 2 = 0
wynikiem jest z + z
w przeciwnym razie
wynikiem jest x + z + z
Uwaga: x mod y oznacza resztę z dzielenia x przez y, natomiast x div y oznacza wynik
dzielenia całkowitego x przez y.
Dla danych liczb x, y interesuje nas liczba wykonywanych operacji dodawania podczas
obliczania wyniku funkcji iloczyn(x, y).
Przykład 1.
Dla liczb x=9 i y=11 algorytm wykonuje 5 dodawań. Działanie funkcji iloczyn(9, 11) można
zilustrować w następujący sposób (w nawiasach obok wskazano liczbę wykonywanych
operacji dodawania):
iloczyn(9, 11) = 9 + z + z, (dwa dodawania)
gdzie z = iloczyn(9, 5)
iloczyn(9, 5) = 9 + z + z, (dwa dodawania)
gdzie z = iloczyn(9, 2)
iloczyn(9, 2) = z + z, (jedno dodawanie)
gdzie z = iloczyn(9, 1)
iloczyn(9, 1) = 9
Poniższa tabela ilustruje obliczenia wykonywane podczas wywołania iloczyn(9, 11)
Numer
wywołania
Parametry
wywołania
Obliczone k, z
Wynik
x
y
k
z
1
9
11
5
45
99 (9+45+45)
2
9
5
2
18
45 (9+18+18)
3
9
2
1
9
18 (9+9)
4
9
1
9
MINP-R0_100

","answer_text_html":"

10
45
22
220
450

","solutions":[]}