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

Ở đây chúng ta sẽ thấy thuật toán Euclid mở rộng được triển khai bằng C. Thuật toán Euclid mở rộng cũng được dùng để tìm GCD. Nó tìm các hệ số nguyên x và y như sau:

ax+by = gcd(a,b)

Ở đây trong thuật toán nó cập nhật giá trị gcd(a, b) bằng lời gọi đệ quy như sau: gcd(b mod a, a). Hãy xem thuật toán để hiểu ý 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);
}

Kết quả

gcd(60, 25) = 5