โปรแกรม C ++ สำหรับ GCD 0. ของตัวเลข (หรืออาร์เรย์) มากกว่าสองหมายเลข?

ที่นี่เราจะมาดูกันว่าเราจะได้รับ gcd ของตัวเลขมากกว่าสองตัวได้อย่างไร การหา gcd ของตัวเลขสองตัวนั้นง่าย เมื่อเราต้องการหา gcd ที่มากกว่าสองจำนวน เราต้องปฏิบัติตามกฎการเชื่อมโยงของ gcd ตัวอย่างเช่น หากเราต้องการหา gcd ของ {w, x, y, z} มันก็จะเท่ากับ {gcd(w,x), y, z} แล้ว {gcd(gcd(w,x), y) , z} และสุดท้าย {gcd(gcd(gcd(w,x), y), z)} การใช้อาร์เรย์สามารถทำได้ง่ายมาก

อัลกอริทึม

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

ตัวอย่าง

#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);
}

ผลลัพธ์

GCD of array elements: 4