Zadanie 3.2, matura maj 2015, informatyka rozszerzona
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:
,
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
,
parę liczb (x, y) można wyrazić wzorami:
x = 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łania | NWD(a, b): wartość a w i-tym wywołaniu | NWD(a, b): wartość b w i-tym wywołaniu | Zagnieżdżanie rekurencji ← | Powrót z rekurencji → | Wynik x | Wynik y |
|---|---|---|---|---|---|---|
| 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 .
Polecenie
3 punktyUzupeł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
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.
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
za prawidłowo wypełnione pola w krokach 3 i 4 algorytmu.
za prawidłowo wypełnione pola w kroku 4 algorytmu.
za prawidłowo wypełnione pola w kroku 3 algorytmu albo za odpowiedź (y', x' – (a div b) • y').
za odpowiedź niepełną lub błędną albo za brak odpowiedzi.