Zadanie 3.1, 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
2 punktyUzupełnij poniższą tabelę ilustrującą wykonanie funkcji RozszerzonyEuklides(a, b) dla danych a = 188, b = 12.
| i – nr wywołania | Wartość a w i-tym wywołaniu | Wartość b w i-tym wywołaniu | Wynik x | Wynik y |
|---|---|---|---|---|
| 1 | 188 | 12 | ||
| 2 | ||||
| 3 | ||||
| 4 | 0 | 1 | 0 |
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
| i – nr wywołania | Wartość a | Wartość b | Wynik x | Wynik y |
|---|---|---|---|---|
| 1 | 188 | 12 | -1 | 16 |
| 2 | 12 | 8 | 1 | -1 |
| 3 | 8 | 4 | 0 | 1 |
| 4 | 4 | 0 | 1 | 0 |
Schemat punktowania
za prawidłowe uzupełnienie kolumn z wartościami a i b oraz za prawidłowe uzupełnienie kolumn Wynik x i Wynik y.
za prawidłowe uzupełnienie kolumn z wartościami a i b albo za prawidłowe uzupełnienie kolumn Wynik x i Wynik y.
za odpowiedź niepełną lub błędną albo za brak odpowiedzi.