{"id":"informatyka-2015-maj-matura-rozszerzona/zad/3","paper_id":"informatyka-2015-maj-matura-rozszerzona","number":"3","points":null,"ptype":"open","subject":"informatyka","category":"matura","year":2015,"month":"maj","level":"rozszerzona","text":"Zadanie 3. Rozszerzony algorytm Euklidesa\nAlgorytm Euklidesa to algorytm wyznaczania największego wspólnego dzielnika (NWD)\ndwóch liczb całkowitych a > 0 i b ≥ 0.\nSpecyfikacja:\nDane:\nliczby całkowite, a > 0 i b ≥ 0,\nWynik:\nnajwiększy wspólny dzielnik liczb a i b.\nAlgorytm NWD:\nKrok 1.\nJeżeli b = 0, to NWD jest równy a i zakończ wykonywanie algorytmu.\nKrok 2.\nOblicz r jako resztę z dzielenia a przez b.\nKrok 3.\nZastąp a przez b, natomiast b przez r.\nKrok 4.\nPrzejdź do kroku 1.\nW niektórych zastosowaniach informatycznych potrzebujemy wyrazić największy wspólny\ndzielnik dwóch liczb całkowitych a, b w następujący sposób:\nܦሺܽ,ܾሻ=ܽ\n∙ݔ+ܾ\n∙ݕ,\ngdzie x i y są liczbami całkowitymi.\nDo wyznaczenia wartości x i y wykorzystywana jest następująca zależność:\ndla ݎ=ܽ\n݉\n݋݀ ܾ różnego od zera oraz liczb całkowitych x’, y’ takich, że\nܦሺܾ, ݎሻ=ܾ\n∙ݔᇱ+ ݎ∙ݕ′,\nparę liczb (x, y) można wyrazić wzorami:\nݔ= ݕᇱ\nݕ= ݔᇱ-ሺܽ ݀݅\nݒ ܾሻ∙ݕ′\nUwaga:\na mod b, a div b oznaczają odpowiednio resztę i iloraz z dzielenia całkowitego a przez b.\nWypełnia\negzaminator\nNr zadania\n2.3.\n2.4.\n2.5.\nMaks. liczba pkt.\n1\n1\n1\nUzyskana liczba pkt.\nMIN_1R\nOpisana zależność pozwala na rekurencyjne obliczenie pary liczb (x, y).\nNiech RozszerzonyEuklides(a, b) będzie rekurencyjną funkcją realizującą ten pomysł.\nDziałanie funkcji zilustrujmy przykładem.\nPrzykład dla a = 231, b = 30\ni - nr\nwywołania\nNWD (a, b)\nZagnieżdżanie\nrekurencji\n←\nPowrót\nz rekurencji\n→\nWynik\nx\nWynik\ny\nWartość a\nw i-tym\nwywołaniu\nWartość b\nw i-tym\nwywołaniu\n1\n231\n30\n↓\n↑\n3\n-23\n2\n30\n21\n↓\n↑\n-2\n3\n3\n21\n9\n↓\n↑\n1\n-2\n4\n9\n3\n↓\n↑\n0\n1\n5\n3\n0\n↓\n↑\n1\n0\nZatem NWD(231, 30) = 3 · 231 + (-23) · 30.","answer":null,"answer_text":"8\n4\n0\n1","solution":null,"image":"img/informatyka-2015-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 2015 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 3. Rozszerzony algorytm Euklidesa
Algorytm Euklidesa to algorytm wyznaczania największego wspólnego dzielnika (NWD)
dwóch liczb całkowitych a > 0 i b ≥ 0.
Specyfikacja:
Dane:
liczby całkowite, a > 0 i b ≥ 0,
Wynik:
największy wspólny dzielnik liczb a i b.
Algorytm NWD:
Krok 1.
Jeżeli b = 0, to NWD jest równy a i zakończ wykonywanie algorytmu.
Krok 2.
Oblicz r jako resztę z dzielenia a przez b.
Krok 3.
Zastąp a przez b, natomiast b przez r.
Krok 4.
Przejdź do kroku 1.
W niektórych zastosowaniach informatycznych potrzebujemy wyrazić największy wspólny
dzielnik dwóch liczb całkowitych a, b w następujący sposób:
ܦሺܽ,ܾሻ=ܽ
∙ݔ+ܾ
∙ݕ,
gdzie x i y są liczbami całkowitymi.
Do wyznaczenia wartości x i y wykorzystywana jest następująca zależność:
dla ݎ=ܽ
݉
݋݀ ܾ różnego od zera oraz liczb całkowitych x’, y’ takich, że
ܦሺܾ, ݎሻ=ܾ
∙ݔᇱ+ ݎ∙ݕ′,
parę liczb (x, y) można wyrazić wzorami:
ݔ= ݕᇱ
ݕ= ݔᇱ-ሺܽ ݀݅
ݒ ܾሻ∙ݕ′
Uwaga:
a mod b, a div b oznaczają odpowiednio resztę i iloraz z dzielenia całkowitego a przez b.
Wypełnia
egzaminator
Nr zadania
2.3.
2.4.
2.5.
Maks. liczba pkt.
1
1
1
Uzyskana liczba pkt.
MIN_1R
Opisana zależność pozwala na rekurencyjne obliczenie pary liczb (x, y).
Niech RozszerzonyEuklides(a, b) będzie rekurencyjną funkcją realizującą ten pomysł.
Działanie funkcji zilustrujmy przykładem.
Przykład dla a = 231, b = 30
i - nr
wywołania
NWD (a, b)
Zagnieżdżanie
rekurencji
←
Powrót
z rekurencji
→
Wynik
x
Wynik
y
Wartość a
w i-tym
wywołaniu
Wartość b
w i-tym
wywołaniu
1
231
30
↓
↑
3
-23
2
30
21
↓
↑
-2
3
3
21
9
↓
↑
1
-2
4
9
3
↓
↑
0
1
5
3
0
↓
↑
1
0
Zatem NWD(231, 30) = 3 · 231 + (-23) · 30.

","answer_text_html":"

8
4
0
1

","solutions":[]}