Zadanie 3.2, matura maj 2015, informatyka rozszerzona

3 pktotwartetrudne 23%Maj 2015

Darmowe konto pozwoli wrócić do niego później.

Zadanie

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:

NWD⁡(a,b)=a⋅x+b⋅y\operatorname{NWD}(a,b)=a\cdot x+b\cdot y,

gdzie x i y są liczbami całkowitymi.

Do wyznaczenia wartości x i y wykorzystywana jest następująca zależność:

dla r = a mod b różnego od zera oraz liczb całkowitych x', y' takich, że

NWD⁡(b,r)=b⋅x′+r⋅y′\operatorname{NWD}(b,r)=b\cdot x'+r\cdot y',

parę liczb (x, y) można wyrazić wzorami:

x = y′

y=x′−(adiv⁡b)⋅y′y=x'-(a\operatorname{div}b)\cdot y'

Uwaga: a mod b, a div b oznaczają odpowiednio resztę i iloraz z dzielenia całkowitego a przez b.

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łaniaNWD(a, b): wartość a w i-tym wywołaniuNWD(a, b): wartość b w i-tym wywołaniuZagnieżdżanie rekurencji ←Powrót z rekurencji →Wynik xWynik y
123130↓↑3–23
23021↓↑–23
3219↓↑1–2
493↓↑01
530↓↑10

Zatem NWD⁡(231,30)=3⋅231+(−23)⋅30\operatorname{NWD}(231,30)=3\cdot231+(-23)\cdot30.

Polecenie

3 punkty

Uzupełnij poniższą rekurencyjną funkcję obliczania pary liczb (x, y) dla danych liczb a, b.

Specyfikacja:

Dane: liczby całkowite a > 0 i b ≥ 0

Wynik: para liczb całkowitych (x, y), dla których NWD⁡(a,b)=a⋅x+b⋅y\operatorname{NWD}(a,b)=a\cdot x+b\cdot y

RozszerzonyEuklides(a, b):

Krok 1. Jeśli b = 0, podaj jako wynik funkcji parę (1, 0) i zakończ jej wykonywanie.

Krok 2. r ← a mod b

Krok 3. (x, y) ← RozszerzonyEuklides(, )

Krok 4. Podaj jako wynik parę (, ).

Korepetytor

Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.

Wypróbuj za darmo

5 rozmów · bez karty · Zaloguj się

Sprawdź się

Jak poszło?

Pokaż rozwiązanieUkryj rozwiązanie

Odpowiedź z klucza CKE

Krok 3: (b, r).

Krok 4: (y, x – (a div b) • y).

Schemat punktowania

3 pkt

za prawidłowo wypełnione pola w krokach 3 i 4 algorytmu.

2 pkt

za prawidłowo wypełnione pola w kroku 4 algorytmu.

1 pkt

za prawidłowo wypełnione pola w kroku 3 algorytmu albo za odpowiedź (y', x' – (a div b) • y').

0 pkt

za odpowiedź niepełną lub błędną albo za brak odpowiedzi.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.