Programowanie i algorytmy

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:

{tex}NWD(a,\ b)=a\cdot x+b\cdot y{/tex}

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

{tex}NWD(13,5)=1=13\cdot 2 + 5\cdot (-5){/tex}

a więc {tex}x=2,\ y=-5{/tex}

Opis algorytmu

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

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

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

Krok 1.

wynik dzielenia całkowitego liczby a przez b: {tex}13\ div\ 5 = 2{/tex} 

reszta z dzielenia całkowitego liczby a przez b: {tex}13\ mod\ 5 = 3{/tex}

a więc liczbę {tex}13{/tex} można zapisać

(1) {tex}13 = 2\cdot 5 +3{/tex}

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.

{tex}5\ div\ 3 = 1{/tex} 

{tex}5\ mod\ 3 = 2{/tex}

liczbę {tex}5{/tex} możemy przedstawić w postaci równania:

(2) {tex}5 = 1\cdot 3 +2{/tex}

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

Krok 3.

{tex}3\ div\ 2 = 1{/tex} 

{tex}3\ mod\ 2 = 1{/tex}

(3) {tex}3 = 1\cdot 2 +1{/tex}

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

Krok 4.

{tex}2\ div\ 1 = 2{/tex} 

{tex}2\ mod\ 1 = 0{/tex}

{tex}2 = 2\cdot1+0{/tex}

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) {tex}3 = 1\cdot 13 - 2\cdot 5{/tex}

(2) {tex}2 = 1\cdot 5 -1\cdot 3{/tex}

(3) {tex}1 = 1\cdot 3 -1\cdot 2{/tex}

Teraz do równania (3) podstawiamy za {tex}3{/tex} resztę z równania  (2), a do drugiego resztę z równania (1):

 {tex}1=1\cdot 3-1\cdot 2=1\cdot 3-1\cdot (1\cdot 5 -1\cdot 3)={/tex}

{tex}- 1\cdot 5+2\cdot 3=-1\cdot 5+2\cdot(1\cdot 13-2\cdot 5)={/tex}

{tex}2\cdot 13-5\cdot 5{/tex}

W ten sposób znaleźliśmy szukane wartości {tex}x{/tex} i {tex}y{/tex}. 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;
 
 
  cin.get();
  return 0;
}