C Chương trình cho các thuật toán Euclid mở rộng?

Ở đây chúng ta sẽ thấy thuật toán Euclid mở rộng được thực hiện bằng cách sử dụng C. Thuật toán Euclid mở rộng cũng được sử dụng để lấy GCD. Điều này tìm thấy các hệ số nguyên của x và y như bên dưới -

𝑎𝑥+𝑏𝑦 = gcd(𝑎,𝑏)

Ở đây trong thuật toán này, nó cập nhật giá trị của gcd (a, b) bằng cách sử dụng lệnh gọi đệ quy như thế này - gcd (b mod a, a). Hãy để chúng tôi xem thuật toán để có được ý tưởng

Thuật toán

EuclideanExtended (a, b, x, y)

begin
   if a is 0, then
      x := 0
      y := 1
      return b
   end if
   gcd := EuclideanExtended(b mod a, a, x1, y1)
   x := y1 – (b/a)*x1
   y := x1
   return gcd
end

Ví dụ

#include <stdio.h>
int EuclideanExtended(int a, int b, int* x, int* y) {
   if (a == 0) {
      *x = 0;
      *y = 1;
      return b;
   }
   int xtemp, ytemp; // To store results of recursive call
   int res = EuclideanExtended(b % a, a, &xtemp, &ytemp);
   *x = ytemp - (b / a) * xtemp;
   *y = xtemp;
   return res;
}
int main() {
   int x, y;
   int a = 60, b = 25;
   int res = EuclideanExtended(a, b, &x, &y);
   printf("gcd(%d, %d) = %d", a, b, res);
}

Đầu ra

gcd(60, 25) = 5