Реализации алгоритмов: Евклида и расширенный алгоритм Евклида.

       В этом посте рассматриваются реализации алгоритма Евклида, расширенного алгоритма Евклида. При этом как классические так и рекурсивные. Так же есть примеры готовых программ с использованием этих алгоритмов. Кстати, все алгоритмы работают с отрицательныи числами.

       Содержание

• Алгоритм Евклида
• Расширенный алгоритм Евклида
• Рекурсивная реализация алгоритма Евклида
• Рекурсивная реализация расширенного алгоритма Евклида
• Примеры программы (исходный код)

Алгоритм Евклида позволяет находить НОД (наибольший общий делитель) чисел. В интернете масса информации по этому алгоритму, в частности на Википедии.
Мы лишь приведём реализации алгоритмов:

      Алгоритм Евклида. 

int gcd(int a, int b) {
   int t;
   while (b) {
     t = a % b;
     a = b;
     b = t;        
   }
   return abs(a);
}

      Расширенный алгоритм Евклида.


int ext_gcd(int a, int b, int& x, int& y){
int q, r, x1, x2, y1, y2,d;
if (b == 0) {
d = a, x = 1, y = 0;
return d;
}
x2 = 1, x1 = 0, y2 = 0, y1 = 1;
while (b > 0) {
q = a / b, r = a - q * b;
x = x2 - q * x1, y = y2 - q * y1;
a = b, b = r;
x2 = x1, x1 = x, y2 = y1, y1 = y;
}
d = a, x = x2, y = y2;
return d;
}

    Но есть более изящные реализации этих алгоритмов - рекурсивные.

     Рекурсивная реализация алгоритма Евклида. 

int rec_gcd(int a, int b){
return b?gcd(b,a%b):abs(a);
}
    Рекурсивная реализация расширенного алгоритма Евклида.

int rec_ext_gcd (int a, int b, int & x, int & y) {
if (a == 0) {
x = 0; y = 1;
return b;
}
int x1, y1;
int d = gcd (b%a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}


    Примеры использования (исходные коды).

• Евклид + Расширенный
• Рекурсивные реализации