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

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,

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',

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

x = y'

y = x' − (a div b)∙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) | 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.

Zadanie 3.1.

Uzupeł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