Chương trình C ++ cho GCD 0. của nhiều hơn hai (hoặc mảng) số?

Ở đây chúng ta sẽ thấy cách chúng ta có thể lấy gcd của nhiều hơn hai số. Tìm gcd của hai số rất dễ dàng. Khi chúng ta muốn tìm gcd của nhiều hơn hai số, chúng ta phải tuân theo quy tắc kết hợp của gcd. Ví dụ:nếu chúng ta muốn tìm gcd của {w, x, y, z}, thì nó sẽ là {gcd (w, x), y, z}, sau đó là {gcd (gcd (w, x), y) , z}, và cuối cùng là {gcd (gcd (gcd (w, x), y), z)}. Sử dụng mảng có thể được thực hiện rất dễ dàng.

Thuật toán

gcd (a, b)

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

getArrayGcd (arr, n)

begin
   res := arr[0]
   for i in range 1 to n-1, do
      res := gcd(arr[i], res)
   done
   return res;
end

Ví dụ

#include<iostream>
using namespace std;
int gcd(int a, int b) {
   if (a == 0)
      return b;
   return gcd(b%a, a);
}
int getArrayGcd(int arr[], int n) {
   int res = arr[0];
   for(int i = 1; i < n; i++) {
      res = gcd(arr[i], res);
   }
   return res;
}
main() {
   int arr[] = {4, 8, 16, 24};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "GCD of array elements: " << getArrayGcd(arr, n);
}

Đầu ra

GCD of array elements: 4