UWAGA konkurs!
Mistrz Programowania

PROGRAMOWANIE I ALGORYTMY

szkoła fraktal
Zapraszamy na lekcję otwartą wrzesień 2023

Rozszerzony algorytm Euklidesa


Podstawowa wersja algorytmu Euklidesa pozwala wyznaczyć największy wspólny dzielnik dla dwóch liczb naturalnych. Rozszerzona wersja tego algorytmu dodatkowo rozwiązuje równanie diofantyczne:

$$NWD(a,\ b)=a\cdot x+b\cdot y$$

wyznaczając wartości całkowite liczb x oraz y, na przykład dla liczb 13 i 5 mamy:

$$NWD(13,5)=1=13\cdot 2 + 5\cdot (-5)$$

a więc $$x=2,\ y=-5$$

Opis algorytmu

Po pierwsze należy zauważyć, że dla dowolnych trzech liczb całkowitych  $$a,\ b,\ c$$ zachodzi:

jeśli $$\frac{a}{b}=c,\ b\neq 0$$ to $$a=b\cdot c + r$$, gdzie r, to reszta z dzielenia liczb a przez b

Do opisania algorytmu posłużymy się powyższym przykładem:

Krok 1.

wynik dzielenia całkowitego liczby a przez b: $$13\ div\ 5 = 2$$ 

reszta z dzielenia całkowitego liczby a przez b: $$13\ mod\ 5 = 3$$

a więc liczbę 13 można zapisać

(1) $$13 = 2\cdot 5 +3$$

W każdym kolejnym kroku będziemy brać liczbę przez którą dzieliliśmy i otrzymaną resztę, a więc w kroku następnym liczbę 5 i 3.

Krok 2.

$$5\ div\ 3 = 1$$ 

$$5\ mod\ 3 = 2$$

liczbę 5 możemy przedstawić w postaci równania:

(2) $$5 = 1\cdot 3 +2$$

tym razem dzieliliśmy przez 3, a uzyskana reszta to 2.

Krok 3.

$$3\ div\ 2 = 1$$ 

$$3\ mod\ 2 = 1$$

(3) $$3 = 1\cdot 2 +1$$

dzieliliśmy przez 2, a uzyskana reszta to 1.

Krok 4.

$$2\ div\ 1 = 2$$ 

$$2\ mod\ 1 = 0$$

$$2 = 2\cdot1+0$$

Pamiętamy z algorytmu Euklidesa (wersja optymalna), że gdy otrzymujemy resztę równą 0, to NWD liczb jest poprzednia reszta, w tym przykładzie jest to 1.

Z każdego równania z otrzymanych kroków (nie licząc kroku 4), wyznaczamy resztę:

(1) $$3 = 1\cdot 13 - 2\cdot 5$$

(2) $$2 = 1\cdot 5 -1\cdot 3$$

(3) $$1 = 1\cdot 3 -1\cdot 2$$

Teraz do równania (3) podstawiamy za $$3$$ resztę z równania  (2), a do drugiego resztę z równania (1):

 $$1=1\cdot 3-1\cdot 2=1\cdot 3-1\cdot (1\cdot 5 -1\cdot 3)=$$

$$- 1\cdot 5+2\cdot 3=-1\cdot 5+2\cdot(1\cdot 13-2\cdot 5)=$$

$$2\cdot 13-5\cdot 5$$

W ten sposób znaleźliśmy szukane wartości x i y. Problem ten można w prosty sposób rozwiązać rekurencyjnie.

Implementacja rekurencyjna algorytmu 

#include<iostream>
using namespace std;

int x, y;
void euklides(int a, int b)
{
	if(b!=0)
	{
		euklides(b, a%b);
		int pom = y;
		y = x  - a/b*y;
		x = pom;
	}
}
int main()
{
	x = 1, y = 0;
	int a, b;
	
	cout<<"Podaj liczby: ";
	cin>>a>>b;
	
	euklides(a, b);
	
	cout<<"nwd("<<a<<", "<<b<<") = "
	<<a<<" * "<<x<<" + "<<b<<" * "<<y<<" = "
	<<a*x+b*y<<endl;
	
	return 0;
}