C Chương trình cho các thuật toán Euclid cơ bản?

Ở đây chúng ta sẽ xem thuật toán Euclide để tìm GCD của hai số. Có thể dễ dàng tìm thấy GCD (Số chia chung lớn nhất) bằng cách sử dụng thuật toán Euclide. Có hai cách tiếp cận khác nhau. Một là lặp lại, một là đệ quy. Ở đây chúng ta sẽ sử dụng thuật toán Euclid đệ quy.

Thuật toán

EuclideanAlgorithm (a, b)

begin
   if a is 0, then
      return b
   end if
   return gcd(b mod a, a)
end

Ví dụ

#include<iostream>
using namespace std;
int euclideanAlgorithm(int a, int b) {
   if (a == 0)
      return b;
   return euclideanAlgorithm(b%a, a);
}
main() {
   int a, b;
   cout << "Enter two numbers: ";
   cin >> a >> b;
   cout << "GCD " << euclideanAlgorithm(a, b);
}

Đầu ra

Enter two numbers: 12 16
GCD 4