{"id":"informatyka-2009-maj-matura-rozszerzona/zad/3","paper_id":"informatyka-2009-maj-matura-rozszerzona","number":"3","points":null,"ptype":"open","subject":"informatyka","category":"matura","year":2009,"month":"maj","level":"rozszerzona","text":"Zadanie 3. Największy wspólny dzielnik - NWD (10 pkt)\nAlgorytm opisany w Księdze VII Elementów Euklidesa pozwala szybko obliczyć największy\nwspólny dzielnik dwóch liczb naturalnych a i b -\n(\n)\n,\nnwd a b , z których co najmniej jedna jest\nwiększa od 0. Oto rekurencyjny sposób obliczania\n(\n)\n,\nnwd a b :\ndla\n0\n( , )\n( ,\nmod\n) dla\n1\na\nb\nnwd a b\nnwd b a\nb\nb\n⎧\n= ⎨\n≥\n⎩\ngdzie: mod - operator dzielenia modulo; wynikiem jego działania jest reszta z dzielenia\na przez b, na przykład 19 mod 7 = 5.\nPrzykład:\n(\n)\n(\n)\n(\n)\n16,12\n12,4\n4,0\n4\nnwd\nnwd\nnwd\n- funkcja nwd jest wywoływana w tym\nprzypadku 3 razy:\na) Podaj liczbę wywołań funkcji dla\n56\na =\ni\n72\nb =\noraz dla\n72\na =\ni\n56\nb =\nb) Podaj w wybranej przez siebie notacji (lista kroków, schemat blokowy lub język\nprogramowania, który wybrałeś/aś na egzamin) nierekurencyjny algorytm obliczania\nwartości funkcji\n(\n)\n,\nnwd a b wraz ze specyfikacją.\nSpecyfikacja:\nDane:\nWynik:\n8\nPoziom rozszerzony - część I\nNr zadania\n3a)\n3 b)\nMaksymalna liczba pkt\n2\n8\nWypełnia\negzaminator! Uzyskana liczba pkt\nPoziom rozszerzony - część I\n9\nBRUDNOPIS","answer":null,"answer_text":"3.\nb\nZa poprawną specyfikacjĊ - 2 punkty\n(za Dane - 1 punkt, za Wynik - 1 punkt)\nnp.:\nDane: dwie liczby naturalne a i b, z których co najmniej jedna\njest wiĊksza od 0.\nWynik: NajwiĊkszy wspólny dzielnik liczb a i b\nZa poprawny nierekurencyjny algorytm - 6 punktów,\nw tym za:\n- prawidáową konstrukcjĊ pĊtli - 3 punkty\n- poprawne obliczenia wewnątrz pĊtli - 3 punkty\nPrzykáadowy zapis algorytmu:\n(1) dopóki (b > 0) wykonuj\ntemp = a mod b\na = b\nb = temp\n(2) zwróü a\n8\n10\nInformatyka - poziom rozszerzony\nKlucz punktowania odpowiedzi\n99\nCZĉĝû II\nNr zadania\nNr\npodpunktu\nKlucz punktowania odpowiedzi\nMaks.\npunktacja\nza czĊĞü\nzadania\nMaks.\npunktacja\nza\nzadanie\na\nZa poprawną implementacjĊ algorytmu generującego obraz\nsmoka - 4 punkty, w tym za:\n- za wylosowanie wariantu ukáadu równaĔ dla bieĪącej\niteracji - 2 punkty\n- za poprawne obliczenie wspóárzĊdnych x i y wedáug\nwybranego ukáadu równaĔ - 2 punkty\n4\nb\nZa poprawną generacjĊ obrazu (wykresu punktowego)\n- 4 punkty, w tym:\n- za zastosowanie poprawnie dobranych danych do wykresu\n(pominie 100 pierwszych iteracji) - 1 punkt\n- za poprawnie wygenerowany obraz - 3 punkty (jeĞli\nzdający wygeneruje wykres punktowy áączony - 1 punkt)\nPrzykáadowy obraz:\n4\nc\nZa poprawne (zgodne z warunkami zadania) obliczenie\nĞrednich x i y dla wygenerowanych danych - 2 punkty\n(po jednym punkcie za kaĪde prawidáowe obliczenie)\nUwaga: W przypadku podania poprawnych wyników bez\nzaokrąglenia - 1 punkt\n2","solution":null,"image":"img/informatyka-2009-maj-matura-rozszerzona/zad-3.webp","solution_image":null,"topics":null,"page_from":7,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":null,"text_source":"ocr","source_label":"Informatyka · Matura · maj 2009 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 3. Największy wspólny dzielnik - NWD (10 pkt)
Algorytm opisany w Księdze VII Elementów Euklidesa pozwala szybko obliczyć największy
wspólny dzielnik dwóch liczb naturalnych a i b -
(
)
,
nwd a b , z których co najmniej jedna jest
większa od 0. Oto rekurencyjny sposób obliczania
(
)
,
nwd a b :
dla
0
( , )
( ,
mod
) dla
1
a
b
nwd a b
nwd b a
b
b
⎧
= ⎨
≥
⎩
gdzie: mod - operator dzielenia modulo; wynikiem jego działania jest reszta z dzielenia
a przez b, na przykład 19 mod 7 = 5.
Przykład:
(
)
(
)
(
)
16,12
12,4
4,0
4
nwd
nwd
nwd

\n\n

przypadku 3 razy:
a) Podaj liczbę wywołań funkcji dla
56
a =
i
72
b =
oraz dla
72
a =
i
56
b =
b) Podaj w wybranej przez siebie notacji (lista kroków, schemat blokowy lub język
programowania, który wybrałeś/aś na egzamin) nierekurencyjny algorytm obliczania
wartości funkcji
(
)
,
nwd a b wraz ze specyfikacją.
Specyfikacja:
Dane:
Wynik:
8
Poziom rozszerzony - część I
Nr zadania
3a)
3 b)
Maksymalna liczba pkt
2
8
Wypełnia
egzaminator! Uzyskana liczba pkt
Poziom rozszerzony - część I
9
BRUDNOPIS

","answer_text_html":"

3.
b
Za poprawną specyfikacjĊ - 2 punkty
(za Dane - 1 punkt, za Wynik - 1 punkt)
np.:
Dane: dwie liczby naturalne a i b, z których co najmniej jedna
jest wiĊksza od 0.
Wynik: NajwiĊkszy wspólny dzielnik liczb a i b
Za poprawny nierekurencyjny algorytm - 6 punktów,
w tym za:

\n\n

Przykáadowy zapis algorytmu:
(1) dopóki (b > 0) wykonuj
temp = a mod b
a = b
b = temp
(2) zwróü a
8
10
Informatyka - poziom rozszerzony
Klucz punktowania odpowiedzi
99
CZĉĝû II
Nr zadania
Nr
podpunktu
Klucz punktowania odpowiedzi
Maks.
punktacja
za czĊĞü
zadania
Maks.
punktacja
za
zadanie
a
Za poprawną implementacjĊ algorytmu generującego obraz
smoka - 4 punkty, w tym za:

\n\n

iteracji - 2 punkty

\n\n

wybranego ukáadu równaĔ - 2 punkty
4
b
Za poprawną generacjĊ obrazu (wykresu punktowego)

\n\n

(pominie 100 pierwszych iteracji) - 1 punkt

\n\n

zdający wygeneruje wykres punktowy áączony - 1 punkt)
Przykáadowy obraz:
4
c
Za poprawne (zgodne z warunkami zadania) obliczenie
Ğrednich x i y dla wygenerowanych danych - 2 punkty
(po jednym punkcie za kaĪde prawidáowe obliczenie)
Uwaga: W przypadku podania poprawnych wyników bez
zaokrąglenia - 1 punkt
2

","solutions":[]}