Algorytm Euklidesa pozwala na szybkie znalezienie Największego Wspólnego Dzielnika (NWD) dwóch liczb naturalnych dodatnich. Znając jego wartość, będziemy również w stanie wyznaczyć Najmniejszą Wspólną Wielokrotność (NWW) tych liczb.

Zależność ta jest szczególnie istotna przy znajdowaniu wspólnego mianownika dla dwóch ułamków. Informacja o NWW ich mianowników pozwoli nam określić, przez jaką liczbę musimy pomnożyć ich liczniki i mianowniki, aby sprowadzić je do wspólnego mianownika. Dzięki temu, w kolejnym kroku, będziemy mogli wykonać na nich operację dodawania lub odejmowania.

Zadanie typu maturalnego

Rozwiążemy teraz jedno z zadań typu maturalnego.

Dane:
	liczby całkowite dodatnie a i b.
Wynik:
	Największy wspólny dzielnik liczb a i b.

funkcja NWD(a, b)
	dopóki b != 0 wykonuj
		r = a mod b
		a = b
		b = r
        
	zwróć a i zakończ

Przeanalizuj działanie funkcji NWD() i dla wskazanych argumentów podaj liczbę operacji modulooperacja modulooperacji modulo.

Naszym celem jest analiza działania funkcji NWD() i podanie liczby wykonań operacji modulo dla argumentów podanych w tabeli.

Dla pierwszej pary zmiennych a i b, czyli NWD(25, 15), pierwsze przejście pętli w funkcji wygląda następująco:

funkcja NWD(25, 15)
	dopóki b != 0 wykonuj
		r = 25 mod 15 // czyli 10
		a = 15
		b = 10
        
	zwróć a i zakończ

Po jednym wykonaniu pętli dopóki liczba wykonań operacji modulo wynosi 1. Z kodu funkcji możemy wywnioskować, że liczba wykonań operacji modulo będzie równa liczbie wykonań pętli dla podanej pary liczb a i b.

Kontynuujmy analizę działania funkcji dla pierwszego przykładu. Po zakończeniu ostatniego przejścia pętli, nasze zmienne mają wartości:

• a = 15,

• b = 10,

• liczba wykonań operacji modulo = 1.

Zmienna b jest w dalszym ciągu różna od 0. Pętla zostanie wykonana jeszcze raz, realizując następującą operację:

r = 15 mod 10 // czyli 5
a = 10
b = 5

Po tym wykonaniu pętli, nasze zmienne przyjmują wartości:

• a = 10,

• b = 5,

• liczba wykonań operacji modulo = 2.

Zmienna b jest w dalszym ciągu różna od zera. Wykonamy więc jeszcze jedno przejście pętli dopóki, z następującymi operacjami:

r = 10 mod 5 // czyli 0
a = 5
b = 0

W tym momencie, wartości naszych zmiennych prezentują się tak:

• a = 5,

• b = 0,

• liczba wykonań operacji modulo = 3.

Widzimy więc, że było to ostatnie wykonanie pętli dopóki, ponieważ jej warunek nie jest już spełniany - b osiągnęło wartość 0.

Kończymy pętlę, a tym samym działanie funkcji poprzez zwrócenie wartości argumentu a - czyli 5. Jest to NWD dwóch liczb.

Nie zapominajmy jednak, że zgodnie z treścią zadania, mamy podać, ile razy została wykonana operacja modulo.

Jak już zauważyliśmy, w każdym przejściu pętli dopóki wystąpi jedna taka operacja.

W przypadku liczb 25 i 15 pętla ta wykonała się trzy razy. Tak więc w pierwszym wierszu kolumny liczba operacji mod wpisalibyśmy odpowiednio wartość 3.

Znajdziemy teraz odpowiedzi dla pozostałych dwóch par liczb a i b.

Dla a = 116, b = 324 kolejne reszty z dzielenia r osiągną następujące wartości:

1. 116,

2. 92,

3. 24,

4. 20,

5. 4,

6. 0.

Jest sześć reszt, tak więc operacja modulo wykonała się sześć razy.

Oto wartości r dla ostatniego przykładu z zadania:

1. 198,

2. 84,

3. 30,

4. 24,

5. 6,

6. 0.

Ponownie mamy więc do czynienia z sześcioma wykonaniami operacji modulo. W ten sposób prześledziliśmy działanie algorytmu Euklidesa.

Słownik